QuickSort, MergeSort, HeapSort

QuickSort는 분할 정복(divide and conquer) 전략을 사용하는 효율적인 정렬 알고리즘 중 하나다. 평균적인 시간 복잡도는 O(n log n)이며, 최악의 경우 시간 복잡도는 O(n^2)이다.

 

작동 원리

1. 분할(Divide): 배열에서 '피벗'이라고 하는 하나의 원소를 선택한다. 피벗의 위치는 다양한 방법으로 선택할 수 있으며, 피벗 선택 방식에 따라 알고리즘의 성능이 달라질 수 있다. 이 피벗을 기준으로 배열을 두 부분으로 나눈다. 피벗보다 작은 모든 요소는 피벗의 왼쪽에, 피벗보다 큰 모든 요소는 피벗의 오른쪽에 오도록 한다.
2. 정복(Conquer): 피벗을 제외한 왼쪽 부분 배열과 오른쪽 부분 배열을 재귀적으로 정렬한다.
3. 결합(Combine): QuickSort는 정복 단계에서 배열을 실제로 정렬하므로, 별도의 결합 단계가 필요하지 않다.

특징

• In-place 정렬: 추가적인 배열을 필요로 하지 않으며, 주어진 배열 내에서 정렬을 수행한다.
• 불안정 정렬(Unstable sort): 동일한 값의 원소가 있을 경우, 원래의 순서가 유지되지 않을 수 있다.
• 피벗 선택 중요: 피벗 선택 방법에 따라 성능이 크게 달라질 수 있다. 예를 들어, 항상 첫 번째 원소를 피벗으로 선택하면 이미 정렬된 배열에 대해 최악의 성능(O(n^2))을 보일 수 있다.

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

 

 

정렬 과정

1. 초기 배열: [3, 6, 8, 10, 1, 2, 1]
2. 피벗 선택: 8 (배열의 중간 요소)
3. 분할:
   • 왼쪽(left): [3, 6, 1, 2, 1] (피벗보다 작은 요소)
   • 중간(middle): [8] (피벗과 같은 요소)
   • 오른쪽(right): [10] (피벗보다 큰 요소)
4. 왼쪽(left) 부분 배열에 대한 재귀적 정렬:
   • 피벗 선택: 1
   • 분할:
     • 왼쪽: [1] (피벗보다 작거나 같은 요소)
     • 중간: [1] (피벗과 같은 요소)
     • 오른쪽: [3, 6, 2] (피벗보다 큰 요소)
   • 오른쪽 부분 배열에 대한 재귀적 정렬:
     • 피벗 선택: 6
     • 분할:
       • 왼쪽: [3, 2] (피벗보다 작은 요소)
       • 중간: [6] (피벗과 같은 요소)
       • 오른쪽: [] (피벗보다 큰 요소가 없음)
     • 왼쪽 부분 배열에 대한 재귀적 정렬:
       • 피벗 선택: 2
       • 분할:
         • 왼쪽: [2] (피벗보다 작은 요소)
         • 중간: [] (피벗과 같은 요소가 없음)
         • 오른쪽: [3] (피벗보다 큰 요소)
     • 재조합: [2, 3, 6]
   • 재조합: [1, 1, 2, 3, 6]
5. 전체 배열에 대한 재조합: [1, 1, 2, 3, 6, 8, 10]

정렬된 배열

• 최종 결과: [1, 1, 2, 3, 6, 8, 10]

 

MergeSort는 분할 정복(divide and conquer) 방법론을 기반으로 하는 효율적인 정렬 알고리즘이다. 평균적으로 O(n log n)의 시간 복잡도를 가지며, 최악의 경우에도 O(n log n)을 유지한다. 이 알고리즘은 배열을 더 이상 나눌 수 없을 때까지 반으로 나눈 다음, 나누어진 배열을 다시 정렬하면서 병합하는 방식으로 작동한다.

 

작동 원리

1. 분할(Divide): 입력 배열을 가장 작은 단위가 될 때까지 계속 반으로 나눈다. 이 과정은 재귀적으로 수행되며, 각 부분 배열이 하나의 요소만을 갖게 될 때까지 계속된다.
2. 정복(Conquer): 나누어진 부분 배열을 다시 병합하면서 정렬한다. 이때, 인접한 두 부분 배열을 정렬하면서 병합하는 방식으로 진행한다.
3. 결합(Combine): 모든 부분 배열이 병합되어 하나의 정렬된 배열이 될 때까지 2단계를 반복한다.

특징

• 안정 정렬(Stable sort): 동일한 값의 요소 사이의 상대적인 순서가 변경되지 않는다.
• 비교적 메모리 사용량이 많음: 병합 과정에서 추가적인 배열이 필요하기 때문에, QuickSort와 같은 일부 다른 정렬 알고리즘에 비해 메모리 사용량이 많다.
• 분할 정복 알고리즘: 데이터를 분할하고, 각각을 정복한 다음, 결과를 결합하는 전형적인 분할 정복 접근 방식을 따른다.

def mergeSort(arr):
    if len(arr) > 1:
        mid = len(arr)//2
        L = arr[:mid]
        R = arr[mid:]

        mergeSort(L)
        mergeSort(R)

        i = j = k = 0

        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

 

 

