[Algorithm] 정렬 - 거품 정렬 (Bubble Sort)

거품 정렬(Bubble Sort)이란?

앞에서부터 차례로 두 개씩 비교하여, 작은 값을 앞으로 정렬하는 방식이다.

 

예)

1)  맨 앞부터, 두 개의 값인 arr[0]과 arr[1]을 비교한다.

 

2)  arr[0]값이 더 크므로 두 값을 교체한다. (작은 값을 앞으로)

 

3)  그 다음 두 개 값인 arr[1]과 arr[2]를 비교한다. arr[2]값이 더 크므로 교체하지 않고 넘어간다.

 

4)  그 다음 두 개 값인 arr[2]와 arr[3]을 비교한다. arr[3]값이 더 크므로 교체하지 않고 넘어간다.

 

5)  그 다음 두 개 값인 arr[3]과 arr[4]를 비교한다.

 

6)  arr[4]값이 더 크므로 두 값을 교체한다.

 

이렇게 1회전을 돌면 제일 큰 값이 맨 뒤에 오게 된다.

따라서 2회전을 돌 때에는, 제일 마지막 값을 제외하고 나머지 4개의 값만 정렬하면 된다.

 

 

소스코드

#include <iostream>

using namespace std;

void bubbleSort(int* arr, int len);

int main() {
	int N;
	cin >> N;

	int* arr = new int[N];
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	bubbleSort(arr, N);

	for (int i = 0; i < N; i++) {
		cout << arr[i] << endl;
	}

	delete[] arr;

	return 0;
}

void bubbleSort(int* arr, int len) {
	for (int i = len - 1; i > 0; i--) {
		for (int j = 0; j < i; j++) {
			if (arr[j] > arr[j + 1]) {
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

 

시간복잡도

평균의 경우 : O(n²)

최선의 경우 : O(n²)

최악의 경우 : O(n²)

 

데이터 총 개수가 n개라고 하면, 비교 횟수는 아래와 같다.

(n-1) + (n-2) + ... + 2 + 1

= n(n-1) / 2

= O(n²)

 

데이터가 정렬되어 있는 경우라고 해도 비교 횟수는 동일하다.

따라서 평균, 최선, 최악의 경우 모두 같은 시간복잡도로 계산된다.