버블정렬

버블정렬의 특징

1. 인접 비교 기반 정렬

바로 옆 두 원소만을 비교해서 순서에 맞게 교환하는 방식이다. 멀리 떨어진 배열과는 비교하지 않기 때문에, 한 번에 한 칸씩만 이동할 수 있다.

 

2. 시간 복잡도

버블 정렬의 시간복잡도는, 바깥 루프가 n번 돌고, 안쪽 루프는 바깥 루프가 진행될수록 반복 횟수가 점점 줄어들어(n-1, n-2, ..., 1) 총 비교 횟수는 등차수열 합 공식에 의해 n(n-1)/2번이 된다. 이를 빅오 표기법으로 나타내면 최고차항(n²)만 남기고 상수와 낮은 차수 항을 생략하여 O(n²)의 시간복잡도를 가진다.

 

3. 안정 정렬(Stable Sort)다.

값이 같은 두 원소가 있을 때, 원래 순서가 그대로 유지 된다.

 

4. 제자리 정렬(In-place Sort)

추가 배열이나 메모리 공간이 거의 필요없다. temp 변수 하나로 교환만 하면 되니까 공간 복잡도는 O(1)이다.

 

5. 실전성

실전성은 거의 없다. 같은 O(n²)계열에선 삽입 정렬이 대부분의 경우 버블 정렬보다 실교환 횟수가 적어서 더 빠르고, 큰 데이터 셋에는 O(n log n)인 다른 정렬법을 사용한다.

 

정렬 과정

처음 내가 작성한 코드

#include <stdio.h>


int main() {
	int aList[5] = { 30, 40, 10, 50, 20 };
	int temp = 0;
	int rotationCount = 0;

	for (int i = 0; i < sizeof(aList) / sizeof(int); i++) {

		for (int j = sizeof(aList) / sizeof(int)-1; j > i; j--) {
			if (aList[j] < aList[j - 1]) {
				temp = aList[j - 1];
				aList[j - 1] = aList[j];
				aList[j] = temp;

			}
		}
		++rotationCount;

	}
	
	for (int i = 0; i < sizeof(aList) / sizeof(int); i++) {
		printf("%d \t", aList[i]);
	}
	printf("\n회전 횟수 : %d", rotationCount);
	return 0;
}

 

개선점

위 코드가 문제라고는 할 수 없으나, 개선 방향을 고려한다면 스왑플래그를 도입하는 방식을 생각 해 볼 수 있다. 스왑플래그란 매 회전마다 데이터 교환이 실제로 발생했는지를 기록하는 변수이다. 만약 어떤 회전에서 교환이 한 번도 일어나지 않았다면, 이는 배열이 이미 정렬 완료된 상태임을 의미하므로 남은 회전을 더 반복할 필요 없이 즉시 종료할 수 있다.

개선한 코드

#include <stdio.h>


int main() {
	int aList[5] = { 30, 40, 10, 50, 20 };
	int temp = 0;
	int rotationCount = 0;

	for (int i = 0; i < sizeof(aList) / sizeof(int); i++) {
		int swapflag = 0;
		for (int j = sizeof(aList) / sizeof(int)-1; j > i; j--) {
			if (aList[j] < aList[j - 1]) {
				temp = aList[j - 1];
				aList[j - 1] = aList[j];
				aList[j] = temp;
				swapflag = 1;
			}
		}
		++rotationCount;
		if (!swapflag)
			break;
	}
	
	for (int i = 0; i < sizeof(aList) / sizeof(int); i++) {
		printf("%d \t", aList[i]);
	}
	printf("\n회전 횟수 : %d", rotationCount);
	return 0;
}

실제 효과

이 예제(n = 5)에서는 조기 종료 최적화를 적용하지 않은 경우 바깥 루프가 총 5회 실행되지만, 3회전 (i = 2) 시점에 이미 배열이 정렬 완료되어 교환이 발생하지 않는다. 따라서 swapflag를 통해 이 시점에서 반복을 종료하면 바깥 루프 실행 횟수를 5회에서 3회로 줄일 수 있으며, 이는 약 40%의 반복 횟수 감소에 해당한다. 데이터 크기가 작은 예제에선 미미해 보이지만, 입력 데이터가 이미 정렬에 가까운 상태에선 이러한 최적화가 큰 효과를 낼 수 있다.