C++ 정렬 알고리즘, Merge, Quick, Selection, Insert, Bubble, Heap
Stability
우선 A에 대해 정렬을 하고, 그 정렬된 결과를 바탕으로 B에 대해 정렬했을때 정렬 순서가 그대로 유지되는 알고리즘을 stable 하다고 합니다.
merge 가 대표적인 stable 정렬, quick 이 대표적인 unstable 정렬입니다. 이외에도 selection 이나 heap 같은 정렬이 unstable 합니다.
Sorting Algorithm
몇몇 알고리즘의 특징과 간단한 구현을 담았습니다. 글의 내용은 다른분들의 블로그에서 가져온 내용들이 있으며 출처는 제가 틈틈히 추가하겠습니다. 그리고 때때로 구현은 틀릴 수 있으며 댓글로 달아주시면 감사히 피드백 받아 수정 하겠습니다.
간단한 설명을 드리면 C++ 로 구현이 되있으며, 제네릭하게 사용하기 위해 template 를 이용했습니다. 때문에 비교는 lambda 함수를 받아 comparator 로 이용합니다. comparator의 구현은 다음과 같습니다. 아마 여러분이 C 에서 int 를 비교하길 원하신다면 간단히 > 를 사용하셔도 괜찮습니다.
function<bool(int&, int&)> f = [](int& l, int&r)->bool {
if (l > r) {
return true;
}
return false;
};
기타 Sort
G++ 4.8.2 를 사용했으며, 컴파일은 /cpp/algorithm-folder/ 위치에서 make 를, 클린은 make compile을 하시면 됩니다. 참고로 템플릿 때문에 header 파일만 이용해서 구현 했는데, main.cpp 가 아니라 sort.h 가 바뀔경우는 매번 make clean 을 해야 하더군요.
1.Bubble
버블 정렬의 경우 최악은 O(n^2), 최선은 O(n) 입니다. 그냥 생각해보면 버블정렬은 최선의 경우에 O(n^2) 이라 생각하기 쉬운데 간단한 트릭을 이용하면 O(n) 으로 구현 할 수 있습니다.
template <typename T>
bool Sort<T>::bubble(T* arr, size_t length, function<bool(T&, T&)>& comparator) {
if ( arr == nullptr || length <= 1) {
return false;
}
bool sorted;
for(int i = length; i >1; i--) {
sorted = true;
for(int j = 0; j < i - 1; j++) {
if (comparator(arr[j], arr[j+1])) {
T* temp = new T(arr[j]);
arr[j] = arr[j+1];
arr[j+1] = *temp;
sorted = false;
delete temp;
}
}
if (sorted) {
break;
}
}
return true;
}2. Selection
선택 정렬은 최선, 최악 모두 O(n^2) 입니다. 선택 정렬은 unstable 한데, 그 이유는 여기 에 의하면 다음과 같습니다.
Let b = B in
< B > , < b > , < a > , < C > (with a < b < c)
After one cycle the sequence is sorted but the order of B and b has changed:
< a > , < b > , < B > , < c >
아래는 소스코드입니다.
template <typename T>
bool Sort<T>::selection(T* arr, size_t length, function<bool(T&, T&)>& comparator) {
if(arr == nullptr) {
return false;
}
if (length <= 1) {
return false;
}
for(int i = 0; i < length - 1; i++) {
for(int j = i+1; j < length; j++) {
if( comparator(arr[i], arr[j]) ) {
T* temp = new T(arr[j]);
arr[j] = arr[i];
arr[i] = *temp;
delete temp;
}
}
}
return true;
}3. Insertion
삽입 정렬은 삽입 대상 앞에 있는 원소들이 미리 정렬 되어 있다고 보기때문에 최선의 경우 O(n) 입니다. 삽입만 하면 되지요. Bubble, Selection, Insertion 같은 경우는 In-place 정렬입니다. 많은 메모리를 필요로 하지 않습니다. 위키피디아 에서는 O(1) 이라고 표현합니다. 아래는 소스코드입니다.
template <typename T>
bool Sort<T>::insertion(T* arr, size_t length, function<bool(T&, T&)>& comparator) {
if(arr == nullptr) {
return false;
}
if(length <= 1) {
return false;
}
int j = 0;
for(int i = 1; i < length; i++) {
T* temp = new T(arr[i]);
for(j = i - 1; j >= 0 && comparator(arr[j], *temp); j--)
arr[j+1] = arr[j];
arr[j+1] = *temp;
delete temp;
}
return true;
}4. Quick
퀵 정렬은 unstable 정렬입니다. 그리고 최선일때나 평균적일때 O(nlogn) 의 복잡도를 가집니다. 최악일때는 O(n^2) 이구요. 위 3개의 In-place 정렬과는 다르게 O(nlogn) 의 메모리를 요구합니다.
pivot 이 퀵 정렬의 성능에 지대한 영향을 미치기때문에 pivot 을 구하는 방법이 많이 논의 되어 왔습니다. 대표적인 방법으로 median-of-3 pivot 이 있습니다.
특이하게 퀵 정렬은 O(nlogn) 메모리 중 가장 나은 성능을 보입니다. 이는 퀵 정렬의 내부 루프가 캐시를 히트율이 높게끔 지역화된 메모리 참조를 하기 때문입니다.
평균적으로는 좋으나, 최악의 경우에는 O(n^2) 의 복잡도를 가지기 때문에 개선 방안이 많이 논의 되어왔습니다. 대표적인 예로 인트로 소트 가 있습니다. 인트로 소트 는 평상시에는 퀵소트로 작동하다가, 일정 뎁스 이상이 되면 힙 소트로 변환합니다.
퀵소트에는 위에서 언급한 단점이 있기 때문에 2000년 C++ STL 표준에서는 큰 덩어리에서는 인트로 소트를 사용하고, 엘레먼트가 16개 이하에서는 삽입정렬을 하는 방식이 표준으로 정했습니다.
하단은 퀵소트를 위한 소스코드인데, 일반적으로 널리 알려진 코드보다는 좀 더 간단한 코드를 사용했습니다. (성능이 더 빠르다는 것이 아니라 코드 작성이 더 용이하다는 뜻입니다.)
template <typename T>
bool Sort<T>::quick(T* arr, int length, function<bool(T&, T&)>& comparator) {
if(arr == nullptr) {
return false;;
}
if (length <= 1) {
return false;
}
Sort<T>::internal_quick(arr, 0, length - 1, comparator);
return true;
}
// ref : http://www.algolist.net/Algorithms/Sorting/Quicksort
template <typename T>
void Sort<T>::internal_quick(T* arr, int left, int right, function<bool(T&, T&)>& f) {
int i = left;
int j = right;
int pivot = (left + right) / 2;
while (i <= j) {
while(f(arr[pivot], arr[i])) i++;
while(f(arr[j], arr[pivot])) j--;
if (i <= j) {
T* temp = new T(arr[j]);
arr[j] = arr[i];
arr[i] = *temp;
delete temp;
i++; j--;
}
}
if (left < j) {
internal_quick(arr, left, j, f);
}
if (i < right) {
internal_quick(arr, i, right, f);
}
}5. Merge
머지 정렬은 stable 이며, 최선의 경우에도, 최악의 경우에도 O(nlogn) 이라는 복잡도를 가집니다.
실제 사용시 머지 정렬은 최악의 경우에 O(n^2) 의 복잡도를 가지는 퀵 소트에 비해 성능이 떨어지며, 힙소트보다도 느린 경우가 많습니다. 이는 머지소트가 O(n) 의 추가적인 메모리를 요구하며, 퀵 정렬의 메모리 지역 참조성때문이기도 합니다.
그러나 머지 정렬은 연결리스트의 경우 최적의 선택이 될 수 있습니다. 배열을 머지 정렬 할때는 O(n) 의 추가 공간이 필요하지만, 연결리스트를 머지 소트시에는 O(1) 의 추가 공간만 필요합니다. 배열을 새로 만들어서 옮길 필요 없이 작은 순서부터 차례대로 이어 붙이면 되니까요. 게다가 연결리스트의 느린 랜덤 억세스 때문에 퀵 소트는 제대로 성능을 내지 못하므로 연결리스트에서 머지 정렬은 좋은 선택일 수 있습니다.
template <typename T>
bool Sort<T>::merge(T* arr, int length, function<bool(T&, T&)>& comparator) {
if(arr == nullptr) {
return false;;
}
if (length <= 1) {
return false;
}
Sort<T>::internal_merge(arr, length, comparator);
return true;
}
template <typename T>
void Sort<T>::internal_merge(T* arr, int length, function<bool(T&, T&)>& f) {
if ( length > 1) {
int mid = length / 2;
internal_merge(arr, mid, f);
internal_merge(arr + mid, length - mid, f);
// merge two partial arrays
T* temp = new T[length];
int left, right, index;
for(index = 0, left = 0, right = mid; left < mid && right < length; index++) {
temp[index] = (f(arr[left], arr[right])) ? arr[right++] : arr[left++];
}
while(left < mid) temp[index++] = arr[left++];
while(right < length) temp[index++] = arr[right++];
for(index = 0; index < length; index++) {
arr[index] = temp[index];
}
delete temp;
}
}6. Heap
우선 힙 자료구조(또는 힙 소트) 은 unstable 하지만 최악의 경우에도 O(nlogn) 성능을 보여주며 정렬을 위해 별도의 메모리가 필요 없다는 장점이 있습니다.
힙은 사실 주어진 자료들 중 가장 작은값이나 가장 큰 값을 빠르게 찾기위해 만들어진 자료입니다. 힙은 완전 이진트리의 구조로서 최소 힙 / 최대 힙 두가지 종류가 있으며 각각 부모 노드는 자식 노드보다 작거나 / 크다는 특징을 가지고 있습니다.
힙은 완전 이진트리이므로 삽입시에는 가장 마지막 노드 위치에, 추출시에는 루트가 삭제됩니다. 재미있는 사실은, 힙은 완전 이진트리이므로 배열로 구현하기가 쉽습니다.
루트 노드의 인덱스를 i 라고 했을때, 왼쪽 자식 노드는 i*2, 오른쪽은 i*2 + 1 이고, 부모 노드는 자식노드 index 값을 i 라고 했을때 i / 2 이므로 부모와 자식에 대한 접근 연산이 단순 나눗셈, 덧셈으로 구현되어 접근이 편하기 때문입니다.
물론 이 경우 root 노트의 index 값은 1부터 시작합니다. 0부터 시작하는 경우는 부모와 자식에 대한 연산의 값이 조금 달라질 수 있습니다. 그러나 1부터 시작하는 경우의 장점은, 왼쪽 자식에 대한 접근이 곱하기 2로, 부모에 대한 접근이 나누기 2로 표현되므로 시프트 연산으로 구현할 수 있다는 점입니다.
Heap 구현 코드는 작성중입니다.References :
1. http://sunbeatz.blog.me/140107902878
2. http://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC
3. http://ko.wikipedia.org/wiki/AVL_%ED%8A%B8%EB%A6%AC
4. http://sweeper.egloos.com/920252
5. http://sweeper.egloos.com/891931
