先頭へ戻る

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

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

先頭へ戻る

この章の概要

この章の概要です。

関連する話題が、以下のページにあります。


ヒープソート

この章では、ヒープソートを取り上げます。

ヒープソートは、ヒープというデータ構造を利用したアルゴリズムです。ヒープについては、【データ構造】第9章で解説しているので、そちらを参照してください。

ヒープソートの理屈は、ヒープのことさえ理解していれば拍子抜けするほど簡単です。ソートしたいデータ列をヒープへすべて挿入し、あとは順次取り出すだけです。

ヒープは、最小値(または最大値)を持った要素から取り出されるように実装されるデータ構造なので、データを全部入れて、全部出せば、勝手にソートされるわけです。

そのため、ヒープのしくみさえ準備できれば終わったも同然です。

プログラム例

ヒープソートは、【データ構造】第9章で解説したヒープのコードをそのまま利用するだけで実現できます。

#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[i] );
    }

    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" );
}
// heap.c

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


// ヒープ
struct Heap_tag {
    int*      data;        // データ本体
    size_t    capacity;    // 最大容量
    size_t    first_empty; // 空になっている最初の位置
};

#define SWAP(type,a,b)          { type work = a; a = b; b = work; }

static void up_heap(Heap heap, size_t index);
static void down_root(Heap heap);
static void heap_print_node(const Heap heap, size_t index, int level);


/*
    ヒープを作る
*/
Heap heap_create(size_t capacity)
{
    struct Heap_tag* heap = malloc( sizeof(struct Heap_tag) );
    heap->data = malloc( sizeof(int) * (capacity + 1) );  // 添字を 1 から始めるため、+ 1 して確保
    heap->capacity = capacity;
    heap->first_empty = 1;  // 0番目は使わない

    return heap;
}

/*
    ヒープを削除する
*/
void heap_delete(Heap heap)
{
    if( heap != NULL ){
        free( heap->data );
        free( heap );
    }
}

/*
    ヒープに要素を追加する
*/
bool heap_insert(Heap heap, int value)
{
    // 容量が一杯でないか確認
    if( heap->capacity < heap->first_empty ){
        return false;
    }


    // まず、末尾に追加する
    size_t index = heap->first_empty;
    heap->data[index] = value;
    heap->first_empty += 1;

    // 適切な位置まで浮かび上がらせる
    up_heap(heap, index);

    return true;
}

/*
    ヒープから根を取り除く
*/
bool heap_remove_root(Heap heap, int* value)
{
    // ヒープが空でないか確認する
    if( heap_getsize(heap) <= 0 ){
        return false;
    }


    *value = heap->data[1];

    // ヒープの最後にある要素を、先頭に移動する
    heap->first_empty -= 1;
    heap->data[1] = heap->data[heap->first_empty];

    // 先頭に移動させた要素を、正しい位置に沈める
    down_root(heap);

    return true;
}

/*
    ヒープから要素を探す
*/
bool heap_search(const Heap heap, int value)
{
    for( int i = 1; i < heap->first_empty; ++i ){
        if( heap->data[i] == value ){
            return true;
        }
    }

    return false;
}

/*
    ヒープに格納されている要素数を返す
*/
size_t heap_getsize(const Heap heap)
{
    return heap->first_empty - 1;
}

/*
    ヒープの内容を出力する
*/
void heap_print(const Heap heap)
{
    if( heap == NULL || heap_getsize(heap) <= 0 ){
        return;
    }

    heap_print_node( heap, 1, 0 );
}

/*
    ヒープの指定要素を適切な位置まで浮かび上がらせる
*/
void up_heap(Heap heap, size_t index)
{
    while( index > 1 ){  // 根に到達したら終わり
        size_t parent = index / 2;

        if( heap->data[parent] > heap->data[index] ){
            // 親との大小関係が逆なら入れ替える
            SWAP( int, heap->data[parent], heap->data[index] );

            // さらに親をたどる
            index = parent;
        }
        else{
            // 大小関係が正常だったら終わり
            break;
        }
    }
}

