힙 정렬

 

 힙 정렬은 자료구조의 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법이다. 각각의 차이는 내림차순이냐 오름차순이냐에 있다. 트리 구조를 이용해서 작성할 필요는 없고 간단하게 1차원 배열로도 충분히 표현 가능하다. 정렬해야 할 값을 배열에 저장하고 힙 삽입을 통해 차례대로 삽입한다. 이 과정이 끝나면 힙이 구성되는데 배열에서 최소값부터 삭제하면서 정렬한다.

출처 : wiki media

 위의 그림은 최대 힙 정렬을 하는 과정을 보여준다. 부모노드와 자식노드의 크기 비교를 해서 오름차순, 내림차순에 맞게 삽입을 하면서 힙을 구성한다. 다음에는 부모노드를 제거하고 그 자리에 최하위 자식 노드를 삽입한다. 다시 루트 노드의 자식 노드와 크기 비교를 하며 힙을 재구성한다. 이 과정을 반복하면 힙 정렬이 끝난다.

 힙 정렬의 시간 복잡도 또한 O(nlogn)이다.

public class Main {
    public static void buildHeap(int[] a,int n){
        for(int i = (int)Math.floor(n/2);i>=1;i--){
            heapify(a,i,n);
        }
    }
    public static void heapify(int[] a, int k, int n){
        int left = k * 2;
        int right = k * 2+1;
        int smaller;
        if(right <= n){
            if(a[left] < a[right]) smaller = left;
            else smaller = right;
        }
        else if(left <= n)
            smaller = left;
        else
            return;

        if(a[smaller] < a[k]){
            int temp = a[k];
            a[k] = a[smaller];
            a[smaller] = temp;

            heapify(a,smaller,n);
        }
    }
    public static void heapSort(int[] a,int n){
        buildHeap(a,n);
        for(int i = n;i>=2;i--){
            int temp = a[1];
            a[1] = a[i];
            a[i] = temp;
            heapify(a,1,i-1);
        }
    }

    public static void main(String[] args) {
        int[] a= {8,31,48,73,3,65,20,29,11,15};
        //int n = (int)Math.floor(a.length/2);
        for (int i = 0; i <a.length ; i++) {
            //heapify(a,i,9);
            heapSort(a,a.length-1);
           // buildHeap(a,9);
        }

        for(int i:a){
            System.out.printf("%d ",i);
        }
    }
}

이 코드를 실행시키면 다음처럼 8이 정렬이 안된다. 왜 이런 문제가 발생하는지 알 수 없다.

public class HeapSort 
{ 
    public void sort(int arr[]) 
    { 
        int n = arr.length; 
  
        // Build heap (rearrange array) 
        for (int i = n / 2 - 1; i >= 0; i--) 
            heapify(arr, n, i); 
  
        // One by one extract an element from heap 
        for (int i=n-1; i>=0; i--) 
        { 
            // Move current root to end 
            int temp = arr[0]; 
            arr[0] = arr[i]; 
            arr[i] = temp; 
  
            // call max heapify on the reduced heap 
            heapify(arr, i, 0); 
        } 
    } 
  
    // To heapify a subtree rooted with node i which is 
    // an index in arr[]. n is size of heap 
    void heapify(int arr[], int n, int i) 
    { 
        int largest = i; // Initialize largest as root 
        int l = 2*i + 1; // left = 2*i + 1 
        int r = 2*i + 2; // right = 2*i + 2 
  
        // If left child is larger than root 
        if (l < n && arr[l] > arr[largest]) 
            largest = l; 
  
        // If right child is larger than largest so far 
        if (r < n && arr[r] > arr[largest]) 
            largest = r; 
  
        // If largest is not root 
        if (largest != i) 
        { 
            int swap = arr[i]; 
            arr[i] = arr[largest]; 
            arr[largest] = swap; 
  
            // Recursively heapify the affected sub-tree 
            heapify(arr, n, largest); 
        } 
    } 
  
    /* A utility function to print array of size n */
    static void printArray(int arr[]) 
    { 
        int n = arr.length; 
        for (int i=0; i<n; ++i) 
            System.out.print(arr[i]+" "); 
        System.out.println(); 
    } 
  
    // Driver program 
    public static void main(String args[]) 
    { 
        int[] a= {8,31,48,73,3,65,20,29,11,15};
        int n = a.length; 
  
        HeapSort ob = new HeapSort(); 
        ob.sort(a); 
  
        printArray(a); 
    } 
} 

Geeksforgeeks에서 가져온 소스 코드이다. 여기서는 오름차순으로 정렬하고 있는데 추후에 시간이 더 된다면 비교하면서 고쳐봐야겠다. 이 소스로 10000개 데이터 정렬 시간을 구해보자.

0.032초로 복잡한 정렬 알고리즘들 중에서는 느린 편에 속한다.