[Data Structure] C++로 구현한 버블 정렬

Bubble Sort

#include <iostream>

void bubbleSort(int arr[]) {
	int n = sizeof(arr) / sizeof(arr[0]);
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < n - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}

int main() {
	int arr[] = { 64,25,12 };

	bubbleSort(arr);

	int len = sizeof(arr) / sizeof(arr[0]);
	for (int i = 0; i < len; i++) {
		std::cout << arr[i] << std::endl;
	}
	return 0;
}

설명

첫번째 for문의 한 사이클이 끝날때 가장 우측의 값은 큰값을 가지고 확정된다. (모든 수를 비교하기 때문에) 따라서 두번째 사이클 에는 우측의 한자리를 제외하고 정렬을 진행한다.

그렇기에 두번쨰 for문의 조건에 -i이 사용되는 것이다.

두번쨰 사이클엔 - 1 (우측숫자 1개 제외)
세번쨰는 -2 (우측숫자 2개 제외)
...

추가 최적화

swap이 일어나지 않으면 미리 함수를 종료하도록 최적화를 더 할 수 있다.

void bubbleSort(int arr[]) {
	int n = sizeof(arr) / sizeof(arr[0]);
	for (int i = 0; i < n - 1; i++) {
		bool swapped = false; // bool 체크 변수 추가
		for (int j = 0; j < n - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
				swapped = true;
			}
		}
		if (swapped == false) {
			return;
		}
	}
}

시간 복잡도

• 최악의 경우: 이중 반복문을 전부 순찰하니.. O(n^2)