[자료구조] 버블 정렬

자 오늘은 정렬 중에 기본인 버블 정렬에 대해 알아보자.

 

버블 정렬은 인접한 두 수를 대수 비교하면서 정렬하는 방법이다. 바로 그림을 보자.

 

 

4  2  3  1  에서 버블 정렬을 1회 시행해 본 그림이다.  4의 위치에 주목해서 보자.

4와 2를 비교하여 2가 우선순위가 앞섬을 알 수 있고 이에 따라 4와 2가 위치가 바뀐다.

마찬가지로 뒤에 숫자들과 비교하면서 자리를 바꿔주면 4는 자기 위치를 찾게 된다.

 

1회 시행에서 4의 위치를 찾았다. 그럼 2회 시행 시 어떤 숫자가 자기 자리를 찾아가겠는가?   3이다.

 

위 과정을 프로그래밍 해보자.

 

#include <stdio.h>

void BubbleSort(int arr[],int n) {
	for (int i = 0; i < n - 1; i++) {
		for (int k = 0; k < n - 1 - i; k++) {  //4의 위치를 찾았다면 4를 건들 필요가 없어진다.
			if (arr[k] > arr[k + 1]) {
				int tmp = arr[k + 1];
				arr[k + 1] = arr[k];
				arr[k] = tmp;  //배열값을 교환하는 알고리즘
			}
		}
	}
}

int main() {
	int arr[] = { 4,2,3,1 };

	BubbleSort(arr, 4);

	for (int i = 0; i < 4; i++) {
		printf("%d ", arr[i]);
	}
}

 

자 이제 시행 횟수를 통해 시간복잡도를 구해보자.

 

4  2  3  1  에서 1회 시행 시 4와 2, 4와 3, 4와 1 총 3번의 비교가 발생했다.

2회 시행 시 2와 3, 3과 1 총 2번의 비교가 발생했다.

 

결국 일반화 시키면 (n-1) + (n-2) + ... + 2 + 1 로

n(n-1)/2 로 나타낼 수 있으며 시간복잡도는 O(n^2) 임을 알 수 있다.