ヒープソートをC言語で作ってみた

いろいろお勉強したのでまとめます

ヒープソートって？

ヒープソートは、ヒープ化を使って配列の最小（最大）値を求めて配列の先っぽにくっつける
その最小（最大）値を配列から無視して、もう一度ヒープ化

これを繰り返すと、ソートが完了するよねっていうソート方法

ヒープ化って？

ヒープ化は配列を木構造に見立てて親が子よりも小さい（大きい）法則を守った木構造にすること
これによって配列の中の最小（最大）を早く求めることができる

ソースコード

heap.c

void swap(int* i1, int* i2){
    int temp = *i1;
    *i1 = *i2;
    *i2 = temp;
}

void downheap(int* array, int len ,int target){
    int right, left, min = target;
    left = (target * 2) + 1;
    right = (target * 2) + 2;
    if(len > left){
        if(array[left] < array[min]){
            min = left;
        }
    }
    if(len > right){
        if(array[right] < array[min]){
            min = right;
        }
    }
    if(min != target){
        swap(&array[min], &array[target]);
        downheap(array, len, min);
    }
}

void heap(int* array, int len){
    for(int i = (len / 2) - 1; i >= 0; i--){
        downheap(array, len, i);
    }
}

void heap_sort(int* array, int len){
    for(int length = len, i = 0; length > 0; length--, i++){
        heap(&array[i], length);
    }
}

ヒープソートの本体はheap_sort()
ヒープ化はheap()が担っている

実行してみる

heap.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
void array_print(int* array, int len){
    for(int i = 0; i < len; i++){
        printf(" %d,", array[i]);
    }
    printf("\n");
}

#define ARRAY_NUM 15

int main(int argc, char const *argv[])
{
    
    int buf[ARRAY_NUM];
    srand((unsigned int)time(NULL)); 
    for(unsigned int i = 0; i < ARRAY_NUM; i++){
        buf[i] = rand() % 200;
    }
    array_print(buf, ARRAY_NUM);
    heap_sort(buf, ARRAY_NUM);
    array_print(buf, ARRAY_NUM);

    return 0;
}

乱数を使ってぐちゃぐちゃの配列を作って並び替えてみる

実行結果

./heap2.bin
 172, 137, 40, 128, 97, 73, 180, 155, 132, 101, 96, 87, 93, 72, 171,
 40, 72, 73, 87, 93, 96, 97, 101, 128, 132, 137, 155, 171, 172, 180,

ヨシ！！！！

まとめ

とりあえずヒープ化を理解するのが難しかった
最初は配列を木構造にするとかもあんまり理解できなかったし
そこからヒープ化する動きも、最初は理解できなかった
先人たちのコードを参考にしなければ絶対に理解できなかった気がする

クイックソートがあるから実用環境じゃあんまり使えないけど
ヒープ化の参考にでもしてください