Data Structure - Sorting ( Heap Sort )

Heap Sort

• 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법입니다.
• 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 됩니다.
• 과정
  • 정렬해야 할 n개의 요소들로 최대 힙(완전 이진 트리 형태)를 만듭니다.
  • 그 다음에 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 됩니다.
  • 삭제되는 요소들(최댓값부터 삭제)는 값이 감소되는 순서로 정렬되게 됩니다.

max Heap을 삭제하고 추가하는 과정은 이미 안다고 가정하고 코드를 바로 짜 보도록 하겠습니다.

 

아래 코드는 Max Heap을 구현한 다음에 최댓값 부터 pop해 가면서 배열의 뒷 쪽 부터 삽입해 가는 코드라고 보시면 됩니다.

/heap_sort.c

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

#define ARR_SIZE 100

#define HEAP_FULL(n) (n == ARR_SIZE - 1)
#define HEAP_EMPTY(n) (!n)

int sorted[ARR_SIZE];

typedef struct
{
    int key;
} element;

element heap[ARR_SIZE];

void push(element item, int *n)
{
    int i;
    // 만약 힙이 꽉 차있다면
    if (HEAP_FULL(*n))
    {
        fprintf(stderr, "The heap is full. \n");
        exit(EXIT_FAILURE);
    }
    i = ++(*n);
    while ((i != 1) && (item.key > heap[i / 2].key))
    {
        heap[i] = heap[i / 2];
        i /= 2;
    }
    heap[i] = item;
}

element pop(int *n)
{
    int parent, child;
    element item, temp;
    if (HEAP_EMPTY(*n))
    {
        fprintf(stderr, "The heap is empty. \n");
        exit(EXIT_FAILURE);
    }
    item = heap[1];
    temp = heap[(*n)--];
    parent = 1;
    child = 2;
    while (child <= *n)
    {
        if ((child < *n) && (heap[child].key < heap[child + 1].key))
            child++;

        if (temp.key >= heap[child].key)
            break;

        heap[parent] = heap[child];
        parent = child;
        child *= 2;
    }
    heap[parent] = temp;
    return item;
}

void heap_sort(int a[], int n)
{
    int count = 0, i;
    element newElement = {0};

    // 우선 int 배열의 값을 하나씩 heap에 집어 넣어주어야 한다.
    for (int i = 0; i < n; i++)
    {
        newElement.key = a[i];
        push(newElement, &count);
    }

    for (i = (n - 1); i >= 0; i--)
    {
        a[i] = pop(&count).key;
    }
}

int seqSearch(int a[], int k, int n)
{
    int i;
    for (i = 1; i < n && a[i] != k; i++)
        ;

    if (i >= n)
        return -1;
    return i;
}

