先頭へ戻る

ヒープソート 解答ページ | Programming Place Plus アルゴリズムとデータ構造編【整列アルゴリズム】 第8章

Programming Place Plus トップページアルゴリズムとデータ構造編

先頭へ戻る

問題①

問題① 「プログラム例」のサンプルプログラムを、降順にソートした結果を得るように修正してください。


ヒープの実装が、根が最小値になっているので、根から順番に取り出すと昇順になります。ここではヒープの実装は変えられないので、根から取り出した値を配列の末尾の方へ入れるように変えます。

#include <stdio.h>
#include "heap.h"

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

static void heap_sort(int* array, size_t size);
static void print_array(const int* array, size_t size);

int main(void)
{
    int array[] = {7, 2, 9, 6, 4, 3, 8, 1, 5};

    print_array( array, SIZE_OF_ARRAY(array) );
    heap_sort( array, SIZE_OF_ARRAY(array) );
    print_array( array, SIZE_OF_ARRAY(array) );

    return 0;
}

/*
    ヒープソート (昇順)
*/
void heap_sort(int* array, size_t size)
{
    Heap heap = heap_create( size );

    // データをヒープへ格納
    for( size_t i = 0; i < size; ++i ){
        heap_insert( heap, array[i] );
    }

    // データを根から順に取り出す
    for( size_t i = 0; i < size; ++i ){
        heap_remove_root( heap, &array[size - i - 1] );
    }

    heap_delete( heap );
}

/*
    配列の要素を出力
*/
void print_array(const int* array, size_t size)
{
    for( size_t i = 0; i < size; ++i ){
        printf( "%d ", array[i] );
    }
    printf( "\n" );
}

実行結果:

7 2 9 6 4 3 8 1 5
9 8 7 6 5 4 3 2 1


参考リンク


更新履歴

’2015/12/27 SIZE_OF_ARRAYマクロの定義を修正。

’2015/2/21 サンプルプログラムで、ファイルスコープでよい関数に static を付加。

’2013/2/9 新規作成。



第8章のメインページへ

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー