[c++] 알고리즘 개념공부 :: 정렬 (퀵 정렬, 합병 정렬)

퀵 정렬

개념

퀵 정렬의 세부과정은 다음과 같다.

 

pivot이라는 요소를 선택한 후, pivot을 기준으로 왼쪽에는 pivot보다 작은 요소들을 놓고 오른쪽에는 pivot보다 큰 요소들을 놓는다.

 

이후 순환호출을 이용하여 재귀적으로 왼쪽, 오른쪽으로 분류해둔 요소들에 대해 전과 같은 과정을 반복한다. 위의 그림은 오른쪽 요소들에 대해 순환호출한 모습이다.

 

 분할이 불가능할 때까지 반복하다보면 최소한의 요소로 나누어지고 이후 순서대로 결합을 진행한다. 위의 그림에서 색이 칠해져있는 요소들을 순서대로 합치면 된다.

 

퀵 정렬은 분할 정복 알고리즘 중 하나이다. pivot으로 2개의 부분 배열을 생성하는 분할(Divide) 과정과 부분 배열을 재귀적으로 호출하는 정복(Conquer) 과정과 정렬된 부분 배열을 합병하는 결합(Combine)과정이 존재한다.

 

(분할 정복)

 

구현

의사코드는 다음과 같다.

function quicksort(left, right):
    pivot := arr[left]
    low := left+1
    high := right

    while low < high:
        pivot보다 큰 요소를 가진 index 찾기 => low
        pivot보다 작은 요소를 가진 index 찾기 => high
        arr[low]와 arr[high] 교환

    high와 pivot 교환

end

 

c++로 구현한 코드는 다음과 같다.

void quickSort(int* arr, int left, int right) {
    if (right - left <= 1)
        return;

    int pivot = arr[left];
    int low = left+1;
    int high = right-1;
    while (1) {
        while(low<right){
            if (arr[low] > pivot)
                break;
            else
                low++;
        }
        while(high>left){
            if (arr[high] < pivot)
                break;
            else
                high--;
        }
        if (low >= high)
            break;
        swap(arr, low, high);
    }
    swap(arr, left, high);
    quickSort(arr, left, high);
    quickSort(arr, high + 1, right);
}

 

시간 복잡도

최선과 최악의 경우를 생각해보자.

 

 퀵 정렬에서 최선의 경우는 분할되는 두 부분 리스트가 크기가 비슷할 때일 것이다. 최선의 경우에서 리스트의 길이가 1/2로 줄어든다고 했을 때, 1이 되기까지 lgn번의 분할이 필요하다. 또한 각 단계마다 리스트들이 low, high를 움직이며 pivot과 비교하는 횟수는 합쳐보면 n에 비례한다. 따라서 비교횟수는 O(nlgn)이다. 이동 횟수는 비교횟수에 비해서 적으므로 고려하지 않는다.

 

한 쪽으로 치우치는 최악의 경우에는 pivot과 다른 모든 요소를 비교하여 가장 큰(or 작은) 요소를 거르는 선택 정렬과 같은 양상을 띄므로 시간복잡도가 O(n^2)이다.

이러한 경우를 막기 위해 pivot을 랜덤으로 정하거나 주어진 리스트를 무작위로 섞은 후 정렬을 진행하기도 한다.

그렇다면 평균 시간 복잡도는 어떻게 알 수 있을까? 

 

---

(필요없다면 스킵해도 된다.)

위와 같이 pivot에 대해 왼쪽 오른쪽으로 요소들을 정리하고 나면, 리스트에서의 pivot 위치가 드러나게 되는데 리스트를 두 분류로 나눌 수(split) 있다는 뜻에서 이를 splitpoint라고 한다.

 

$$
A(n) = n-1 + \sum \frac{1}{n}(A(i-1) + A(n-i))
$$

 

splitpoint가 i일 때의 비교횟수는 splitpoint를 찾기 위해 다른 요소들과 비교하는 n-1번에다가 재귀적으로 왼쪽 i-1개를 퀵 정렬하는데에 필요한 평균 비교횟수, 오른쪽 n-i개를 퀵 정렬하는데에 필요한 평균 비교횟수를 더한 것과 같다. 따라서 splitpoint를 1부터 n까지 옮겨가며 평균 비교횟수를 더하고 경우의 수 n으로 나누어주면 위와 같은 식이 완성된다.

 

$$
\sum_{i=1}^{n}(A(i-1)+A(n-i))
$$

이 식은 풀어쓸 경우에

이므로

$$
\sum_{i=0}^{n-1}2A(i)
$$

이다.

그렇다면 최종적으로

$$
A(n) = n-1 + \sum_{i=0}^{n-1}2A(i)
$$

