バブルソート、シェルソート
さてさて、今回は講座らしくアルゴリズムの勉強をしましょう。
アルゴリズムを学ぶ基本的な事項としてソートという物があります。
ソートというのはデータ列をある規則に並べ替える事を言う。
例えば、
・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) |
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 |
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 |
ソート法 | データ数 10 | データ数 50 | データ数 100 | データ数 1000 | データ数 10000 |
---|---|---|---|---|---|
バブルソート | 0.01 | 0.05 | 0.191 | 18.557 | 2020 |
シェルソート | 0.01 | 0.03 | 0.05 | 1.072 | 16.494 |
sort関数 | 0.01 | 0.01 | 0.01 | 0.04 | 0.441 |