정렬 - 힙정렬

힙 정렬

힙 정렬은 이진 트리를 이용해서 정렬해 나가는 방식이다.

힙 생성 시 최대 힙으로 생성하고, 왼쪽 자식의 인덱스는 부모 인덱스의 / 2, 오른쪽 자식의 인덱스는 부모 인덱스의 / 2 + 1 이라는 점을 이용한다.

단, 배열은 인덱스가 0부터 시작하지만 힙 정렬에서 예시로 사용하기 위해서, 배열의 0번을 비우고 1번부터 사용하기로 한다.

이를 위해 출력과 랜덤 값 채우기 메서드를 힙 정렬에 맞추어 아래와 같이 조금 변경했다.

template <typename T> 
void swap(T *a, T *b) {
    T temp = *a;
    *a = *b;
    *b = temp;
    return;
}

template <typename T>
void printArrayForHeap(T &array, int size) {
    for (int i = 1; i <= size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    return;
}

int *generateRandomArrayForHeap(int size) {
    int *myArray = (int *)calloc(size + 1, sizeof(int));
    srand((unsigned)time(NULL));
    for (int i = 1; i <= size; i++) {
        myArray[i] = rand() % 100;
    }
    return myArray;
}

static int arrayLength = 20;
int *myArray = generateRandomArrayForHeap(arrayLength);

printArrayForHeap(myArray, arrayLength); // 정렬 전 배열 출력

// 배열을 최대 힙에 맞게끔 순서를 변경한다.
for (int currentIndex = 2; currentIndex <= arrayLength; currentIndex ++) {
    while (currentIndex > 1) {
        int parentIndex = currentIndex / 2; // 부모 인덱스는 자식 인덱스의 / 2
        if (myArray[currentIndex] > myArray[parentIndex]) { // 만일 자식이 부모보다 크다면, 둘이 스왑 후 다시 탐색
            swap(&myArray[currentIndex], &myArray[parentIndex]);
            currentIndex = parentIndex;
        }
        else {
            break; // 자식이 부모보다 작다면 OK, 다음 요소 검사
        }
    }
}

for (int i = arrayLength; i >= 2; i --) { // 맨 마지막부터 힙 정렬이 되기 때문에, 맨 앞에서부터 뒤쪽을 줄여 가며 반복
    swap(&myArray[1], &myArray[i]); // 최대 힙의 맨 첫번째 항목과 현재 스코프의 맨 마지막 항목을 스왑
    heapSortCheck(myArray, 1, i - 1); // 최대 힙 만들기
}

printArrayForHeap(myArray, arrayLength); // 정렬 후 배열 출력

void heapSortCheck(int *myArray, int currentIndex, int checkLength) {
    int checkIndex = currentIndex; // 검사할 인덱스
    int leftChildIndex = currentIndex * 2; // 왼쪽 자식 인덱스
    int rightChildIndex = currentIndex * 2 + 1; // 오른쪽 자식 인덱스

    if (leftChildIndex <= checkLength && (myArray[leftChildIndex] > myArray[checkIndex])) {
        // 왼쪽 자식 인덱스가 범위 이내이고, 자식이 부모보다 크다면
        checkIndex = leftChildIndex;
    }
    if (rightChildIndex <= checkLength && (myArray[rightChildIndex] > myArray[checkIndex])) {
        // 오른쪽 자식 인덱스가 범위 이내이고, 자식이 부모보다 크다면
        checkIndex = rightChildIndex;
    }

    if (checkIndex != currentIndex) { // 만일 변경점이 있다면
        swap(&myArray[currentIndex], &myArray[checkIndex]); // 부모와 자식을 스왑 후
        heapSortCheck(myArray, checkIndex, checkLength); // 바꿔진 인덱스를 다시 검사
    }
}

작은 것부터, 점점 커지게, 오름차순으로 정렬한 예제이다.

힙 정렬은 O(N * log N) 의 복잡도를 가지게 된다. 복잡도와 더불어, 메모리 또한 추가적인 배열이 필요하지 않다는 점에서 매우 효율적이라고 볼 수 있다.