정렬 알고리즘 (퀵 정렬, 병합 정렬)

이창윤·2022년 7월 27일

퀵 정렬 (Quick Sort)

pivot을 기준으로 두 개의 비균등한 크기로 배열을 분할하고 분할된 부분 배열을 정렬하며 해결하는 방식
pivot보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮긴다.
Devide and conquer 알고리즘이다.

Devide and conquer (분할 정복법): 기존의 문제를 해결하기 쉬운 단위로 나누어 해결한 후 다시 합쳐서 해를 구하는 방법

void quick_sort(int left, int right) {
	if(left < right) {
    	int pivot_index = partition(left, right);
        quick_sort(left, pivot_index-1);
        quick_sort(pivot_index+1, right);
    }
}

int partition(int left, int right) {
	int low = left;
    int high = right + 1;
    int pivot = arr[left];
    
    do{
    	do{ 
        	low++;
        } while(low <= right && arr[low] < pivot);
        do{
        	high--;
        } while(high >= left && arr[high] > pivot);
        if(low < high)
        	swap(arr[low], arr[high]);
    } while(low < high);
    swap(arr[left], arr[high]);
    return high;
}

배열의 첫번째 데이터를 pivot으로 둔다. (어떤 값이든 상관 없다.. GIF에서는 마지막 데이터를 선택)
왼쪽 인덱스 left에서 출발해 pivot보다 큰 데이터를 발견하면 오른쪽 인덱스 right가 pivot보다 작은 데이터를 발견할 때 까지 기다리다가 조건이 맞으면 서로 swap을 한다.
2의 과정을 left가 right를 넘어갈 때 까지 반복한다.
pivot을 왼쪽과 오른쪽 부분 배열의 사이에 넣는다.
pivot을 제외한 왼쪽 배열과 오른쪽 배열을 다시 정렬 및 분할하기 위해 부분 배열의 크기가 0 또는 1이 될 때 까지 재귀 호출을 한다.

시간복잡도

최선, 평균(배열이 균등하게 분할될 때):

비교 횟수: 재귀 호출의 깊이가 logn이고 각 단계에서 비교 연산이 n번 일어나므로 nlogn이다.
이동 횟수: 비교 횟수보다 적으므로 무시

=> O(nlogn)

최악(pivot이 배열의 최소값이거나 최대값이라서 비균등 분할이 계속될 때):

비교 횟수: 재귀 호출의 깊이가 n이고 각 단계에서 비교 연산이 n번 일어나므로 n^2이다.
이동 횟수: 비교 횟수보다 적으므로 무시

=> O(n^2)

장점

시간복잡도가 O(nlogn)으로 가장 빠른 정렬 알고리즘 중 하나이다.
제자리 정렬이라서 추가 메모리 공간을 필요로 하지 않는다.

제자리 정렬: 배열 이외에 추가 메모리를 요구하지 않는 정렬 방법

단점

불안정 정렬이다.

불안정 정렬: 동일한 값을 가진 데이터의 순서가 유지되지 않는 정렬 방법
정렬된 배열은 퀵 정렬의 비균등 분할에 의해 시간이 오래 걸린다. 균등한 크기로 배열을 분할할 수 있는 pivot을 고르는 것이 중요하다.

병합 정렬 (Merge Sort)

배열을 잘게 쪼갠 뒤 합치는 과정에서 해결해나가는 방식
Devide and conquer 알고리즘이다.
다른 정렬 알고리즘과 달리 swap이 일어나지 않는다. (제자리 정렬이 아니다..)

void merge_sort(int low, int high) {
	if(high - low < 2) return;

    int mid = (low+high) / 2;
    merge_sort(low, mid);
    merge_sort(mid+1, high);
    merge(low, mid, high);
}
	
    
void merge(int low, int mid, int high) {
	int[] temp = new int[high - low];
    int t = 0, l = low, h = mid;

    while (l < mid && h < high) {
        if(arr[l] <= arr[h]) {
            temp[t++] = arr[l++];
        } else {
            temp[t++] = arr[h++];
        }
    }
     while (l < mid) {
        temp[t++] = arr[l++];
    }
     while (h <= high) {
        temp[t++] = arr[h++];
    }
     for (int i = low; i <= high; i++) {
        arr[i] = temp[i];
    }
}

분할: 배열을 반으로 나누는 작업을 재귀 호출한다.
모든 부분 배열의 길이가 1이 되면 병합을 시작한다.
병합: 왼쪽의 인덱스 l과 오른쪽의 인덱스 h를 비교하여 더 작은 데이터를 새로운 리스트 temp로 옮긴다.
3의 과정을 한쪽 인덱스가 끝까지 갈 때 까지 반복한다.
남은 인덱스의 데이터를 temp로 마저 옮긴다.
기존 배열에 정렬이 완료된 temp의 값을 옮겨서 복사한다.

시간복잡도

비교 횟수: 재귀 호출의 깊이가 logn이고 각 합병 단계에서 비교 연산이 n번 일어나므로 nlogn이다.

이동 횟수: 재귀 호출의 깊이가 logn이고 각 합병 단계에서의 이동 연산은 임시 배열에 복사했다가 다시 가져와야 하므로 총 2n번 발생한다. 따라서 2nlogn이다.
nlogn(비교) + 2nlogn(이동) = 3nlogn =>
O(nlogn)

장점

안정 정렬이다.
시간복잡도가 O(nlogn)으로 동일해서 데이터의 분포에 영향을 덜 받는다.

안정 정렬: 동일한 값을 가진 데이터의 순서가 유지되는 정렬 방법

단점

정렬하고자 하는 데이터의 개수만큼 따로 저장하고 있어야 하기 때문에 O(n)의 공간복잡도를 가진다. (메모리 공간을 많이 차지한다)
이동 횟수가 많다.
==> 배열 대신 연결리스트를 사용하면 극복 가능

비교 & 정리

병합 정렬은 분할이 균등하게 (절반씩) 일어나지만 퀵 정렬은 불균등하게 일어난다.
퀵 정렬은 최악의 경우를 방지하기 위한 다양한 전략이 존재한다.
- 배열의 랜덤화: pivot으로 배열의 고정된 위치의 데이터를 선택하는 경우 배열 전체를 랜덤화를 한 다음 정렬을 하면 최악의 경우를 피할 수 있다.
- 랜덤 pivot 선택: 난수를 발생시켜 pivot을 선택하는 방법으로, 최악의 경우를 피할 수 있는 확률이 증가한다.
- Median of three pivot: 첫번째, 중간, 마지막 원소를 후보로 두고 그 중간값을 pivot으로 선택하는 방법으로, 최악의 경우를 피할 수 있는 확률이 증가한다.
병합 정렬은 순차적인 비교를 하므로 연결리스트를 정렬할 때 효과적이다. 이동 연산도 링크 인덱스만 변경하면 되므로 효율적이다.
퀵 정렬은 데이터에 임의 접근을 하기 때문에 연결리스트를 정렬하기에 비효율적이다.