[정렬] 퀵 정렬, 병합 정렬, 힙 정렬

정렬(2)

시간 복잡도가 O(N*log₂N)인 정렬 방법을 정리합니다.

• 퀵 정렬
• 병합 정렬
• 힙 정렬

퀵 정렬

Divide & Conquer 알고리즘.

최악의 경우 속도가 O(N²)가 될 수 있다.(정렬된 데이터에 pivot을 맨 우측으로 잡을 경우)

재귀 전 작업 때문에 재귀 오버헤드가 크다.

1. 배열의 한 원소를 고른다. (pivot이라고 부른다)
2. pivot보다 작은 원소는 pivot의 왼쪽으로, 큰 요소는 오른쪽으로 옮긴다.
3. pivot의 왼쪽 배열과 오른쪽 배열을 다시 1, 2 과정을 거치게 한다.
4. 배열의 크기가 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. 배열을 크기가 1이 될 때 까지 반으로 나눈다.
2. 반으로 나뉘어진 배열을 비교하면서 합친다.

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)의 시간이 걸린다.