힙 정렬 (Heap Sort)

원하는 기준으로 요소를 배열하는 정렬 알고리즘

 

 

 

힙 정렬 (Heap Sort)

힙 정렬은 효율적인 비교 기반 정렬 알고리즘입니다. 힙 정렬은 최대 힙, 최소 힙이라는 자료구조를 사용합니다. 힙은 완전 이진 트리의 일종으로, 힙의 모든 부모 노드는 그 자식 노드보다 크거나 같은 값을 가지는 특성을 가집니다. 이 특성을 이용하여 배열을 힙으로 구성하여 최소값을 찾고 남은 배열을 또 힙 구조로 만들어 최소값을 찾아서 정렬을 완성합니다. 

 

시간 복잡도 

평균 : O(n log n)

최악의 경우 : O(n log n) 

 

힙에서 자료의 추가, 삭제는 O(log n)입니다. 이를 배열을 순회하면서 일어납니다. 배열의 순회는 O(n)으로 최종적으로 시간 복잡도는 O(n log n)이 됩니다. 

 

 

 

장점

• 일정한 성능 : 데이터의 분포에 상관없이 일정한 성능을 보장합니다. O(n log n)
• 제자리 정렬 : 입력 배열에서 정렬이 일어나므로 추가적인 메모리가 필요하지 않습니다.

 

단점

• 안정적이지 않음 : 같은 요소의 순서가 정렬 후에 바뀔 수 있습니다. 

 

 

 

동작 과정

힙 정렬은 크게 두 단계로 이루어 집니다. 힙 구성 단계와 정렬 단계입니다. 

 

 

1. 힙 구성 단계

주어진 배열을 힙 구조로 변환합니다. 배열의 끝에서부터 시작하여 부모 노드가 자식 노드보다 크도록 배열을 재구성 합니다. 

 

2. 정렬 단계 

최대 흽 루트를 배열의 마지막 요소와 교환합니다. 나머지 부분들을 다시 힙 구조로 재구성합니다. 이 과정을 정렬될 때까지 반복합니다. 

 

 

 

예시

입력 배열 : [4, 10, 3, 5, 1] 

 

 

1. 힙 구성 

입력 배열을 최대 힙으로 구성합니다. 

배열 : [10, 5, 3, 4, 1] 

 

2. 힙에서 가장 큰 요소 제거 및 정렬 

힙의 루트인 10을 배열의 마지막 요소와 교환하여 정렬합니다. 

배열 : [1, 5, 3, 4, 10]

 

3. 힙 재구성 및 반복

정렬된 10을 제외하고 다시 힙을 재구성합니다.

배열 : [5, 4, 3, 1, 10] 

 

정렬된 부분을 제외한 마지막 요소와 힙의 루트를 교환하여 정렬합니다.

배열 : [1, 4, 3, 5, 10] 

 

이런 식으로 정렬이 완성될 때까지 과정을 반복합니다. 

 

 

Java 코드

/*
힙 정렬
이진 힙 구조를 사용

배열을 최대 힙으로 변환한다. (부모 노드의 값이 자식 노드들의 값보다 항상 크다.)
힙의 루트(가장 큰 값)을 배열의 마지막 요소와 교환하고 힙의 크기를 하나 줄인다.
이 과정을 힙이 비워질 때까지 반복한다.

자기 자신의 배열에서 계속 힙 구조를 만들기 때문에 추가적인 메모리는 들어가지 않는다.
 */
public class HeapSort {

  public static void main(String[] args) {
    int[] array = {3,1,5,9,4,8,7};
    printArray(array);
    heapSort(array);
    printArray(array);
  }

  public static void heapSort(int[] array) {
    int n = array.length;

    // 최대 힙 구성
    // 완전 이진 트리에서 배열의 절반 이후의 요소들은 모두 리프 노드 (절반 이전은 모두 부모 노드)
    // n/2-1 부터 시작하여 루트 노드까지 거꾸로 이동하여 부모 노드를 입력값으로 넣어 자식 노드와 비교
    // 자식 노드가 더 크다면 부모 노드와 교환한다. 이 과정을 반복하여 root 노드에 최대값이 오게 된다.
    for(int i = n/2-1; i>= 0; i--) {
      heapify(array, n ,i);
    }

    // 힙 정렬
    for(int i = n -1 ; i > 0; i--) {
      swap(array, 0, i);
      
      // 감소된 힙에 대해 힙 조정 (i는 n-1, n-2 이런 식으로 크기가 줄어듬)
      heapify(array, i , 0);
    }
  }

  // heap 조정 함수 (root 노드(0번째 인덱스)에 최댓값을 배치한다.)
  // 부모와 자식을 비교하여 자식이 높은 경우 부모와 자리를 바꾼다. 즉 큰 값을 부모한테 올린다.
  public static void heapify(int array[], int heapSize, int rootIndex) {

    int largest = rootIndex;
    int leftChildIndex  = 2 * rootIndex + 1;
    int rightChildIndex = 2 * rootIndex + 2;

    // 왼쪽 자식이 더 큰 경우
    if(leftChildIndex < heapSize && array[leftChildIndex] > array[largest]) {
      largest = leftChildIndex;
    }

    // 오른쪽 자식이 더 큰 경우
    if(rightChildIndex < heapSize && array[rightChildIndex] > array[largest]) {
      largest = rightChildIndex;
    }

    // 최대값이 루트가 아닌 경우
    if (largest != rootIndex) {
      swap(array, largest, rootIndex);

      heapify(array, heapSize, largest);
    }
  }

  public static void swap(int[] array, int largest, int rootIndex) {
    int temp = array[largest];
    array[largest] = array[rootIndex];
    array[rootIndex] = temp;
  }



  public static void printArray(int[] array) {
    for(int number : array) {
      System.out.print(number + " ");
    }
    System.out.println();
  }

}

 

 

 

 

마무리

이번에는 힙 정렬을 정리했습니다.

다음에는 Java의 sort() 메소드에서 사용하는 듀얼 피벗 퀵소트와 팀소트에 대해 정리하겠습니다.

감사합니다.