[자료구조] Merge Sort, Heap Sort, Quick Sort

이번 정렬 알고리즘은 분할 정복 기법을 활용한 알고리즘들인 Merge Sort, Quick Sort 그리고 Heap 구조를 사용한 정렬기법인 Heap Sort를 정리해보려고 한다.

 

분할정복 기법이란?

분할 정복이란, 큰 문제를 해결하기 쉬운 작은 문제들로 나눠서 해결해나가 결국 전체 문제를 해결하는 기법이다. 알고리즘 뿐 아니라 정치, 군사 등 다양한 분야에서 사용되는 기법이다.

분할 정복 알고리즘의 일반적인 큰 흐름은 다음 세 단계로 요약할 수 있다.

1. Divide (분할)
정렬해야 할 원소들을 두 개의 크기가 비슷한 그룹으로 나눈다.
예를 들어, 길이가 n인 배열이면 인덱스 0 … (n/2 - 1)을 왼쪽 그룹, 인덱스 (n/2) … (n-1)을 오른쪽 그룹으로 분할한다.

2. Conquer (정복, 재귀 호출을 이용한 정렬)
분할된 두 그룹 각각을 재귀적으로 정렬한다.
즉, 왼쪽 그룹을 다시 Divide → Conquer → Combine”하고, 오른쪽 그룹도 마찬가지”라는 식으로 재귀 호출이 이어진다.
재귀 호출은 결국 각 그룹 크기가 1(또는 기준 이하)일 때 바로 정렬을 마치는 기저 사례로 내려가게 된다.

3. Combine (결합, 병합 혹은 합치는 단계)
두 그룹이 각각 정렬된 상태가 되면, 이들을 하나의 큰 정렬된 리스트로 합쳐야 한다.
이 과정은 각 알고리즘별로 차이가 있다.

 

Merge Sort(병합정렬)이란?

Merge Sort는 분할 정복 기법의 대표라고 해도 과언이 아니다.

Merge Sort의 경우 하나의 array를 처리하기 적합한 크기까지 계속 절반으로 나눈다

(일반적으로 각 배열의 크기가 1 또는 2로 될 때까지 나눈다)
이후 각 2개의 배열을 비교하면서 정렬된 하나의 배열로 병합해나간다.

 

Merge Sort의 시간복잡도

(길이 N의 배열을 계속 절반으로 나눠 최소 배열 크기로 줄이는 시간) * (병합 비교에 걸리는 시간)

== (logN) * (N) == O(NlogN)

 

Merge Sort 의사코드

MergeSort(A, left, right):
    // A: 정렬할 배열
    // left: 배열의 시작 인덱스 (0부터 시작)
    // right: 배열의 끝 인덱스 (포함)

    if left < right:
        mid = (left + right) // 2

        // 1) 왼쪽 절반 정렬
        MergeSort(A, left, mid)

        // 2) 오른쪽 절반 정렬
        MergeSort(A, mid + 1, right)

        // 3) 병합 과정
        Merge(A, left, mid, right)


Merge(A, left, mid, right):
    // 왼쪽 절반: A[left..mid], 오른쪽 절반: A[mid+1..right] 를 병합하여
    // A[left..right]를 정렬된 상태로 만든다.

    n1 = mid - left + 1       // 왼쪽 부분 배열 길이
    n2 = right - mid          // 오른쪽 부분 배열 길이

    // 임시 배열 생성
    L = new 배열 of size n1
    R = new 배열 of size n2

    // 원본 배열에서 값 복사
    for i from 0 to n1 - 1:
        L[i] = A[left + i]
    for j from 0 to n2 - 1:
        R[j] = A[mid + 1 + j]

    i = 0        // 왼쪽 부분 배열 인덱스
    j = 0        // 오른쪽 부분 배열 인덱스
    k = left     // 병합할 원본 배열 인덱스

    // 두 부분 배열을 비교하며 작은 값을 원본에 채워 넣음
    while i < n1 and j < n2:
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
        k = k + 1

    // 만약 왼쪽 배열에 남은 요소가 있으면 원본에 복사
    while i < n1:
        A[k] = L[i]
        i = i + 1
        k = k + 1

    // 만약 오른쪽 배열에 남은 요소가 있으면 원본에 복사
    while j < n2:
        A[k] = R[j]
        j = j + 1
        k = k + 1

 

 

Quick Sort란?

Quick Sort는 빠른 정렬이라는 의미의 이름과는 별개로 NlogN부터 N²의 시간복잡도를 갖을 수도 있는 특이한 알고리즘이다.

Quick Sort는 다음과 같은 과정으로 정렬된다.

1. 특정한 pivot을 기준으로 작은것, 큰것으로 나눈다.

2. pivot을 기준으로 분할한다.

3. 분할된 구간에서 다시 각각의 pivot을 잡고 각 구간에서 다시 pivot을 기준으로 크고 작은 것으로 구간을 분할한다.

이 과정을 계속 반복하면 정렬이 가능하다.

노란색 : pivot / 초록색 : 정렬끝난 것

 

Quick Sort의 시간복잡도