/*
    根を適切な位置まで沈める
*/
void down_root(Heap heap)
{
    int index = 1;  // 根から開始

    while( index * 2 <= heap->first_empty ){
        int child = index * 2;  // 左の子の位置

        // 2つの子があるなら、小さい方を使う
        // 右の子の添字は、左の子の添字 + 1 である
        if( child + 1 < heap->first_empty ){
            if( heap->data[child] > heap->data[child + 1] ){
                child = child + 1;
            }
        }

        // 子との大小関係が逆なら、入れ替える
        if( heap->data[child] < heap->data[index] ){
            SWAP( int, heap->data[child], heap->data[index] );
            index = child;
        }
        else {
            break;
        }
    }
}

/*
    ヒープの内容を出力する
*/
void heap_print_node(const Heap heap, size_t index, int level)
{
    for( int i = 1; i < level; ++i ){
        printf( "    " );
    }
    if( level > 0 ){
        printf( "+---" );
    }
    printf( "%d\n", heap->data[index] );


    // 左の子
    index *= 2;
    if( index < heap->first_empty ){
        heap_print_node( heap, index, level + 1 );
    }

    // 右の子
    index += 1;
    if( index < heap->first_empty ){
        heap_print_node( heap, index, level + 1 );
    }
}
// heap.h

#ifndef HEAP_TREE_H_INCLUDED
#define HEAP_TREE_H_INCLUDED

#include <stdbool.h>

// ヒープ型
typedef struct Heap_tag* Heap;


/*
    ヒープを作る

    引数:
        capacity:   ヒープの最大容量。

    戻り値:
        作成されたヒープ。
        使い終わったら、heap_delete関数に渡して削除する。
*/
Heap heap_create(size_t capacity);

/*
    ヒープを削除する

    引数:
        heap:   ヒープ
*/
void heap_delete(Heap heap);

/*
    ヒープに要素を挿入する

    引数:
        heap:   ヒープへのポインタ
        value:  挿入する要素の値
    戻り値:
        成功したら true、失敗したら false を返す。
*/
bool heap_insert(Heap heap, int value);

/*
    ヒープから根を取り除く

    引数:
        heap:   ヒープへのポインタ
        value:  取り除かれた要素を受け取るメモリアドレス
    戻り値:
        成功したら true、失敗したら false を返す。
*/
bool heap_remove_root(Heap heap, int* value);

/*
    ヒープから要素を探す

    引数:
        heap:   ヒープ
        value:  探し出す要素の値
    戻り値:
        要素が見つかれば true、見付からなければ false を返す。
*/
bool heap_search(const Heap heap, int value);

/*
    ヒープに格納されている要素数を返す

    引数:
        heap:   ヒープ
    戻り値:
        格納されている要素の個数。
*/
size_t heap_getsize(const Heap heap);

/*
    ヒープの内容を出力する

    引数:
        heap:   ヒープ
*/
void heap_print(const Heap heap);


#endif

実行結果:

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

ソート対象の配列の要素をヒープへ格納した後、根から順番に取り出すだけです。ヒープ自体の実装ができていれば、非常に簡単です。

しかし、このプログラムには少し問題があります。それは、ソート対象の配列以外に、ヒープを実装するためのメモリ領域を取ってしまうことです。ヒープの実装も配列ですから(【データ構造】第9章参照)、単純にいって、メモリを2倍使ってしまうということです。

次の項で、この問題の解決を試みます。


メモリを浪費しない実装

先ほどのサンプルプログラムでは、ソート対象のデータ列の2倍程度のメモリを使ってしまう問題があります。この問題を解決してみます。

問題は、heap_create関数の中で確保している配列です。

