Heap Sort

Heap Sort 를 구현해보자. 과정은 다음과 같다.

1. 정렬할 배열을 Max Heap 배열로 만든다.
2. 최대값을 배열의 마지막으로 옮긴다.( 오름차순 정렬일 경우 )
3. 정렬할 사이즈를 줄이고 1과 2를 반복한다.

우선 내가 만든 코드를 보자.

 

#include <stdlib.h>
#inlcude <stdio.h>

void HeapSort(int* arr, int len);
void Heapify(int* arr, int idx, int len);
void swap(int* num1, int* num2);

int main()
{
    int len; scanf("%d",&len);
    int* arr = (int*)malloc(sizeof(int)*len);

    for(int i=0; i<len; i++)
        scanf("%d",&arr[i]);

    HeapSort(arr, len);

    free(arr);
    return 0;
}

void HeapSort(int* arr, int len)
{
    // 최대 힙 배열로 만든다.
    // 자식 노드가 없는 노드부터 루트노드까지 진행하며 최대힙 배열을 만든다.
    int startIndex = len/2;
    for(int i=0; i<len/2+1; i++)
    {
        Heapify(arr, startIndex,len);
        startIndex--;
    }
        

    int curSize = len;
    for(int i=0; i< len-1; i++)
    {
        // 첫 번째 인덱스와 마지막 인덱스 의 데이터를 교환한다.
        swap(&arr[0], &arr[curSize-1]);
        // 사이즈를 줄여 최대 힙 배열로 만든다.
        curSize--;
        Heapify(arr, 0, curSize);
    }
    
}

void Heapify(int* arr, int idx, int len)
{
    int leftChildIdx = 2*idx + 1;
    int rightChildIdx = 2*idx + 2;

    // 자식 노드가 없으면 return;
    if(leftChildIdx >= len) return;
    // idx 가 음수이면 return;
    if(idx < 0 ) return;

    // 자식이 1 개인지 2 개인지 구분
    if(rightChildIdx < len )
    {
        // 자식 노드가 2 개이면
        if(arr[leftChildIdx] < arr[rightChildIdx] && arr[idx] < arr[rightChildIdx])
        {
            swap(&arr[idx], &arr[rightChildIdx]);
            Heapify(arr, rightChildIdx, len);
        }
        else if(arr[leftChildIdx] >= arr[rightChildIdx] && arr[idx] < arr[leftChildIdx])
        {
            swap(&arr[idx], &arr[leftChildIdx]);
            Heapify(arr, leftChildIdx, len);
        }
        else
            return;
    }
    else
    {
        // 자식 노드가 1 개이면
        if(arr[idx] < arr[leftChildIdx] )
        {
            swap(&arr[idx], &arr[leftChildIdx]);
            Heapify(arr, leftChildIdx, len);
        }
        else
            return;
    }
}

void swap(int* num1, int* num2)
{
    int temp = *num1;
    *num1 = *num2;
    *num2 = temp;
}

 

다른 사람이 만든 코드를 보며 수정해보자. 함수중 Heapify 로직이 더 깔끔한데, 이를 보자.

void Heapify(int* arr, int idx, int len)
{
    int largest = idx;
    int l = 2*idx + 1;
    int r = 2*idx + 2;

    // l 과 r 을 순차적으로 비교하고 largest 변수를 활용한다.
    if(l < len && arr[largest] < arr[l])
        largest = l;
    
    if(r < len && arr[largest] < arr[r])
        largest = r;
    
    if( largest != idx ) // largest 가 root 가 아니면
    {
        swap(&arr[idx], &arr[largest]);
        Heapify(arr,largest,len);
    }
}