[알고리즘/C] 버블 정렬(bubble sort)

버블 정렬이란?

인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을

리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다.

이 과정이 한번 완료되면 가장 큰 값이 배열의 오른쪽 끝으로 이동한다.

 

버블 정렬(bubble sort)은 이러한 비교-교환 과정을 배열 전체가 정렬될 때까지 계속하는 방법이다.

void bubble_sort(int list[], int n) {
	int i, j;

	for (i = 0; i < n - 1; i++) { //n-1번 반복
		for (j = 0; j < n - i - 1; j++) { //오른쪽 제외
			if (list[j] > list[j + 1]) { //list[j]가 list[j+1]보다 크면, 즉 오름차순으로 정렬되어있지 않으면
				int large = list[j]; //서로 교환한다.
				list[j] = list[j + 1];
				list[j + 1] = large;
			}
		}
	}
}

 

시간복잡도

• 비교 횟수 : 최선, 평균, 최악 모두 1+2+...n-1 = n(n-1)/2
• 이동 횟수 : 최선의 경우 입력 자료가 이미 정렬 되어있는 경우이므로 0, 최악의 경우 역순으로 정렬되어있는 경우이므로 비교횟수에 3을 곱한 수이다. (교환하는 부분에서 3번의 이동이 일어나기 때문에), 평균의 경우 자료 이동이 0번부터 i까지같은 확률로 일어나므로 (0+....n = n(n+1)/2)

따라서 비교 횟수와 이동 횟수를 더하면 시간복잡도는 O(n^2)이다.