정렬(2)
시간 복잡도가 O(N*log2N)인 정렬 방법을 정리합니다.
퀵 정렬
Divide & Conquer 알고리즘.
최악의 경우 속도가 O(N2)가 될 수 있다.(정렬된 데이터에 pivot을 맨 우측으로 잡을 경우)
재귀 전 작업 때문에 재귀 오버헤드가 크다.
- 배열의 한 원소를 고른다. (pivot이라고 부른다)
- pivot보다 작은 원소는 pivot의 왼쪽으로, 큰 요소는 오른쪽으로 옮긴다.
- pivot의 왼쪽 배열과 오른쪽 배열을 다시 1, 2 과정을 거치게 한다.
- 배열의 크기가 0이나 1이 될때까지 반복한다.
void Quick_sort(int ary[], int low, int high) {
if (low < high) {
int pivot = Partition(ary, low, high);
Quick_sort(ary, low, pivot - 1);
Quick_sort(ary, pivot + 1, high);
}
}
int Partition(int ary[], int low, int high) {
int left = low, right = high;
int pivot = ary[left]; // pivot을 가장 왼쪽으로 선택하기로 한다.
while (left < right) {
// pivot보다 큰 원소가 나올 때까지 left를 증가시킨다.
while (ary[left] <= pivot)
left++;
// pivot보다 작은 원소가 나올 때까지 right를 감소시킨다.
while (ary[right] > pivot)
right--;
if (left < right)
swap(ary[left], ary[right]);
}
swap(ary[right], ary[low]);
return right;
}
병합 정렬
공간복잡도가 O(N)이다. 공간이 더 필요하다.
퀵 정렬은 Big -> Small Scale로 정렬하지만, 병합 정렬은 Small -> Big Scale로 정렬하기 때문에 재귀 오버헤드가 없다.
결국에 하나씩 비교하기 때문에 입력 데이터의 사전 정렬에 영향을 받지 않는다.
- 배열을 크기가 1이 될 때 까지 반으로 나눈다.
- 반으로 나뉘어진 배열을 비교하면서 합친다.
void Merge_sort(int ary[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
Merge_sort(ary, left, mid);
Merge_sort(ary, mid + 1, right);
Merge(ary, left, mid, right);
}
}
void Merge(int ary[], int left, int mid, int right) {
int i = left, j = mid + 1, k = left;
int temp[SIZE];
while (i <= mid && j <= right) {
if (ary[i] <= ary[j])
temp[k++] = ary[i++];
else
temp[k++] = ary[j++];
}
if (i > mid) {
for (int l = j; l <= right; l++)
temp[k++] = ary[l];
} else {
for (int l = i; l <= mid; l++)
temp[k++] = ary[l];
}
for (int l = left; l <= right; l++)
ary[l] = temp[l];
}
힙 정렬
우선순위 큐를 이용한 정렬 방법이다.
하나의 삽입, 삭제 과정이 O(logN)의 시간이 걸린다.
전체 데이터 삽입, 삭제 과정은 O(NlogN)의 시간이 걸린다.
