Bubble Sort

기본 아이디어

인접한 두 숫자를 비교하여 두 수의 정렬순서가 맞지 않는 경우에는 교환(swap)한다.
마치 깊은 물 속의 큰 물방울이 표면으로 떠 오르는 것과 같이 큰 데이터들이 배열의 왼쪽에서 오른쪽 이동하기 때문에 Bubble Sort 라 부른다.

Pass

맨 왼쪽 인접한 두 숫자를 비교하기 시작하여 맨 오른쪽 인접한 두 숫자를 비교할 때 까지 연속적으로 인접한 두 숫자를 비교해 두 숫자의 정렬 순서가 맞지 않을 경우에는 교환한다.

제일 큰 숫자가 맨 오른쪽으로 이동하면서 이 숫자는 더이상 다음 Pass에 포함시지 않는다.

---

비교 연산자 실행 횟수는 best case든 worst case든 n(n-1)/2 만큼 실행된다.

---

토끼와 거북이 데이터

토끼 데이터 (rabbit data)

왼쪽에 있는 큰 데이터들은 빠르게 오른쪽위치로 이동한다.

거북이 데이터 (tutle data)

오른쪽에 있는 작은 데이터들은 매우 느리게 왼쪽 제 위치로 이동한다.

특징

In-Place Algorithm : 입력 데이터를 저장하는 메모리 이외에 상수 메모리만 필요하다.
Stable sorting Algorithm : 크기가 같은 데이터가 정렬된 이후에도 입력된 순서를 그대로 유지한다.
big-O notation : O($n^2$)의 시간 복잡도를 가지고 있다.

구현

#include <iostream>
#include <vector>

using namespace std;
void swap(int& i, int& j) {
	int k;
	k = i;
	i = j;
	j = k;
}

void BubbleSort(vector<int>& A) {
	int n = A.size();
	for (int pass = 1; pass < n; pass++) {
		for (int i = 1; i <= n - pass; i++) {
			if (A[i - 1] > A[i]) {
				swap(A[i - 1], A[i]);
			}
		}
	}
}

void print(vector<int> A) {
	for (auto el : A) {
		cout << el << " ";
	}
	cout << endl;
}
void main() {
	vector<int> A = { 9,6,3,1,2,4,5,7,8 };
	print(A);
	BubbleSort(A);
	print(A);
}