(Quick sort는 pivot을 기준으로 나누는데 걸리는 시간)*(배열 범위 내 크기를 비교하는 시간)

== 이론상(logN) * N으로 O(NlogN)이 걸린다고 할 수 있지만,

만약 pivot이 극단의 수로만 걸리게 되는 worst case에서는 N개의 pivot을 잡고 N개의 비교를 진행하므로

O(N²)의 시간복잡도를 갖게 된다.

 

Quick Sort 의사코드

QuickSort(A, low, high):
    // A: 정렬할 배열
    // low: 배열의 시작 인덱스 (0부터 시작)
    // high: 배열의 끝 인덱스 (포함)

    if low < high:
        // 1) 분할 지점(pivot index)을 구함
        p = Partition(A, low, high)

        // 2) 피벗 기준 왼쪽 부분 정렬
        QuickSort(A, low, p - 1)

        // 3) 피벗 기준 오른쪽 부분 정렬
        QuickSort(A, p + 1, high)


Partition(A, low, high):
    // A[low..high] 범위를 하나의 피벗 기준으로 분할하고
    // 피벗이 위치할 최종 인덱스를 반환

    pivot = A[low]      // 피벗을 배열의 첫 번째 원소로 선택
    left = low + 1      // 왼쪽 스캔 인덱스
    right = high        // 오른쪽 스캔 인덱스

    while true:
        // 왼쪽 인덱스가 가리키는 값이 피벗보다 작거나 같으면 계속 이동
        while left <= right and A[left] <= pivot:
            left = left + 1

        // 오른쪽 인덱스가 가리키는 값이 피벗보다 크면 계속 이동
        while left <= right and A[right] > pivot:
            right = right - 1

        if left > right:
            break
        else:
            // A[left]가 피벗보다 크고, A[right]가 피벗 이하라면 서로 교환
            swap A[left] and A[right]

    // 마지막으로 피벗을 'right' 위치와 교환하여 경계 설정
    swap A[low] and A[right]

    return right     // 피벗의 최종 인덱스 반환

Heap Sort(힙 정렬)

Heap은 완전 이진트리를 이용한 자료구조이다. 만약 Heap에 대해 잘 모른다면 아래 링크를 타고 알아보도록 하자.

[자료구조] Heap & Priority Queue ADT

[자료구조] Heap & Priority Queue ADT

이 힙의 구조를 이용해서 정렬을 수행하는 방법이 바로 Heap Sort이다.

과정은 다음과 같다.

1. 최대,최소 힙을 구성한 후 root Node와 말단 node를 교체

2. 교체된 말단 Node(전 root Node)를 고정한다.

3. 나머지 Node들로 1과 2를 반복 수행한다.

이렇게 되면 총 N개의 Node를 모두 정렬할 수 있다.

Heap Sort의 시간복잡도

나는 처음 생각했을 때, N개의 Node에 대해 항상 모든 연산을 다 해주면서 진행하면, O(N2)이 되는거 아닌가? 하는 의구심이 들었었다.

그러나 나의 착각은 Heap구조의 이진트리를 고려하지 않았기 때문에 발생했다.

실제로 시간복잡도를 구해보면 (Heap을 구성하는데 걸리는 시간) * (N개의 Node에 대한 연산 시간)

== logN * N == O(NlogN)이라는 것을 알 수 있다.

위 예시도 5 * log₂5 = 5 *2.3219... 이니 대략 9인 시간복잡도에 부합함을 볼 수 있다.

 

 

Heap Sort 의사코드

HeapSort(A, n):
    // 1) 배열 A를 최대 힙으로 변환
    BuildMaxHeap(A, n)

    // 2) 힙 크기를 줄여가며 루트(최댓값)와 마지막 요소를 교환하고 재조정
    heapSize = n
    for i from n - 1 down to 1:
        swap A[0] and A[i]
        heapSize = heapSize - 1
        MaxHeapify(A, 0, heapSize)


BuildMaxHeap(A, n):
    // 배열 A[0..n-1]을 최대 힙 구조로 만든다
    // 마지막 내부 노드의 인덱스는 floor(n/2) - 1 이다
    for i from floor(n / 2) - 1 down to 0:
        MaxHeapify(A, i, n)


MaxHeapify(A, i, heapSize):
    // 인덱스 i를 루트로 하는 서브트리를 최대 힙 조건에 맞게 재조정
    left  = 2 * i + 1       // 왼쪽 자식 인덱스
    right = 2 * i + 2       // 오른쪽 자식 인덱스
    largest = i

    // 왼쪽 자식이 존재하고, 왼쪽 자식이 현재 largest보다 크면 largest 갱신
    if left < heapSize and A[left] > A[largest]:
        largest = left

    // 오른쪽 자식이 존재하고, 오른쪽 자식이 현재 largest보다 크면 largest 갱신
    if right < heapSize and A[right] > A[largest]:
        largest = right

    // 만약 루트(i)가 largest가 아니라면, 교환 후 재귀 호출
    if largest != i:
        swap A[i] and A[largest]
        MaxHeapify(A, largest, heapSize)