/*
    ヒープを作る
*/
Heap heap_create(size_t capacity)
{
    struct Heap_tag* heap = malloc( sizeof(struct Heap_tag) );
    heap->data = malloc( sizeof(int) * (capacity + 1) );  // 添字を 1 から始めるため、+ 1 して確保
    heap->capacity = capacity;
    heap->first_empty = 1;  // 0番目は使わない

    return heap;
}

この配列 (heap->data) は、あくまで作業用です。ソート対象の要素がいったんここにすべて集められてヒープを構築し、その後、すべて取り出されます。

もし、“いったんここにすべて集め” ずに、ソート対象の配列の中だけを使ってヒープを構築できれば、メモリ使用量は一気に半分になります。


ソート対象の配列は main.c にあるので、とりあえずの方針として、heap.c と heap.h にあるコードのいくらかを main.c に移し替えます。

まず、ヒープをあらわす構造体をもってきます。

// ヒープ
struct Heap_tag {
    int*      data;        // データ本体
    size_t    capacity;    // 最大容量
    size_t    first_empty; // 空になっている最初の位置
};
typedef struct Heap_tag Heap;

ソート対象の配列自体をヒープにしたいのですから、data メンバはソート対象の配列を指し示すようにします。

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

Heap heap;
heap.data = array;
heap.capacity = SIZE_OF_ARRAY(array);
heap.first_empty = SIZE_OF_ARRAY(array);

heap_create関数のときは、指定された要素数よりも 1つ余分に確保していました。これは、添字の計算を楽にするために、0 のところを使わないようにするためです。しかし、ソート対象配列の 0番目の要素には、すでにデータが入ってしまっていることが多いでしょう。0番目も普通に要素が入っているものとして扱うことにします。

heap.c の処理を使った実装のときは、ヒープに要素を1つ1つ挿入していましたが、今回はその過程がなくなります。すでにデータが入っている配列を指すので、ヒープは一杯になっているとみなします。first_empty メンバの値は、最後の要素のさらに後ろ、つまり、空きはありません。


さて、この時点ではヒープの要件をまったく満たしていません。ヒープは、根が最小値、または最大値となるように構成しなければなりません。根を最小値とした場合、ある節の値は必ずその親の値以上です。根を最大値とした場合、ある節の値は必ずその親の値以下です。

heap.c では、heap_insert関数の中で適切な位置を見つける処理を行っていますが、今回は、要素を挿入することがないので、どこか別のタイミングで、同じような処理を書く必要があります。

タイミングについては簡単です。さっさとヒープとして正しい状態にしなければなりませんから、さきほど、Heap構造体を初期化した直後に書きます。

問題は方法です。heap_insert関数では、挿入する要素をいったん末尾に置き、その後、適切な位置を探していました。イメージとしては、木構造の一番深いところに置いてから、適切な位置まで浮かび上がらせるということです。しかし今回は、末尾の位置にはじめから要素が置かれていますから、この方法をマネすることはできません。

そこで考え方を反対にして、要素を適切な位置まで沈めるようにします。このような操作は heap.c の down_root関数にすでにあります。down_root関数は、ヒープから要素を取り除くときに使われています。ヒープでは取り除く要素がつねに根にありますから、取り除いたあと、根の部分が空くことになります。そこで、末尾にある要素をその空いた位置に移動させ、その要素を適切な位置まで沈めるという操作を行っていました。

これをそのまま利用すれば、根の要素を適切な位置へ移動させることができます。

down_root(&heap);

しかし、この操作を行っても、根の要素にとって本当に適切な位置が、やはり根の位置だった、ということはあり得ますから、必ずしも根の要素が移動するわけではありません。そのため、この処理を何度繰り返しても、一向に要素が動かず、ヒープにならないという事態が起こり得ます(かなりの高確率でそうなるでしょう)。

そこで、根の位置を変えながら、down_root関数を繰り返し呼ぶようにします。根の位置を変えるというのは変な話なようですが、木構造は再帰的なかたちをしていることを思い出しましょう。つまり、部分部分を1つの木(部分木)とみなせば、根はいくつもあります。