단계	과정	설명
1	[38, 27, 43, 3, 9, 82, 10]	초기 배열
2	[38, 27, 43] & [3, 9, 82, 10]	배열을 반으로 나눈다.
3	[38] & [27, 43]	왼쪽 부분 배열을 다시 반으로 나눈다.
4	[27] & [43]	[27, 43]을 다시 반으로 나눈다.
5	[27, 43]	[27]과 [43]을 병합하여 정렬한다.
6	[27, 38, 43]	[38]과 [27, 43]을 병합하여 정렬한다.
7	[3] & [9, 82, 10]	오른쪽 부분 배열을 반으로 나눈다.
8	[9] & [82, 10]	[9, 82, 10]을 다시 반으로 나눈다.
9	[82] & [10]	[82, 10]을 다시 반으로 나눈다.
10	[10, 82]	[82]와 [10]을 병합하여 정렬한다.
11	[9, 10, 82]	[9]와 [10, 82]을 병합하여 정렬한다.
12	[3, 9, 10, 82]	[3]와 [9, 10, 82]을 병합하여 정렬한다.
13	[3, 9, 10, 27, 38, 43, 82]	최종적으로 모든 부분 배열을 병합하여 정렬한다.

 

HeapSort는 힙(heap) 자료구조를 기반으로 하는 효율적인 정렬 알고리즘 중 하나다. 이 알고리즘은 최악, 평균, 최선의 경우 모두 O(n log n)의 시간 복잡도를 가진다. HeapSort의 기본 아이디어는 주어진 데이터를 이진 힙(binary heap) 구조로 만든 후, 큰 값들(또는 작은 값들)을 배열의 끝으로 이동시키면서 정렬하는 것이다.

 

힙(Heap) 이란?

힙은 각 노드의 값이 자식 노드의 값보다 크거나 같은(또는 작거나 같은) 완전 이진 트리(complete binary tree)이다. 힙은 크게 두 종류가 있다: 최대 힙(max heap)과 최소 힙(min heap). 최대 힙에서는 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같으며, 최소 힙에서는 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같다.

 

HeapSort의 작동 방식

1. 힙 구성(Heapify): 주어진 배열을 최대 힙 형태로 구성한다. 이 과정은 배열의 중간부터 시작하여 루트 노드까지 거슬러 올라가면서, 각 노드를 올바른 위치로 이동시키는 "heapify" 과정을 반복하여 수행한다.
2. 정렬(Sort): 최대 힙의 루트(가장 큰 값)는 항상 힙의 첫 번째 위치에 있으므로, 이를 배열의 마지막 요소와 교환한다. 배열에서 힙으로 고려되는 부분의 크기를 하나 줄이고(실제로 배열에서 요소를 제거하는 것은 아니다), 변경된 힙에 대해 다시 heapify 과정을 수행한다. 이 과정을 배열이 정렬될 때까지 반복한다.

특징

• In-place 정렬: 추가적인 배열을 필요로 하지 않으며, 주어진 배열 내에서 정렬을 수행한다.
• 불안정 정렬(Unstable sort): 동일한 값의 원소가 있을 경우, 원래의 순서가 유지되지 않을 수 있다.
• 효율적인 시간 복잡도: 모든 경우에 O(n log n)의 시간 복잡도를 제공한다.

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[largest] < arr[left]:
        largest = left

    if right < n and arr[largest] < arr[right]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heapSort(arr):
    n = len(arr)

    for i in range(n//2 - 1, -1, -1):
        heapify(arr, n, i)

    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

 

힙 구성(Heapify) 단계

단계	과정	설명
1	[3, 9, 82, 10, 38, 27, 43]	초기 배열
2	[3, 9, 82, 10, 38, 27, 43]	배열을 최대 힙으로 만들기 시작 (아직 변화 없음)
3	[3, 9, 82, 10, 38, 27, 43]	자식 노드들과 비교하여 최대 힙 속성 만족 (아직 변화 없음)
4	[3, 9, 82, 10, 38, 27, 43]	더 큰 자식 노드와 부모 노드를 계속 교환
5	[82, 9, 43, 10, 38, 27, 3]	최대 힙 구성 완료

 

정렬(Sort) 단계

단계	과정	설명
6	[3, 9, 43, 10, 38, 27, 82]	최대 값(82)을 배열의 끝으로 이동 후 힙 크기 감소
7	[43, 9, 27, 10, 38, 3, 82]	새로운 최대 힙 구성
8	[9, 10, 27, 3, 38, 43, 82]	다음 최대 값(43)을 배열의 끝으로 이동 후 힙 크기 감소
9	[38, 10, 27, 3, 9, 43, 82]	계속해서 최대 힙 구성 및 최대 값을 배열 끝으로 이동
10	[10, 9, 27, 3, 38, 43, 82]	최대 힙 구성 및 최대 값을 배열 끝으로 이동
11	[27, 9, 10, 3, 38, 43, 82]	반복
12	[9, 3, 10, 27, 38, 43, 82]	최종적으로 정렬된 배열