ソート

ページトップへ　一つ上へ

ポイント


バブルソート、シェルソート



さてさて、今回は講座らしくアルゴリズムの勉強をしましょう。
アルゴリズムを学ぶ基本的な事項としてソートという物があります。
ソートというのはデータ列をある規則に並べ替える事を言う。
例えば、

・1,4,21,30…　昇順
・30,21,4,1…　降順

というような感じです。
このソートの方法により、処理時間が大きく違ってきます。
データの並び方によっても違いが出てくるので一概には言えませんが。

そこで今回は二つのソート法について紹介し、
そのプログラムを書いてみます。
それではまずバブルソートから。

バブルソートとは次のデータの方が後のデータよりも小さければ、（昇順の場合）
二つのデータを入れ替えし、それを順々に繰り返す方法です。

ではこのプログラムを見てみましょう。 
function b_sort

%
%　バブルソートのプログラム
%
%

n=10;					% データの個数

a=zeros(n,1);				% 変数aを初期化

for i = 1 : n				% 変数aにランダムデータの格納
    a(i)=floor(rand(1)*n*100);
end

fprintf('ソート前\n');			% ソート前データの表示	
print_display(a);

for i = 1 : n				% ソート処理
    for j = n :-1: i+1
        if a(j) < a(j-1)
            b=a(j);
            a(j)=a(j-1);
            a(j-1)=b;
        end
    end
end

fprintf('\nソート後\n');			% ソート後データの表示
print_display(a);

さて、バブルソートのプログラムはこんな感じになります。
一つ気になる部分がありますね。

print_display(a)
これは、たくさんデータが格納されている配列データを表示させる為に
僕が作った関数みたいな奴です。
別にこんなのを作らなくても数行で書けるのですが、
今回はこのデータ表示がいくつも出てくるので、
このような関数っぽいのを作ってみました。
以下が、print_display関数です。 
function print_display(a)

%
%　配列を持つデータの表示
%
%

data_size=length(a);

for i = 1 : data_size
    fprintf('%d ',a(i));
end

では、先ほどのバブルソートのプログラムを実行しましょう。
実行した結果は以下のようになります。

ソート前
670 485 382 563 489 155 651 726 3 909 
ソート後
3 155 382 485 489 563 651 670 726 909

ランダム関数を使っていますので、
実行するたびに結果は違います。
でもソート後はきちんと小さい順に並んでいるのがわかると思います。

それでは次にシェルソートについて説明します。
シェルソートとは、データの数列をいくつかのとびのある部分数列に分け
部分数列ごとにａiがどこに入るか調べてそこに挿入します。
部分数列を大雑把にソートし、部分数列を数列に収束させる事で、
ソートが完了するようになっています。
文章で見ると凄く難しい事をしているように思えます。
それではシェルソートのプログラムを見てみましょう。 
function s_sort

%
%　シェルソートのプログラム
%
%

n=10;					% データの個数

a=zeros(n,1);				% 変数aを初期化

for i = 1 : n				% 変数aにランダムデータを格納
    a(i)=floor(rand(1)*n*100);
end

fprintf('ソート前\n');			% ソート前データの表示
print_display(a);

gap=n/2;					% gapの初期化
while gap > 0				% ソート処理
    for i = 1 : gap
        for j = i+gap : gap : n
            for k = j-gap : -gap : i
                if a(k) > a (k+gap)
                    b=a(k);
                    a(k)=a(k+gap);
                    a(k+gap)=b;
                else
                    break;
                end
            end
        end
    end
    gap=floor(gap/2);
end

fprintf('\nソート後\n');			% ソート後データの表示
print_display(a);

多重ループが出来て、難しい事になっていますね。
しかし、核になる部分はバブルソートと大差ないと思います。
前処理みたいなのが難しいだけですので。
ではこれを実行した時の実行結果は

ソート前
128 208 955 772 700 50 225 91 885 607 
ソート後
50 91 128 208 225 607 700 772 885 955

ちゃんとソート出来ていますね。

それでは最後に、肝心の処理時間の比較をしてみましょう。
MATLABでは最初からsort関数というものが用意されてます。
高速化にとことんこだわっているMATLABの関数もいっしょに比較してみましょう。
下に表にしてまとめます。

ソート法データ数
１０		データ数
５０		データ数
１００		データ数
１０００		データ数
１００００
バブルソート0.010.050.19118.5572020
シェルソート0.010.030.051.07216.494
sort関数0.010.010.010.040.441
単位（秒）

上の表を見ればわかると思いますが、データ数が多くなるほど差は大きいです。
この表を参考にして、ソートプログラムを行う時に考えて下さい。
データ数が１０個ぐらいならどちらでも良いし（むしろバブルソートの方が簡単）
１００万個もあるようなプログラムではもっと最適化しなくてはいけないと言えます。
結論を言えば、sort関数を使うのが一番早いと思います。
しかし、ソートのアルゴリズムがわからないでsort関数を使ってしまうと、
Ｃ言語に移行する時に少々困る事があるので、
参考程度に知っておいて下さい。