ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [Sort] 힙 정렬(Heap Sort]
    CSE/Sort 2015. 6. 12. 15:52

    힙 정렬(Heap Sort)






     



    정의힙이라는 자료구조를 이용하여 정렬하는 방법


    힙은 삭제 연산을 수행하면 가장 최상위 루트원소를 반환한다.


    최상위 루트원소는 힙 내부에서 가장 큰 원소이다.





    힙정렬....


    힙을 이용해서 정렬을 하므로 굉장히 쉽게 사용되죠~



    왜냐면 힙 구현해 놓고 삭제 연산을 하면 정렬이 되니깐요!!!



    한번 봅시다 !






    1단계






     



    자 이렇게 최대 힙이 구성이 되어있습니다!!!


    여기서 힙의 삭제연산을 합니다!!




    삭제 연산은 루트 를 반환한다고 했죠???


    루트를 반환하고 힙은 다시 최대 힙을 구성합니다!



    아래처럼 말이죠~




     



    1단계 끝!!














    2단계



    삭제 연산을 진행해야 겠죠???


    아래처럼 진행됩니다!!




     



    계속 힙안에 있는 원소를 삭제 시키는 겁니다...










    3단계



    계속 삭제...


    힙이 보잘것 없어서 아예 없어 질때까지...




     









    4단계



     










    5단계





     












    6단계






     












    7단계












    8단계




    자 이렇게 마무리가 됩니다!!






     

     



    이 힙 정렬의 시간 복잡도(Time Complexity)는 아래와 같습니다!


    모든 케이스에 대해


     


    를 갖습니다!!!




    자 그럼 소스 코드로 예제를 살펴 봅시다~



    HeapMain.java



     

    1
    2
    3
    4
    5
    6
    7
    8
    9
    package Heap;
     
    public class HeapMain {
        public static void main(String[] args) {
            int[] arr = { 69103021683122 };
            HeapSort.heapSort(arr);
        }
    }
     
    cs



    HeapSort.java


     

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
     
    package Heap;
     
    import Selection.SelectionSort;
     
    public class HeapSort {
        public static void heapSort(int[] arr) {
            Heap heap = new Heap();
     
            for (int i = 0; i < arr.length; i++) {
                heap.insertHeap(arr[i]);
            }
     
            for (int i = arr.length - 1; i >= 0; --i) {
                arr[i] = heap.deleteHeap();
     
            }
            System.out.println("힙 정렬 :");
            SelectionSort.printArr(arr);
        }
    }
     
    cs



    Heap.java

     

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
     
    package Heap;
     
    public class Heap {
        private int heapSize;
        private int itemHeap[];
     
        public Heap() {
            heapSize = 0;
            itemHeap = new int[50];
        }
     
        public void insertHeap(int item) {
            int i = ++heapSize;
     
            while ((i != 1) && (item > itemHeap[i / 2])) {
                itemHeap[i] = itemHeap[i / 2];
                i /= 2;
            }
     
            itemHeap[i] = item;
        }
     
        public int getHeapSize() {
            return this.heapSize;
        }
     
        public int deleteHeap() {
            int parent, child;
            int item, tmp;
            item = itemHeap[1];
            tmp = itemHeap[heapSize--];
            parent = 1;
            child = 2;
     
            while (child <= heapSize) {
                if ((child < heapSize) && (itemHeap[child] < itemHeap[child + 1]))
                    child++;
     
                if (tmp >= itemHeap[child])
                    break;
     
                itemHeap[parent] = itemHeap[child];
                parent = child;
                child *= 2;
            }
     
            itemHeap[parent] = tmp;
            return item;
        }
    }
     
    cs





    실행 결과는 아래와 같습니다!!!


     


     


    'CSE > Sort' 카테고리의 다른 글

    [Sort] 기수 정렬(Radix Sort)  (0) 2015.06.12
    [Sort] 합병 정렬(Merge Sort)  (0) 2015.06.12
    [Sort] 셸 정렬(Shell Sort)  (0) 2015.06.12
    [Sort] 퀵 정렬(Quick sort)  (1) 2015.06.12
    [Sort] 삽입 정렬(Insertion sort)  (0) 2015.06.12
    [Sort] 버블 정렬(Bubble Sort)  (0) 2015.06.12

    댓글

Designed by Tistory.