[C 언어] 백준 2750. 수 정렬하기

---

2750. 수 정렬하기 (누르면 해당 문제로 이동)

시간 복잡도가 O(n^2)인 정렬 알고리즘으로 풀 수 있습니다.

예를 들면 삽입 정렬, 거품 정렬 등이 있습니다.

 

제약사항)

시간 : 1 초

메모리 : 128 MB

 

문제)

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

 

입력)

첫째 줄에 수의 개수 N(1<=N<=1,000) 이 주어진다.

둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다.

수는 중복되지 않는다.

 

출력)

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

입출력 예제

입력	출력
5 5 2 3 4 1	1 2 3 4 5

 

---

 

풀이 순서)

[ 삽입 정렬 (insertion sort) ]

- 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여,

  자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘입니다.

- 배열이 길어질수록 효율이 떨어지지만 구현이 간단한 장점이 있습니다.

- 선택 정렬이나 거품 정렬과 같은 O(n^2) 알고리즘에 비교하여 빠르며 안정 정렬이고 in-place 알고리즘입니다.

삽입 정렬(insertion sort)의 예

 

[ 거품 정렬 (bubble sort) ]

- 두 인접한 원소를 검사하여 정렬하는 알고리즘입니다.

- 시간 복잡도가 O(n^2)로 상당히 느리지만, 코드가 단순하여 자주 사용되는 방법입니다.

 

---

 

소스코드 및 결과 (C)

 

[ 삽입 정렬 (insertion sort) ]

#include <stdio.h>

int main() {
	int N, tmp;
	int num[1024] = { 0, };

	scanf("%d", &N);
	for (int i = 0; i < N; i++)
		scanf("%d", &num[i]);

	for (int i = 1; i < N; i++) {
		for (int j = 0; j < i; j++) {
			if (num[i] < num[j]) {
				tmp = num[i];
				for (int k = i; k >= j; k--) {
					num[k] = num[k - 1];
				}
				num[j] = tmp;
				break;
			}
		}
	}

	for (int i = 0; i < N; i++)
		printf("%d\n", num[i]);

	return 0;
}

 

메모리 : 1112 KB

시간 : 0 ms

코드길이 : 428 B

 

 

 

[ 거품 정렬 (bubble sort) ]

#include <stdio.h>

int main() {
	int N, tmp = 0, flags = 0;
	int num[1024] = { 0, };

	scanf("%d", &N);
	for (int i = 0; i < N; i++)
		scanf("%d", &num[i]);

	while (1) {
		flags = 0;
		for (int i = 1; i < N; i++) {
			if (num[i-1] > num[i]) {
				tmp = num[i];
				num[i] = num[i - 1];
				num[i - 1] = tmp;
			}
			else
				flags++;
		}
		if (flags == N-1)
			break;
	}

	for (int i = 0; i < N; i++)
		printf("%d\n", num[i]);

	return 0;
}

 

메모리 : 1112 KB

시간 : 0 ms

코드길이 : 442 B

 

---