具体的にどうすればいいかというと、まず、一番深く、一番右側にある根を探して、その位置に対して down_root関数の処理を適用します。その後は、左側へ移動、なければ上(親)の段へ移動、というように動きながらそのつど、down_root関数の処理を適用します。これを、木構造全体の根に到達するまで繰り返します。

「一番深く、一番右側にある根」の位置は、ヒープの性質を利用すれば簡単にわかります。ヒープには次の性質があるのでした(【データ構造】第9章)。

連番値とは、全体の根を 1 としたときの添字のことです。今回は、添字を 0 から始めなければならないので、次のように読み替えます。

末尾の要素の位置は分かっているので(heap.first_empty - 1)、その親が「一番深く、一番右側にある根」です。よって、((heap.first_empty - 1) - 1) / 2 で求められます。少し整理すると、(heap.first_empty - 2) / 2 です。

down_root関数の引数には、根とみなす要素の位置を指定できませんから、引数を都合のいいように変えます。位置が指定できるのなら、もはや root と呼ぶのもおかしいので、関数名も down_heap に変えます。

/*
    ヒープの指定要素を適切な位置まで沈める

    引数:
        heap:   ヒープへのポインタ
        root:   根の位置
        end:    末尾の位置
*/
void down_heap(Heap* heap, int root, int end);

そのうえで、次のように繰り返せば、ヒープを構築できます。「左側へ移動、なければ上の段へ移動」という操作は、変数 root をデクリメントするだけで実現できます。

for( int root = ((int)(heap.first_empty) - 2) / 2; root >= 0; --root) {
    down_heap( &heap, root, heap.first_empty - 1 );
}

heap.first_empty が size_t型(符号無し整数型)なので、int型へのキャストをしておかないと「-2」した結果が巨大な正の数になってしまい失敗します。ヒープの章で使ったコードが size_t型になっているので、それに合わせたコードですが、heap.first_empty を int型にするのでも構いません。

この処理を終えた時点で、ヒープとして正しい並びになっています。概念図であらわすと、以下のようになります。

ヒープソートの途中経過

根に一番小さい値があり、子は親以上の値を持つという要件は満たされています。しかし、配列をソートするという、本来の目的が達成されたわけではありません。この時点で、配列は次のようになっており、ソートできていません。

1 2 3 5 4 9 8 6 7

ヒープソートの基本手順は、この章の最初に書いたとおり「ソートしたいデータ列をヒープへすべて挿入し、あとは順次取り出す」です。ここまでに前半部分は終わりました。あとは後半部分を実行すれば、ソート済みの配列が得られます。

「順次取り出す」のところで取り出される値は(根のことなので)、最小値(あるいは最大値)です。しかし、対象の配列がソートしたい配列そのものなので、要素を実際に取り出してしまうわけにはいきません。そこで、取り出す代わりに、配列の末尾にある要素と交換すればいいでしょう。

しかし、単に交換するだけだと、根の位置に最小値(あるいは最大値)ではない値が置かれてしまいます。そこでここでも、down_heap関数を呼びます。交換によって根の位置にやってきた要素を、down_heap の処理にかけてやれば、適切な位置へ沈んでいき、ヒープの状態が保たれます。

そうしたらまた、根と末尾(本当の末尾は先ほど定まったので、今度は1つ手前)を交換し、down_heap を呼び、また根と末尾(の2つ手前)を交換し・・・と繰り返せば、ソートを実現できます。

void sort_heap(Heap* heap)
{
    int end = (int)heap->first_empty - 1;

    while( end >= 1 ){
        SWAP(int, heap->data[0], heap->data[end]);
        end--;
        down_heap( heap, 0, end );
    }
}

ここまでの話をすべて踏まえて、ヒープソートを行うプログラムは次のようになります。

#include <stdio.h>

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))
#define SWAP(type,a,b)          { type work = a; a = b; b = work; }

