Merge / Quick / Heap Sort (Medium)
출처(위키피디아/GeeksforGeeks)
1. Merge Sort(병합 정렬)
- 분할 정복 알고리즘.
- 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로 분할한다. (원소가 하나인 리스트는 정렬된 것과 같으므로)
- 부분 리스트가 하나만 남을때까지 반복해서 병합하며 정렬된 부분리스트를 생성한다.
- 마지막 남은 부분리스트가 정렬된 리스트이다.
- Stable / Not in place
| 최악 시간복잡도 | Θ( n log n ) |
| 최선 시간복잡도 | Θ( n log n ) |
| 평균 시간복잡도 | Θ( n log n ) |
| 공간 복잡도 | Θ( n ) |
void merge(int arr[], int l, int m, int r){
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for(int i=0; i<n1; i++)
L[i] = arr[l+i];
for(int i=0; i<n2; i++)
R[i] = arr[m+1+i];
int i = 0;
int j = 0;
int k = l;
while( i < n1 && j < n2){
if(L[i] <= R[j])
arr[k++] = L[i++];
else
arr[k++] = R[j++];
}
while(i < n1){
arr[k++] = L[i++];
}
while(j < n2){
arr[k++] = R[j++];
}
}
// Top-Down
void mergeSort(int arr[], int l, int r){
if (l<r){
int m = (l+r-1)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr,l,m,r);
}
}
// Bottom-Up
void mergeSortIterative(int arr[], int l, int r){
for(int m=1; m<=r-l; m=2*m){
// m = 1, i = 0, 2, 4, 6, 8...
// m = 2, i = 0, 4, 8...
// m = 4, i = 0, 8...
for(int i=l; i<r; i+=2*m){
int start = i;
int mid = i + m - 1;
int end = min(i + 2*m - 1, r);
merge(arr, start, mid, end);
}
}
}2. Quick Sort(퀵 정렬)
- 리스트 가운데서 하나의 원소(피벗)를 구한다.
1. 첫 번째 원소를 선택
2. 마지막 원소를 선택 (이미 정렬된 입력에 대해 Θ( n ^ 2 ))
3. 랜덤 원소를 선택
4. 중간 원소를 선택
- 피벗 앞에는 피벗보다 값이 작은 원소들이 오고, 뒤에는 피벗보다 값이 큰 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나누다. (Partition)
- 분리된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트이 크기가 0이나 1일 될때까지 반복된다.
- Unstable / In-place
| 최악 시간복잡도 | Θ( n ^ 2 ) |
| 최선 시간복잡도 | Θ( n log n ) |
| 평균 시간복잡도 | Θ( n log n ) |
| 공간 복잡도 | Θ( log n ) |
inline void swap(int &a, int &b){
int t = a; a = b; b = t;
}
int partition(int arr[], int low, int high){
int &pivot = arr[high];
int i = low - 1;
for(int j=low; j < high; j++){
// If current element is smaller than the poivot
if(arr[j] < pivot)
swap(arr[++i], arr[j]);
}
swap(arr[++i], pivot);
return i;
}
void quickSort(int arr[], int low, int high){
if(low < high){
// pi is partioning index, arr[p] is now at right place
int pi = partition(arr, low, high);
quickSort(arr, low, pi-1);
quickSort(arr, pi+1, high);
}
}
void quickSortIterative(int arr[], int low, int high){
// create auxiliary stack
int stack[high - low + 1];
// initialize top of stack
int top = -1;
// push initial low and high to stack
stack[++top] = low;
stack[++top] = high;
while(top >= 0){
// pop high and low
high = stack[top--];
low = stack[top--];
// Set pivot element at its correct position in sorted array
int p = partition(arr, low, high);
// If there are elements on left side of pivot
if(p - 1 > low){
// then push left side to stack
stack[++top] = low;
stack[++top] = p - 1;
}
// If ther are elements on right sidf of pivot
if(p + 1 < high){
// then push right side to stack
stack[++top] = p + 1;
stack[++top] = high;
}
}
}
3. Heap Sort(힙 정렬)
- 최대 힙 or 최소 힙 트리를 구성해 정렬을 하는 방법으로 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.
- 입력에 대해 최대 힙을 구성한다.
- 가장 큰 수(루트에 위치)를 힙의 마지막 항목과 교체하고 힙의 크기를 1 줄인다. (힙의 크기가 1이 될때까지 반복)
- Unstable / In-place
| 최악 시간복잡도 | Θ( n log n ) |
| 최선 시간복잡도 | Θ( n log n ) |
| 평균 시간복잡도 | Θ( n log n ) |
| 공간 복잡도 | Θ( 1 ) |
void heapify(int arr[], int n, int i){
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
// If left child is larger than root
if(l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than root
if(r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i){
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n){
// Build Heap
for(int i = n / 2 - 1; i>=0; i--)
heapify(arr, n, i);
for(int i = n - 1; i > 0; i--){
// move current root to end
swap(arr[0], arr[i]);
// heapify on the reduced size
heapify(arr, i, 0);
}
}
※ Merge Sort Vs Quick Sort :
Merge Sort 보다 Quick Sort가 선호되는 이유는 Quick Sort가 In-place 이기 때문, Merge Sort의 경우 O(N)의 공간 복잡도를 요구 (이에 필요한 추가 시간 필요).
어떤 입력에 대해서 항상 동일한 반응 시간을 요구하는 시스템에서는 Merge Sort가 적합하다고 할 수 있음, Quick Sort의 경우 특정 데이타의 경우 느린 응답 속도를 보일 수 있다.
하지만 입력 데이타 형식이 array가 아닌 linked list일 경우 Merge Sort가 더 유리, linked list의 경우 index에 따른 접근이 제한적이며 Quick Sort에서는 이런 행우이가 빈번하게 발생한다.