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

先頭へ戻る

この章の概要

この章の概要です。


単純ソート

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

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

単純ソートは、整列対象のデータを先頭から1つと、それ以降の部分にあるデータ1つとを比較して、順序関係が逆になっていたら交換を行います(交換のアルゴリズムについては、【その他】第1章を参照)。これを、対象のデータ列の末尾に行き着くまで繰り返せば、整列が完了します。

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

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

これを昇順にソートします。

まず、先頭の要素 array[0] と、その次の要素 array[1] とが比較対象となります。それぞれ、7 と 2 ですから、昇順になっていないので、両者を交換します。その結果、

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

という状態になります。次は、array[0] はそのままで、対象だけを後続にずらします。よって、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つ先へ進めて、右側の方はその1つ後ろに戻します。つまり、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)
{
    size_t i, j;

    for(i = 0; i < size - 1; ++i){
        for(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)
{
    size_t i;

    for(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マクロを使っています。関数化されたものを使うと、関数呼び出しのコストが余分に掛かる可能性があることに注意して下さい。詳細は、【その他】第1章を参照して下さい。

性能

単純ソートのプログラムを見ると分かりますが、2重のループがあります。このループによって、配列全体を走査していますが、これは配列の要素数が増加すれば、それに伴ってループ回数も増加することを意味しています。ループが二重になっているため、配列の要素数が 2倍になったら、ループ回数も 2倍になるということではなく、ループ回数はもっと大きくなります。

具体的に計算量で表せば、O(n2) となります(計算量については、【導入】第1章参照)。これは性能としては、かなり悪いと言えます。そのため、性能が重要な場面では、単純ソートを利用すべきではありません。

実際、どのくらいのデータ量があると、どの程度の性能になるのかは実測してみる必要があります。ここで、実測例を挙げますが、これはコンピュータの性能によって大きく左右されるものですから、以下の結果をそのまま受け取るのではなく、データ量と実行時間との関係性を確認して下さい。

#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];
    int i;

    for(i = 0; i < SIZE_OF_ARRAY(array); ++i){
        array[i] = 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)
{
    size_t i, j;

    for(i = 0; i < size - 1; ++i){
        for(j = i + 1; j < size; ++j){
            if(array[i] > array[j]){
                SWAP(int, array[i], array[j]);
            }
        }
    }
}

実行結果:

simple_sort: 0.265000 seconds

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

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

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

このように理解できれば、この環境で 100万個のデータを単純ソートでソートすることは、ほとんど実用に耐えない結果になるであろうことが分かると思います。

まとめ

単純ソートの計算量は 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 に保存 Twitter でツイート Twitter をフォロー
Facebook でシェア Google+ で共有 LINE で送る rss1.0 取得ボタン RSS
管理者情報 プライバシーポリシー