// ヒープ
struct Heap_tag {
    int*      data;        // データ本体
    size_t    capacity;    // 最大容量
    size_t    first_empty; // 空になっている最初の位置
};
typedef struct Heap_tag Heap;

static void heap_sort(int* array, size_t size);
static void down_heap(Heap* heap, size_t root, size_t end);
static void sort_heap(Heap* heap);
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.data = array;
    heap.capacity = size;
    heap.first_empty = size;

    // ヒープを再構成
    for( int root = ((int)(heap.first_empty) - 2) / 2; root >= 0; --root) {
        down_heap( &heap, root, heap.first_empty - 1 );
    }

    // ヒープ内をソートする
    sort_heap( &heap );
}

/*
    ヒープの指定要素を適切な位置まで沈める
*/
void down_heap(Heap* heap, size_t root, size_t end)
{
    while( root * 2 + 1 <= end ){
        size_t child = root * 2 + 1;  // 左の子の位置

        // 2つの子があるなら、小さい方を使う
        // 右の子の添字は、左の子の添字 + 1 である
        if( child + 1 <= end ){
            if( heap->data[child] > heap->data[child + 1] ){
                child = child + 1;
            }
        }

        // 子との大小関係が逆なら、入れ替える
        if( heap->data[child] < heap->data[root] ){
            SWAP( int, heap->data[child], heap->data[root] );
            root = child;
        }
        else {
            break;
        }
    }
}

/*
    ヒープ内をソートする
*/
void sort_heap(Heap* heap)
{
    int end = (int)heap->first_empty - 1;

    while( end >= 1 ){
        SWAP(int, heap->data[0], heap->data[end]);
        end--;
        down_heap( heap, 0, end );
    }
}

/*
    配列の要素を出力
*/
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

これで、メモリを浪費せずにヒープソートを実現できました。

ただ、ソートが昇順でなくて、降順で行われています。もちろんそれでいいならいいのですが、やはり昇順にしたいことが多いので、どうにかしなければなりません。

これはヒープを構築する際の大小関係の判定を逆にすれば修正できます。具体的には、down_heap関数内の2つの if文の条件式を書き換えます(★のコメントが入っているところ)。

/*
    ヒープの指定要素を適切な位置まで沈める
*/
void down_heap(Heap* heap, size_t root, size_t end)
{
    while( root * 2 <= end ){
        size_t child = root * 2 + 1;  // 左の子の位置

        // 2つの子があるなら、大きい方を使う
        // 右の子の添字は、左の子の添字 + 1 である
        if( child + 1 <= end ){
            if( heap->data[child] < heap->data[child + 1] ){  // ★
                child = child + 1;
            }
        }

        // 子との大小関係が逆なら、入れ替える
        if( heap->data[child] > heap->data[root] ){  // ★
            SWAP( int, heap->data[child], heap->data[root] );
            root = child;
        }
        else {
            break;
        }
    }
}


性能

性能を確認しておきましょう。この章で取り上げた2つのヒープソートの実装を比較します。

heap.c と heap.h はこの章の最初のサンプルのところで掲載したとおりです。また、同時に使うと名前が被る箇所があるので、メモリ節約版のほうの名前に「2」を付加しています。

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

#define ARRAY_SIZE              100000
#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))
#define SWAP(type,a,b)          { type work = a; a = b; b = work; }

// ヒープ
struct Heap2_tag {
    int*      data;        // データ本体
    size_t    capacity;    // 最大容量
    size_t    first_empty; // 空になっている最初の位置
};
typedef struct Heap2_tag Heap2;

static void init_array(int* array, size_t size);
static void heap_sort(int* array, size_t size);
static void heap_sort2(int* array, size_t size);
static void down_heap(Heap2* heap, size_t root, size_t end);
static void sort_heap(Heap2* heap);