라는 식이 나오게 되는데, 이 식이 최선의 경우에 가까운지 최악의 경우에 가까운지를 수학적 귀납법으로 판단해보자.

---

따라서 평균 시간복잡도는 최선의 시간복잡도에 가까운 O(nlgn)이다.

 

특징

• 찰스 앤터니 리처드 호어가 개발했다.
• 불안정 정렬이다.
• 비교 정렬이다.
• 평균적으로 가장 빠른 정렬 방법이다.
• 분할 정복 기법을 사용했다.
• 이후 나올 합병 정렬, 힙 정렬이 항상 O(nlgn)인 것에 반해 퀵 정렬은 평균 시간복잡도가 O(nlgn)이다.

 

 

합병 정렬

개념

합병 정렬 또한 퀵 정렬과 같이 분할 정복 기법을 사용한 정렬이다. 합병 정렬의 세부과정은 다음과 같다.

 

먼저 주어진 배열을 분할한다.

 

분할 된 각각의 요소들을 비교하여 합병(정복)한다.

 

합병의 세부 과정은 위와 같다. A, B 두 리스트를 합병한다고 했을 때 각각의 리스트에 포인터를 둔다. 포인터의 요소를 비교하여 작은 순으로 새로운 배열 C에 저장하고, 한 배열의 모든 요소를 모두 저장했다면 다른 배열의 남은 요소를 C에 저장한다. 위에서는 A의 요소가 먼저 모두 저장되었기 때문에 그 후, B의 남은 요소들을 C에 저장했다.

 

구현

의사코드는 다음과 같다.

function merge(left, mid, right):
    l:=left
    r:=right
    sorted := []
    while l<mid+1 && r<right:
        if arr[l]<arr[r]:
            sorted에 arr[l++] 넣기
        else
            sorted에 arr[r++] 넣기

    남은 배열 sorted에 넣기
    sorted 배열 arr[left,right]에 저장
end

function mergesort(left, right):
    if left==right:
        return;

    mid:= (left+right)/2
    mergesort(left,mid);
    mergesort(mid+1,right);
    merge(left, mid, right);
end

 

c++로 구현한 코드는 다음과 같다.

void merge(int* arr, int left, int mid, int right) { 
    int l = left; int r = mid; 
    int* sorted = (int*)malloc(sizeof(int)*(right - left));
    int index = 0;

    while (l < mid && r < right) {
        if (arr[l] < arr[r])
            sorted[index++] = arr[l++];
        else
            sorted[index++] = arr[r++];
    }

    // 남은 배열 넣기
    if (l >= mid) {
        // 왼쪽 배열을 다 넣었으면
        for (int i = r; i < right; i++)
            sorted[index++] = arr[i];
    }
    else if(r >= right){
        // 오른쪽 배열을 다 넣었으면
        for (int i = l; i < mid; i++)
            sorted[index++] = arr[i];
    }

    // sorted => arr
    for (int i = 0; i < right-left; i++) {
        arr[i+left] = sorted[i];
    }
}

void mergeSort(int* arr, int left, int right) {
    if (right-left<=1) // 원소가 하나이면 return
        return;

    int mid = (int)((left + right) / 2);
    mergeSort(arr, left, mid);
    mergeSort(arr, mid, right);
    merge(arr, left, mid, right);
}

 

시간 복잡도

 합병 단계에서 n만큼의 요소를 훑으면서 비교하고 합치는 과정을 lgn 단계만큼 반복한다. 따라서 비교의 시간복잡도는 O(nlgn)이다. 이동은 기존 배열에서 새로운 배열으로 요소들을 옮기는 과정과 새로운 배열에서 기존 배열로 요소들을 옮기는 과정에 의해 2n번 발생하고, 이를 lgn 단계만큼 반복하므로 이동의 시간복잡도는 O(2nlgn)이다.

 

 따라서 합병 정렬의 총 시간 복잡도는 O(nlgn)이며 최악, 최선, 평균에서 큰 차이 없이 비슷하다.

퀵 정렬과 비교해서 생각해보면 분할 과정에서 쏠림현상 없이 균등하게 분배되므로 항상 퀵 정렬의 최선의 경우와 같다. 식으로 나타내보면 다음과 같다.
$$
O(n) = O(\lceil\frac{n}{2}\rceil)+O(\lfloor\frac{n}{2}\rfloor)+ n-1
$$

 

특징

• 퀵 정렬과 비교하여 최악의 시간복잡도도 O(nlgn)이다.
• 하지만 공간복잡도가 O(n)으로 큰 편이다.
• 안정 정렬이다.
• 초기 데이터 상태에 영향을 덜 받는다.