Comb Sort

기본 아이디어

Bubble Sort에서 거북이(tutle) 데이터를 줄이고자 한다.
토끼(rabbit) 데이터는 Bubble Sort에서 문제가 되지 않는다.

Bubble Sort

Bubble Sort에서는 인접한 두 데이터의 크기를 비교한다.
비교하는 두 데이터의 거리를 gap이라고 할 떄 Buble Sort는 gap은 1이다.

Comb Sort

gap의 크기를 1보다 크게 한다
각 pass가 진행됨에 다라 gap의 크기를 줄여간다.
[$\frac{n}{k}$,$\frac{n}{k^2}$,$\frac{n}{k^3}$,$\dots$,1]
k값에 따라 Comb Sort의 효율성이 달라진다.
보통 K = 1.3을 권장한다.

---

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

---

구현

#include <iostream>
#include <vector>
#include <cmath>

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

void SelectionSort(vector<int>& A) {
	int n = A.size();
	int jMin;
	for (int i = 0; i < n - 1; i++) {
		jMin = i;
		for (int j = i + 1; j < n; j++) {
			if (A[j] < A[jMin]) {
				jMin = j;
			}
		}
		if (jMin != i) {
			swap(A[jMin], 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);
	SelectionSort(A);
	print(A);
}