int main(void)
{
    static int array[ARRAY_SIZE];


    init_array( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_BEGIN(1);
    heap_sort( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("heap_sort");

    init_array( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_BEGIN(1);
    heap_sort2( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("heap_sort2");

    return 0;
}

/*
    配列を初期化
*/
void init_array(int* array, size_t size)
{
    srand(0);

    for( size_t i = 0; i < size; ++i ){
        array[i] = rand() % size;
    }
}

/*
    ヒープソート (昇順)
*/
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[i] );
    }

    heap_delete( heap );
}

/*
    ヒープソート (昇順)
*/
void heap_sort2(int* array, size_t size)
{
    Heap2 heap;
    heap.data = array;
    heap.capacity = size;
    heap.first_empty = size;

    // ヒープを再構成
    for( int root = ((int)(heap.first_empty) - 2) / 2; root >= 0; --root) {
        down_heap( &heap, root, heap.first_empty - 1 );
    }

    // ヒープ内をソートする
    sort_heap( &heap );
}

/*
    ヒープの指定要素を適切な位置まで沈める
*/
void down_heap(Heap2* heap, size_t root, size_t end)
{
    while( root * 2 + 1 <= end ){
        size_t child = root * 2 + 1;  // 左の子の位置

        // 2つの子があるなら、小さい方を使う
        // 右の子の添字は、左の子の添字 + 1 である
        if( child + 1 <= end ){
            if( heap->data[child] > heap->data[child + 1] ){
                child = child + 1;
            }
        }

        // 子との大小関係が逆なら、入れ替える
        if( heap->data[child] < heap->data[root] ){
            SWAP( int, heap->data[child], heap->data[root] );
            root = child;
        }
        else {
            break;
        }
    }
}

/*
    ヒープ内をソートする
*/
void sort_heap(Heap2* heap)
{
    int end = (int)heap->first_empty - 1;

    while( end >= 1 ){
        SWAP(int, heap->data[0], heap->data[end]);
        end--;
        down_heap( heap, 0, end );
    }
}

要素数を変えて比較した結果は次のとおりでした。

データ件数 ヒープソ ート1 ヒープソート2
10000個 0 .004秒 0 .003秒
100000個 0 .046秒 0 .033秒
1000000個 0 .484秒 0 .373秒
10000000個 6 .586秒 5 .622秒

ヒープソートの計算量は O(n log n) ですが、これと同等のクイックソート、マージソートの実測値も挙げておきます。クイックソートは、基準値に3要素のメジアンを使った非再帰版(第6章練習問題② の実装)、マージソートは、(ボトムアップ方式の実装)を使っています。

データ件数 クイック ソート マージソート
10000個 0 .002秒 0 .003秒
100000個 0 .019秒 0 .021秒
1000000個 0 .171秒 0 .244秒
10000000個 1 .773秒 2 .528秒

クイックソートが一番速く、次にマージソート、ヒープソートと続くことが分かります。

まとめ

ヒープソートの計算量は O(n log n)です。これは、クイックソート(第6章)やマージソート(第7章)と同じですが、マージソートの2倍程度遅いといわれており、この3つのアルゴリズムの中では一番低速です。

ヒープソートは、マージソートと同様、データの並びに影響を受けず、つねに O(n log n)の計算量を保てる利点があります。クイックソートはデータの並びに影響を受けて、性能が上下します。

ヒープソートは、この章で挙げた2つ目の実装のように工夫すれば、[作業用のメモリを必要としません。]この点はマージソートより優れています。

一方で、ヒープソートは安定なソートではないことに注意が必要です。

【上級】また、ヒープソートは並列化できないという弱点があります。


3つの高速なソートアルゴリズムが出揃ったので、長所と短所をまとめておくと次のようになります。

したがって、安定である必要がないのなら、クイックソートを優先すればいいです。安定でなければならないのなら、マージソートやヒープソートが候補に挙がります。連結リストのソートのような特殊な場合にはマージソートを使います。


練習問題

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


解答ページはこちら

参考リンク


更新履歴

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

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

’2013/2/9 新規作成。



前の章へ (第7章 マージソート)

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

Programming Place Plus のトップページへ



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