[Java+Python]힙 정렬(Heap Sort)

<Java + Python>으로 구현한 다른 정렬:

 

[Java+Python]삽입 정렬(Insert Sort)

[Java+Python]버블 정렬(Bubble Sort)

[Java+Python]선택 정렬(Selection Sort)

[Java+Python]병합 정렬(Merge Sort)

[Java+Python]퀵 정렬(Quick Sort)

[Java+Python]카운팅 정렬(Counting Sort)

 

힙 정렬은 말 그대로 힙 자료구조를 이용해 정렬하는 방식을 말한다.

 

왜 힙 트리가 아니라 힙 자료구조라고 하냐면.. 힙 트리는 구현될 때 주로 배열을 이용하기 때문이다.

 

힙 트리에 대해선 지난번에 정리해둔 글이 있으니 참고.

 

2022.09.28 - [Development/Java] - [Java]자료구조 - 힙 트리(Heap Tree)

[Java]자료구조 - 힙 트리(Heap Tree)

짧게 요약하자면 힙 트리는 컬렉션 프레임워크의 우선순위 큐를 구현하는데 사용되기도 하며,

 

정해진 기준에 따라 완전 이진트리 형태로 자료를 '반 정렬'해 삽입하여 최대, 최솟값을 O(1)의 속도로 찾기 위한 자료구조이다.

 

여기서 반 정렬, 혹은 약한 힙이란 부모-자녀 노드의 정렬은 되어있으나 형제 노드 간의 정렬은 되어있지 않은 상태를 말한다.

 

위와 같은 성질에 의해 힙 정렬은 선택 정렬과 비슷한 알고리즘 구조를 보이며,

 

최솟값(최댓값)을 찾을 때 전부 순회하느냐 아니면 힙을 사용하느냐의 차이로 구분된다고 할 수 있다.

 

비슷한 효율을 내는 병합 정렬과 비교했을 때, 자료의 상태와 상관 없이 일정한 속도를 낸다는 특징을 공유하면서도

 

공간 복잡도가 O(1)이라는 장점, 그리고 안정 정렬이 아니라는 단점이 존재한다.

 

추가로 이론적인 시간복잡도와는 다르게 현실세계에선 퀵 정렬이 일반적인 경우 빠르게 동작한다고 한다(캐시 친화적).

 

계속해서 대략적인 정렬 알고리즘과 구현에 대해 알아보자.

 

Algorithm

 

힙 트리와 배열은 언제나 변환이 가능하다는 점에서 착안한 알고리즘이다.

 

사실 힙 트리뿐 아니라 모든 배열과 트리는 상호 변환이 가능하지만 힙 트리를 이루고 있는 완전 이진트리의 경우엔

 

배열에 구멍이 없이 배치가 가능하다는 특징을 가진다.

 

먼저 주어진 배열을 힙 트리에 맞게 배열한 후 최상위 노드를 하나씩 새로 배치하는 식으로 정렬이 진행된다.

 

힙 트리에 대해 알고 있다면 그다지 새로운 알고리즘은 아니다.

 

Implementation

 

가장 간단하게는 마찬가지로 힙 트리를 이용하는 우선순위 큐를 활용해 구현할 수 있다.

 

하지만 그건 그냥 주어진 배열을 존재하는 자료구조에 넣어 정렬시키는 거나 다름이 없다.

 

실 사용에서는 당연이 그게 맞겠지만, 여기서는 주어진 배열을 그대로 이용해 구현해 보자.

 

단계는 두 개로 나뉜다.

 

1. 주어진 배열을 (최대) 힙에 맞게 정렬
2. 순서대로 데이터 삭제 및 배열을 정렬

 

추가로, 완전 이진트리의 경우 배열의 사이즈 및 인덱스를 알면 위 그림처럼 부모/자녀 노드의 인덱스를 바로 알 수 있다.

 

먼저 1번 노드부터 시작해 끝까지 순회하며 힙 트리에 배열을 집어넣는다.

 

이후엔 0번 노드(최댓값)와 마지막 노드의 순서를 바꾼 뒤 힙 트리 정렬을 재귀호출로 부르는 식이다.

 

추가로 겉멋이 들어서 swap 메서드를 따로 분리해 보았다.

import java.util.Arrays;

public class HeapSort {

    public static void main(String[] args) {

        int[] arr = {4, 16, 31, 5, 4, 17, 1, 10, 15, 3, 16, 6, 7, 2, 2, 1, 5, 13, 17, 14, 4, 0};
        int l = arr.length;

        heapSortImpl(arr, l);

        System.out.println(Arrays.toString(arr));
    }

    private static void heapSortImpl(int[] arr, int l) {

        if (l == 0) return;
        /*
         * 1번 노드부터 시작해 부모 노드와 값을 비교하며 정렬한다
         */
        for (int i = 1; i < l; i++) {

            while (i != 0) {

                int parent = (i - 1) / 2;

                if (arr[parent] < arr[i]) {
                    swap(arr, parent, i);
                } else break;

                i = parent;
            }
        }
        /*
         * 정렬이 끝났으면 최상위 노드를 배열 마지막에 채우고 재귀호출
         */
        swap(arr, 0, l - 1);

        heapSortImpl(arr, l - 1);
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

[0, 1, 1, 2, 2, 3, 4, 4, 4, 5, 5, 6, 7, 10, 13, 14, 15, 16, 16, 17, 17, 31]

파이썬 구현은 다음과 같다.

def swap(lst, i, j):
    temp = lst[i]
    lst[i] = lst[j]
    lst[j] = temp


def heap_sort(lst, l):
    if l == 0:
        return

    for i in range(1, l):
        while i != 0:
            parent = (i - 1) // 2

            if lst[parent] < lst[i]:
                swap(lst, parent, i)
            else:
                break

            i = parent

    swap(lst, 0, l - 1)

    heap_sort(lst, l - 1)


lst = [4, 16, 31, 5, 4, 17, 1, 10, 15, 3, 16, 6, 7, 2, 2, 1, 5, 13, 17, 14, 4, 0]
l = len(lst)

heap_sort(lst, l)

print(lst)

[0, 1, 1, 2, 2, 3, 4, 4, 4, 5, 5, 6, 7, 10, 13, 14, 15, 16, 16, 17, 17, 31]