void swap(int *a, int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void insertionSort(int a[], int n)
{
    /* sort a[0:n - 1] into nondecreasing order( 오름 차순 ) */
    int i, j, key;
    for (i = 1; i < n; i++)
    {
        key = a[i];
        // 현재 정렬된 배열은 i - 1까지 이므로 i - 1번째부터 역순으로 조사합니다.
        for (j = i - 1; j >= 0 && a[j] > key; j--)
            a[j + 1] = a[j];
        a[j + 1] = key;
    }
}

int partition(int list[], int left, int right)
{
    int pivot;
    int low, high;

    low = left;
    high = right + 1;
    pivot = list[left]; // 정렬할 리스트의 가장 왼쪽 데이터를 피벗으로 선택 ( 임의의 값을 피벗으로 선택 )

    /* low와 high가 교차할 때까지 반복 (low < high) */
    do
    {
        /* list[low]가 피벗보다 작으면 계속 low를 증가 시켜줘야 한다. */
        do
        {
            low++;
        } while (list[low] < pivot && low <= right); // low가 만약에 right이 된다면 멈처 주어야 합니다.

        do
        {
            high--;
        } while (list[high] > pivot && high >= left);

        // 만약 low와 high가 교차하지 않았으면 list[low]를 list[high]와 교환
        if (low < high)
            swap(list + low, list + high);
    } while (low < high);

    // low와 high가 교차했으면 반복문을 빠져나와 list[left]와 list[high]을 교환해줘야 한다.
    swap(list + left, list + high);

    // 피벗의 위치인 high를 반환해주어야 합니다.
    return high;
}

void quick_sort(int list[], int left, int right)
{
    /* 정렬할 범위가 2개 이상의 데이터가렴( 리스트의 크기가 0이나 1이 아니라면) */
    if (left < right)
    {
        // partition함수를 호출하여 피벗을 기준으로 리스트를 비균등 분할 - 분할(Divide)
        int q = partition(list, left, right);
        // 피벗을 제외한 2개의 부분 리스트를 대상으로 순환 호출
        quick_sort(list, left, q - 1);  // (left ~ 피벗 바로 앞) 앞쪽 부분 리스트 정렬 - 정복(Conquer)
        quick_sort(list, q + 1, right); // (피벗 바로 뒤 ~ right) 뒤쪽 부분 리스트 정렬 - 정복(Conquer)
    }
    else
    {
        return;
    }
}

void merge(int list[], int left, int mid, int right)
{
    int i, j, k, l;
    i = left;
    j = mid + 1;
    k = left;

    /* 분할 정렬된 list의 합병 */
    while (i <= mid && j <= right)
    {
        if (list[i] <= list[j])
            sorted[k++] = list[i++];
        else
            sorted[k++] = list[j++];
    }

    // 남아 있는 값들을 일괄 복사
    if (i > mid)
        for (l = j; j <= right; j++)
            sorted[k++] = list[j];
    else
        for (l = i; i <= mid; i++)
            sorted[k++] = list[l];

    for (l = left; l <= right; l++)
        list[l] = sorted[l];
}

void merge_sort(int list[], int left, int right)
{
    int mid;

    // 원소가 1개가 아닌 경우
    if (left < right)
    {
        mid = (left + right) / 2;         // 중간 위치를 계산하여 리스트를 균등 분할 - 분할(Divide)
        merge_sort(list, left, mid);      // 앞쪽 부분 리스트 정렬 - 정복(Conquer)
        merge_sort(list, mid + 1, right); // 뒤쪽 부분 리스트 정렬 - 정복(Conquer)
        merge(list, left, mid, right);    // 정렬된 2개의 부분 배열을 합병하는 과정 - 결합(Combine)
    }
    else
    {
        // 원소가 1개라면 그냥 return시켜 주면 된다.
        return;
    }
}

void printArr(int a[], int n)
{
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    putchar('\n');
}

int main(void)
{
    int sortArr[ARR_SIZE] = {0};
    int count = 0;

    FILE *fp_read = fopen("sort.txt", "r");
    while ((fscanf(fp_read, "%d", sortArr + count) != EOF))
    {
        count++;
    }

    printf("original array: ");
    printArr(sortArr, count);

    // printf("[ 4 ] is in index %d\n", seqSearch(sortArr, 4, count));

    int sortArr_2[ARR_SIZE];
    memcpy(sortArr_2, sortArr, sizeof(int) * ARR_SIZE);
    printf("insertion sort:\t");
    insertionSort(sortArr_2, count);
    printArr(sortArr_2, count);

    int sortArr_3[ARR_SIZE];
    memcpy(sortArr_3, sortArr, sizeof(int) * ARR_SIZE);
    printf("quiuck sort:\t");
    quick_sort(sortArr_3, 0, count - 1);
    printArr(sortArr_3, count);

    int sortArr_4[ARR_SIZE];
    memcpy(sortArr_4, sortArr, sizeof(int) * ARR_SIZE);
    printf("merge sort:\t");
    merge_sort(sortArr_4, 0, count - 1);
    printArr(sortArr_4, count);

    int sortArr_5[ARR_SIZE];
    memcpy(sortArr_5, sortArr, sizeof(int) * ARR_SIZE);
    printf("heap sort:\t");
    heap_sort(sortArr_5, count);
    printArr(sortArr_5, count);

    return 0;
}

// original array: 3 2 4 1 9 8 
// insertion sort: 1 2 3 4 8 9 
// quiuck sort:    1 2 3 4 8 9 
// merge sort:     1 2 3 4 8 9 
// heap sort:      1 2 3 4 8 9

• 장점
  • 시간 복잡도가 좋은 편입니다.
  • 힙 정렬이 가장 유용한 경우는 자료 전체를 정렬하는 것이 아니라 가장 큰 값 몇개만 필요할 때 입니다.
• 힙 트리의 전체 높이가 거의 logN(완전 이진 트리이므로)이므로 하나의 요소를 힙에 삽입하거나 삭제할 때 힙을 재정비하는 시간이 logN만큼 소요 됩니다.
• 요소의 개수가 N개이므로 전체적으로 O(NlogN)의 시간이 걸립니다.

총 정리

저희는 이제까지 Insertion sort(삽입 정렬), quck sort(퀵 정렬), merge sort(합병 정렬), heap sort(힙 정렬)에 대해 알아보았습니다. 이제까지 본 것 처럼 어느 한 상황에서 모두 다 뛰어 난 정렬 알고리즘은 존재하지 않습니다. 

 

• 단순(구현 간단)하지만 비효율적인 방법
  • 삽입정렬, 선택 정렬, 버블 정렬
• 복잡하지만 효율적인 방법
  • 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