導入
「データ構造とアルゴリズム」
- 配列とコレクション
- ソート
- サーチ
- 再帰
今回はその第2回目として
実際のプログラミングでは、
展開
ソートとは
ソートとは、
- 昇順:小さいものから大きなものへ
- 降順:大きなものから小さなものへ
この連載記事において、
代表的なソートアルゴリズム
ソートを行うアルゴリズムの例として次のものが挙げられます。
- 基本形
- 基本交換法:バブルソート
- 基本選択法:直接選択法
- 基本挿入法
- 応用形
- 改良交換法:クイックソート
- 改良選択法:ヒープソート
- 改良挿入法:シェルソート
ここに紹介する分類は
基本選択法
アルゴリズムが単純で理解しやすいことから、
基本選択法のアルゴリズムは次のとおりです。
- 基本選択法のアルゴリズム
- 要素数
n
の配列a
にランダムな整数データが代入されているものとする。 - 添字のために整数変数
i
を用意する。初期値を0
とする。 - 次の手順を
i
の値がn-2
の時まで繰り返す。a[i]
を最小値であるとする。整数変数s
にi
の値を代入する。a[i+1]
からa[n-1]
まで巡回してa[s]
と比較する。a[s]
より小さい要素があれば、その添字の値を整数変数 s
に代入する(巡回用のカウンタ変数は j
とする)。a[i]
とa[s]
の値を交換する。i
の値を1つ増やす。
- 要素数
実際に手を動かし、
基本選択法のsketch
基本選択法ののアルゴリズムをProcessingで組んだものが次のsketchです。ソートの様子を画面に描くために、
5つのデータをソートする場合、setup
メソッド内のframeRate(30)
をframeRate(60)
などとすると、
基本選択法の計算量
基本選択法のアルゴリズムでは、n
個ある場合、n-1
回の比較が行われ、n-1
個のデータが残ります。次のループではn-2
回の比較が行われ、n-2
個のデータが残ります。こうして、
こうして検索回数は、n
に応じた計算回数を表す関数です。
この式のオーダー、n
の変化に応じて急激に増加する形か、
これは計算量としては大きい部類です。実際にコンピュータを動かした場合に大変時間がかかるということです。
改良挿入法:シェルソート
次に、
- シェルソートのアルゴリズム
- 要素数
n
の配列a
にランダムな整数データが代入されているものとする。 - 整数変数
gap
を用意する。初期値はn/
とする。2 - 次の手順を
gap
の値が1
になるまで繰り返す。- 次の操作を
gap
回繰り返す。すなわち整数変数j
は初期値0
、終了値 gap-1
でインクリメントする。a[j]
,a[j+gap]
,a[j+2gap]
, ……を基本挿入法でソートする。++j
gap
を半分にする。
- 次の操作を
- 要素数
シンプルなことがよくわかります。このアルゴリズムを実装については演習の課題とします。
演習
演習1(難易度:easy)
ランダムな整数データを500個もつデータファイルを作成しましょう。データは最小値1、RandomData.
に保存しましょう。このsketchのファイル名はGenerateRandomData.
にしてください。
演習2(難易度:middle)
SelectionSort.
のコードを参考に、frameRate
を10
に変更しましょう。ファイル名はShellSort.
としてください。
演習3(難易度:middle)
基本交換法であるバブルソートのアルゴリズムを調べて、RandomData.
をソートするsketchを作成しましょう。ファイル名はBubbleSort.
としてください。
まとめ
- 専門家として知っておくべきアルゴリズムの例として、
ソートのアルゴリズムを学習しました。
学習の確認
それぞれの項目で、
- 基本選択法の仕組みが理解できましたか?
- 理解できた。気持ちよく納得した。
- 理解できた。しかし、
今ひとつスッキリしない。 - 理解できない。
- シェルソートの仕組みが理解できましたか?
- 理解できた。気持ちよく納得した。
- 理解できた。しかし、
今ひとつスッキリしない。 - 理解できない。
- バブルソートの仕組みが理解出来ましたか?
- 理解できた。気持ちよく納得した。
- 理解できた。しかし、
今ひとつスッキリしない。 - 理解できない。
参考文献
- 『改訂C言語によるはじめてのアルゴリズム入門』
(河西朝雄 著、 技術評論社) - アルゴリズムの入門書。入門者に取っては十分に辞書的な内容である。丁寧に解説された良書。
演習解答
GenerateRandomData.
pde - このコードで作成したデータファイル
RandomData.
はスケッチフォルダtxt GenerateRandomData
内にあります。他のsketchで利用する場合は、そのsketchのスケッチフォルダにコピーしてください。
- このコードで作成したデータファイル
ShellSort.
pde BubbleSort.
pde - 演習2と演習3のソートを実行した時、
描画された画面の美しさにはほれぼれすることでしょう。
- 演習2と演習3のソートを実行した時、