정렬 알고리즘 _ 6. 힙 정렬

🧶 정렬 알고리즘

• 선택 정렬
• 버블 정렬
• 삽입 정렬
• 병합 정렬
• 퀵 정렬
• 힙 정렬

이번에는 힙 정렬
힙 정렬을 위해선 힙에 대해 알아야 한다.
완전 이진트리의 일종으로 우선순위 큐 라고도 한다.
최댓값이나 최솟값을 쉽게 추출할 수 있는 자료구조이다.

🎐 힙 정렬

힙 정렬 (Heap Sort): 최대 힙 트리나 최소 힙 트리를 구성하여 정렬을 하는 방법이다.

진행 과정
1. 정렬해야 될 배열을 힙 구조로 만든다.
2. 그 다음에 0번째 값을 마지막 값과 바꾼다.
3. 힙의 사이즈를 -1
4. 힙 사이즈가 1 보다 크면 반복

🎢 구현

public class HeapSort {

    public int[] sort(int[] data) {

        // 힙 구조로 변경
        for (int i = 1; i < data.length; i++) {
            int child = i;
            do {
                int root = (child - 1) / 2;
                if (data[root] < data[child]) {
                    int temp = data[root];
                    data[root] = data[child];
                    data[child] = temp;
                }
                child = root;
            } while (child != 0);
        }

        // 정렬
        for (int i = data.length - 1; i >= 0; i--) {
            int temp = data[0];
            data[0] = data[i];
            data[i] = temp;
            int root = 0;
            int child = 1;
            do {
                child = 2 * root + 1;
                if (child < i - 1 && data[child] < data[child + 1]) {
                    child++;
                }

                if (child < i && data[root] < data[child]) {
                    temp = data[root];
                    data[root] = data[child];
                    data[child] = temp;
                }
                root = child;
            } while (child < i);
        }

        return data;
    }
}

테스트 코드

class HeapSortTest {
    @Test
    void heap_sort_test() {
        int[] answer = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int[] arr1 = {4, 1, 7, 9, 2, 5, 6, 3, 8};
        int[] arr2 = {2, 1, 8, 9, 4, 3, 6, 5, 7};

        HeapSort heapSort = new HeapSort();

        assertArrayEquals(answer, heapSort.sort(arr1));
        assertArrayEquals(answer, heapSort.sort(arr2));

        int[] arr3 = new int[100];
        Random random = new Random();
        for (int i = 0; i < 100; i++) {
            arr3[i] = random.nextInt(1000);
        }
        final int[] answer3 = Arrays.copyOf(arr3, arr3.length);
        Arrays.sort(answer3);
        assertNotEquals(Arrays.toString(answer3), Arrays.toString(arr3));// 정렬전에는 다르고
        assertArrayEquals(answer3, heapSort.sort(arr3));//정렬후에는 같아야 함
    }
}

테스트 결과

정리

• 장점
  - 속도가 빠르다. O(n * log(n))