アルゴリズム講座―選択ソート法

選択ソート法とは、

選択ソート (selection sort) は、ソートのアルゴリズムの一つ。
配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをおこなうこと。
最悪計算時間がO(n^2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　―Wikipedia『選択ソート』

要するに、

1. ソートする変数のうち最大(最小)のものを見つける
2. 最大(最小)の変数と最後(最初)の変数を交換
3. 残りの変数についてもこれを繰り返す

でソートを実現します。大きい数は後ろに来るから、その中で一番のものを後ろに持っていき続けたら並ぶというわけです。

例えば、a[5]={5,8,1,4,7}とします。このとき、

• まず{5,8,1,4,7}で最大の8と、一番後ろの7を交換して{5,7,1,4,8}とします。
• 次に、最後に持っていった8以外の数で最大の7と、後ろから2つめの4を交換して{5,4,1,7,8}とします。
• また次に、残りの3つから最大の5と、一番後ろの1を交換して{1,4,5,7,8}とします。

これで終了です(実際は最後の2つについても判定をしますが)。

では、実装してみてください。