[C] 백준 2750번 : 수 정렬하기

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	int N = 0, temp = 0;
	int arr[1000] = { 0, };
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
	}
	for (int i = 0; i < N; i++) {	//시간복잡도가 O(n^2)인 버블정렬
		for (int j = i + 1; j < N; j++) {
			if (arr[i] > arr[j]) {
				temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
	}
	for (int i = 0; i < N; i++) {
		printf("%d\n", arr[i]);
	}
	return 0;
}

N의 범위가 1000으로 크지 않았기에 시간복잡도가 O(n^2)인 버블정렬을 이용할 수 있었습니다.

버블정렬은 정렬 알고리즘 중 상대적으로 간단하지만 비효율적인 정렬입니다.

문제에 나와있는 예제를 도식화하였습니다. arr 배열의 초기상태입니다.

0번째 원소가 (0+1)1번째 원소부터 차례대로 비교를 해나가기 시작하는데

0번째 원소의 값보다 비교하는 값이 더 작다면 두 값을 교환해줍니다.

이때,temp 변수를 이용하여 값이 사라지지 않도록 해줍니다.

아직 첫 번째 루프가 끝나지 않았습니다. 교환한 값인 2보다 작은 값이 있는지 2번 인덱스부터 비교합니다.

마지막 4번 인덱스의 값이 2보다 작으므로 위와 마찬가지로 교환해줍니다.

 

배열의 마지막 원소까지 비교를 마쳤으므로 첫 번째 루프를 마칩니다.

첫 번째 루프를 끝내게 되었을 때 배열의 첫번째 원소는 배열의 값 중 가장 작은 값이 위치합니다.

이를 반복해줍니다.

두 번째 루프입니다. 배열의 두 번째원소와 (2+1)세번째 원소부터 비교를 시작해나갑니다.

배열의 마지막 원소의 값이 두 번째 원소의 값보다 작기 때문에 교환해줍니다.

이후 배열의 네 번째 원소부터 비교를 시작하지만 2보다 작은 값이 없으므로

두 번째 루프는 이렇게 끝이납니다.

잘 보시면 두 번째 루프만에 배열이 오름차순으로 정렬된 것을 알 수 있습니다.

따라서 세 번째 루프부터는 보여드리지 않겠습니다. 비교는 하되 교환은 하지 않으니까요.

 

위 경우는 운이 좋은 경우입니다. 이렇게 운이 좋게 오름차순으로 정렬이 끝났다고 해서

반복문이 멈추는 것은 아닙니다. 항상 마지막 루프까지 성실하게 돕니다.

따라서 버블정렬은 최악,평군,최상의 경우 모두 시간복잡도가 O(n^2)이 됩니다.

 

정렬 알고리즘에 대해서는 따로 분류해서 다루겠습니다.