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

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

この章の概要

この章の概要です。


単純ソート

まずは、もっとも単純と思われる整列アルゴリズムから取り上げてみます。その名も、単純ソートです。

単純ソートという名前が、性能の低いいくつかの整列アルゴリズム群のことを指して使われることもあります。

単純ソートは、先頭の要素の値と、それより後ろにある各要素の値を1つ1つ比較して、順序関係が望む結果の逆になっているものを見つけたら、それらの要素の位置を交換します。最後の要素まで調べ終えたら、先頭から2つ目の要素を基準に変えて、それより後ろにある各要素の比較を行います。これを繰り返せば、最終的に整列済みのデータ列が得られるという方法です。

たとえば、対象のデータ列が次のような配列だとします。

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

これを昇順になるようにソートします。

まず、先頭の要素 array[0] と、その次の要素 array[1] の値を比較します。それぞれ、7 と 2 です。昇順になっていないので両者の位置を交換します。その結果は次のようになります。

{2, 7, 4, 5, 1, 6}

次は、比較相手だけを後ろにずらして、array[0] と array[2] を比較します。それぞれの値は 2 と 4 です。これは昇順になっているので、交換せずに続行します。

次は、array[0] と array[3] です。それぞれ、2 と 5 で昇順になっているので、交換しません。

その次は、array[0] と array[4] です。それぞれ、2 と 1 で昇順になっていないので、交換します。次のようになります。

{1, 7, 4, 5, 2, 6}

次は、array[0] と array[5] です。それぞれ、1 と 6 なので交換しません。

これで、比較相手が配列の末尾に達しました。ここまできたら、今まで固定していた側を1つ先へ進めます。つまり、array[1] が基準となり、比較相手はその直後にあたる array[2] とします。

以降は同じことの繰り返しです。

array[1] と array[2] を比較します。それぞれ、7 と 4 なので交換します。

{1, 4, 7, 5, 2, 6}

次は、array[1] と array[3] です。それぞれ、4 と 5 なので交換しません。

次は、array[1] と array[4] です。それぞれ、4 と 2 なので交換します。

{1, 2, 7, 5, 4, 6}

次は、array[1] と array[5] です。それぞれ、2 と 6 なので交換しません。

末尾まで達しました。比較の基準は array[2] に移動し、比較相手は array[3] に移ります。それぞれ、7 と 5 なので交換します。

{1, 2, 5, 7, 4, 6}

次は、array[2] と array[4] です。それぞれ、5 と 4 なので交換します。

{1, 2, 4, 7, 5, 6}

次は、array[2] と array[5] です。それぞれ、4 と 6 なので交換しません。

末尾に達したので、次は array[3] と array[4] です。それぞれ、7 と 5 なので交換します。

{1, 2, 4, 5, 7, 6}

次は、array[3] と array[5] です。それぞれ、5 と 6 なので交換しません。

末尾に達したので、次は array[4] と array[5] です。それぞれ、7 と 6 なので交換します。

{1, 2, 4, 5, 6, 7}

末尾に達しました。これまでのルールからすれば、次は array[5] と array[6] ですが、array[6] はないので、この段階で整列処理を終了とします。

最終的な結果を見ると、昇順にソートできていることが分かります。


プログラム例

それでは、冒頭で確認した実行過程を踏まえて、単純ソートのプログラムを書いてみましょう。

#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; }

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

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

    print_array( array, SIZE_OF_ARRAY(array) );
    simple_sort( array, SIZE_OF_ARRAY(array) );
    print_array( array, SIZE_OF_ARRAY(array) );

    return 0;
}

/*
    単純ソート (昇順)
*/
void simple_sort(int* array, size_t size)
{
    for( size_t i = 0; i < size - 1; ++i ){
        for( size_t j = i + 1; j < size; ++j ){
            if( array[i] > array[j] ){
                SWAP(int, array[i], array[j]);
            }
        }
    }
}

/*
    配列の要素を出力
*/
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 4 5 1 6
1 2 4 5 6 7

単純ソートをしているのは、simple_sort関数の中です。

要素の交換に SWAPマクロを使っています。

単純ソートに限らず、整列アルゴリズムの多くは、2つの要素の値の大小関係を比較して「交換」を行うことを繰り返して実現されます。そのため、(それほど難しいわけではありませんが)、交換を行う方法は前提知識として理解しておく必要があります。交換のアルゴリズムについては、【その他】第1章を参照してください。


simple_sort関数には、二重のループがあります。この章の冒頭で丁寧に確認した動作と照らし合わせてみてください。

外側の for文が比較の基準となる側の添字を制御しています(変数 i)。内側の for文は比較相手の側の添字を制御しています(変数 j)。

比較基準の側は先頭から始まるので、変数 i は 0 で開始されます。比較相手の側は、その直後から始まるので、変数 j は i + 1 で開始されます。

