[알고리즘 정렬] 힙 정렬(Heap Sort)

  힙 정렬(Heap Sort)이란 힙 자료구조 형태의 정렬 방식입니다. 기존 배열을 최대 힙으로 구조 변경 후 정렬을 진행합니다. 알고리즘 복잡도는 O(n log n)입니다.

 

이미지 출처: 위키백과, 힙 정렬 항목

 

  힙 정렬 구현 코드

public class Main {
    public static void heapSort(int[] array) {
        for (int i = array.length / 2 - 1; i >=0 ; i--) {
            heapify(array, i, array.length);
        }
        for (int i = array.length - 1; i > 0; i--) {
            swap(array, 0, i);
            heapify(array, 0, i);
        }
    }
    public static void heapify(int[] array, int parentIndex, int size) {
        int leftIndex = 2 * parentIndex + 1;
        int rightIndex = 2 * parentIndex + 2;
        int maxIndex = parentIndex;

        if (leftIndex < size && array[maxIndex] < array[leftIndex]) {
            maxIndex = leftIndex;
        }
        if (rightIndex < size && array[maxIndex] < array[rightIndex]) {
            maxIndex = rightIndex;
        }
        if (parentIndex != maxIndex) {
            swap(array, maxIndex, parentIndex);
            heapify(array, maxIndex, size);
        }
    }
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

  매개 변수로 배열 array를 받는 heapSort 메소드를 생성합니다.

  첫 번째 for문에서 array의 길이에서 2를 나눈 값에 1을 뺀 값에서부터 i가 0보다 크거나 같을 때까지 i가 1씩 감소하면서 반복문이 진행됩니다. 이는 자식 노드가 있는 노드를 기준으로 정렬을 진행한다는 뜻입니다.

  heapify 메소드를 호출하고 인자에 array, i, array의 길이를 받습니다.

  매개 변수로 배열 array와 정수형 parentIndex, 정수형 size를 받는 heapify 메소드를 생성합니다.

  변수 leftIndex, rightIndex, maxIndex를 생성합니다. 각각 왼쪽 자식 노드, 오른쪽 자식 노드, 부모 노드를 할당받습니다.

  첫 번째 if문에서 leftIndex가 array의 길이보다 작고 동시에 array의 maxIndex 번째 원소보다 array의 leftIndex 번째 원소가 크다면 maxIndex 값을 leftIndex로 갱신합니다.

  두 번째 if문에서 rightIndex가 array의 길이보다 작고 동시에 array의 maxIndex 번째 원소보다 array의 rightIndex 번째 원소가 크다면 maxIndex 값을 rightIndex로 갱신합니다.

  세 번째 if문에서 parentIndex와 maxIndex가 같지 않다면, 즉 앞선 두 if문에서 maxIndex 번째 원소보다 leftIndex 또는 rightIndex 원소가 더 커서 maxIndex의 값이 갱신된 상황을 의미합니다. 이때 swap 메소드를 호출하여 maxIndex의 위치와 parentIndex의 위치를 변경해줍니다. heapify 메소드를 재귀적으로 호출하여 이 과정을 반복합니다.

  매개 변수로 배열 array와 정수형 i, 정수형 j를 받는 swap 메소드를 생성합니다.

  임시 변수 temp에 array의 i번째 원소를 할당합니다.

  array의 i번째 원소에는 array의 j번째 원소를 할당하고, array의 j번째 원소에는 임시 변수 temp를 할당하여 두 원소의 위치를 변경하는 기능이 있습니다.