2つの要素の値の比較を行い(for文の内側にある if文)、大小関係が逆転していたら、交換を行っています。

その後は、比較基準の方は固定したまま、比較相手の方を後続へずらすのですから、変数 i は変わらず、変数 j だけが +1 されなければなりません。for文が二重になっており、内側の for文の中でループしており、変数 i はインクリメントされず、変数 j だけがインクリメントされるので、想定通りです。

比較相手が末尾に達したら、比較基準を次へ進めて、比較相手をその直後にリセットします。「比較相手が末尾に達した」というのは、内側の for文から抜けたときです。すぐに、外側の for文の次の周回が始まり、変数 i は +1 されます(次の位置へ進みました)。そして、再び内側の for文が始まり、変数j は i + 1 で初期化されます(比較基準の直後の位置)。

性能

単純ソートには2重のループがあります。

ループはそれぞれ、配列の各要素を順次参照するようになっています。正確にいえばいずれのループも、配列のすべての要素を参照するのではありません。外側のループは末尾を見ていませんし、内側のループは手前に近い要素はみなくなっていきます。

それでも、大まかにいって、配列の要素数に近い回数のループを行っていると考えると、配列の要素数が増えたとき、ループ回数がどれだけ増えるかを想像できます。たとえば、配列の要素数が 2倍になったとしたら、ループ回数はどうなるでしょう。

ループは二重なので、要素数が 2倍になったとき、ループ回数は 2乗になります。前述したとおり、正確には配列全体を参照するループではないので、実際にはもう少し少ないですが、2倍では済まないということがポイントです。

これは、計算量で表現すると、O(n2)ということです。

O(n2) という計算量は、整列アルゴリズムとしてはかなり悪いといえます(【導入】第1章参照)。性能が重要な場面では、単純ソートを利用すべきではありません。

計算量はあくまで理論であって、実際に何秒かかるとか、何分かかるとか、という話ではありません。実際の処理時間はコンピュータの性能によっても大きく左右されるので、処理時間を知りたければ実測してみる以外に手段はありません。

しかし、計算量が O(n2) だということは、データ量が 2倍になったら、処理時間は恐らく 22 つまり 4倍程度になるであろうということは分かります。

実測するサンプルプログラムを挙げます。

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

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

static void simple_sort(int* array, size_t size);

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

    for( size_t i = 0; i < SIZE_OF_ARRAY(array); ++i ){
        array[i] = (int)(ARRAY_SIZE - i);
    }


    PPP_CHECK_PERFORM_BEGIN(1);
    simple_sort( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("simple_sort");

    return 0;
}

/*
    単純ソート (昇順)
*/
void simple_sort(int* array, size_t size)
{
    for( size_t i = 0; i < size - 1; ++i ){
        for( size_t j = i + 1; j < size; ++j ){
            if( array[i] > array[j] ){
                SWAP(int, array[i], array[j]);
            }
        }
    }
}

実行結果:

simple_sort: 0.265000 seconds

ARRAY_SIZEマクロの置換後の値を変更すれば、データ数を変更できます。

上の実行結果は、1万個の要素を持つ配列の場合で、0.265秒でした。これを 10倍の 10万個に増やして実行すると、21.59秒掛かりました。おおよそですが、実行結果は 100倍になっています。

これが、O(n2) という計算量が意味するところで、データ量が 2倍になれば、時間は 22 になる、データ量が 10倍になれば、時間は 102、つまり 100倍になるということです。

このように理解すれば、この環境で 100万個のデータを単純ソートでソートすることは、ほとんど実用に耐えない結果になるであろうことが分かると思います。さらに 100倍になるのですから、約2000秒(およそ 33分)ほど掛かると思われます。

まとめ

単純ソートの計算量は O(n2) で、これは遅いアルゴリズムだと言えます。また、安定なソートではありません

単純ソートの長所は、プログラムが簡単であることに尽きます。性能をまったく必要としていない場面でソート処理が必要なときに、手軽に実装できます。

ただし、わずかな改良によって、選択ソート(第2章)という別のアルゴリズムに置き換えることが可能なので、そちらに置き換えた方がいいかもしれません。


練習問題

問題① 降順にソートする単純ソートを作成してください。

問題② あなたの環境で、1000万個のデータを単純ソートでソートするとしたら、どれだけの時間が掛かりますか?


解答ページはこちら

参考リンク


更新履歴

’2018/2/22 要素数を意味している「サイズ」について、「要素数」に表記を改めた。

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

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

’2012/6/23 コードライブラリのパス変更に伴い、リンクを修正。

’2012/5/5 新規作成。



前の章へ (第0章 はじめに)

次の章へ (第2章 選択ソート)

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

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポストフォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る