このサイトでは、ここまで「クイックソート」と「マージソート」の解説を行なってきました。
クイックソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）
マージソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）
このページでは、これらと同様のソートアルゴリズムである「選択ソート」について解説します。
まず、選択ソートがどのようなアルゴリズムであるかについて解説し、続いて選択ソートの実装プログラム例を紹介していきたいと思います。
プログラム例は「再帰処理あり（再帰呼び出しあり）」と「再帰処理なし（再帰呼び出しなし）」の２種類を紹介しますので、再帰処理ありのプログラムと再帰処理なしのプログラムの違いについても学んでいただけると思います！
Contents
選択ソートとは
選択ソートとは前述の通り、ソートアルゴリズムの１つです。
選択ソートの特徴
選択ソートには下記のような特徴があります。
- アルゴリズムが簡単！
- 使用メモリが少ない（配列一つ分でソートできる）
- 処理速度が遅い
アルゴリズムが簡単なので、ソートアルゴリズムを最初に学ぶには最適なアルゴリズムです。
処理速度は遅いですが、処理が単純でプログラミングしやすいため、速度がそこまで要求されないような場面では使用される機会も多いと思います。
スポンサーリンク
選択ソートの考え方
選択ソートは与えられたデータの集合に対し、下記の考え方でソートを行うアルゴリズムです。
- 集合の中で最小のデータを探索
- 見つけた最小のデータを、集合の先頭のデータと交換
- 先頭のデータを除いたデータの集合をソート
上記はデータを昇順に並べる時の考え方になります
降順に並べる際は「最小」を「最大」に、「先頭」を「末尾」に読み替えて考えてください
選択ソートの流れ
続いて選択ソートによってデータがソートされていく流れを解説していきたいと思います。
ソートは昇順に行うものとして解説していきます。降順にソートしたい場合は、大小関係を逆に読み取りながら解説を読んでいただければ良いと思います。
データの集合の中で最小のデータを探索
選択ソートでは、まずは集合の中で最小のデータを探索します。
最小のデータがどれであるかは、集合の中の全データを調べないと分からないので、データ数分の比較処理が必要になります。
スポンサーリンク
最小のデータを集合の先頭のデータと交換
続いて、その最小のデータを集合の先頭のデータと交換します。
この時点で、集合の先頭のデータは最小のデータとなります。つまり、集合の先頭のデータはすでにソート済みであると考えられます。
先頭のデータを除いたデータの集合をソート
集合の先頭のデータはすでにソート済みですので、もうこのデータをソートする必要はありません。
ですので、次はこの先頭のデータを除いた集合のデータのみに対してソートを行います。
このソートには選択ソートを用います。
つまり、先頭のデータを除いた集合を新たな集合と考え、その新たな集合の中から最小のデータを探索し、そのデータと新たな集合の先頭のデータを交換します。
これは、元々の集合で考えると、集合の中で２番目に小さいデータと、集合の先頭から２番目のデータを交換することになります。
これにより、元々のデータの集合で考えると、先頭のデータと先頭から２番目のデータがソート済みになります。
さらに、このソート済みのデータを除いたデータを再び新たな集合と考えて同様の処理を繰り返していきます。
これにより、集合の先頭側から順々にソートが完了し、ソートを行う対象となる集合のデータ数が減少されていきます。
最終的に集合のデータ数が１つになるまでこれを繰り返します。
ここまで、集合の中の最小のデータを集合から除外することを繰り返して、集合のデータ数を減らしてきました。したがって、最後に残ったデータは最大のデータとなります。
さらに、他のデータは既にソート済みですので、これにより元々の集合のデータ全てのソートが完了したことになります。つまり、集合のデータが１つになったらソート処理は完了です。
こんな感じで集合のデータが１つになるまで下記を繰り返してソートを行うのが選択ソートです。
- データの集合の中で最小のデータを探索
- 最小のデータを集合の先頭のデータと交換
- 先頭のデータを除いたデータの集合をソート
選択ソートのプログラム
最後に、ここまで解説してきた選択ソートをC言語で実装したサンプルプログラムを紹介しておきます。
ここでは再帰処理を行う場合と行わない場合のサンプルプログラムを紹介します。
スポンサーリンク
再帰処理なしの選択ソートサンプルプログラム
まずは再帰処理を行わない場合の選択ソートを行う関数のサンプルプログラムです。
/* 選択ソートを行う関数
* data[] : ソートを行うデータの集合
* (ソート後のデータの集合を格納)
* left : ソートを行う範囲の開始点
* right : ソートを行う範囲の終了点
*/
void selectionSort(int data[], int left, int right) {
int start;
int i;
int min;
int i_min;
int tmp;
/* データ数が１の場合はソート済みなのでソート終了 */
if (left == right) {
return;
}
/* ソート範囲（開始点）の初期化 */
start = left;
/* ソート範囲を狭めながらソート処理 */
for (start = left; start < right; start++) {
/* ひとまずソート範囲の先頭を最小値とみなす */
i_min = start;
min = data[i_min];
/* ソート範囲の中から最小値を探索 */
for (i = start; i <= right; i++) {
if (min > data[i]) {
/* 最小値とその値を持つインデックスを更新 */
min = data[i];
i_min = i;
}
}
/* ソート範囲の先頭と最小値を交換 */
tmp = data[start];
data[start] = data[i_min];
data[i_min] = tmp;
}
}ソートを行う範囲の先頭を start 変数で管理しています。
データの交換が終わったら for 文により start がインクリメントされますので、どんどんソートを行う範囲が狭まっていくことになります。
/* ソート範囲を狭めながらソート処理 */
for (start = left; start < right; start++) {ソートを行う範囲の先頭を表す start と末尾を表す right が同じ値になったら、ソートが未完了のデータが１つになったことになりますので処理を終了します。
再帰処理ありの選択ソートサンプルプログラム
次は再帰処理ありの選択ソートを行う関数のサンプルプログラムです（データ数が多すぎるとスタックが溢れてプログラムが異常終了する可能性があるので注意してください）。
/* 選択ソートを行う関数
* data[] : ソートを行うデータの集合
* (ソート後のデータの集合を格納)
* left : ソートを行う範囲の開始点
* right : ソートを行う範囲の終了点
*/
void selectionSort(int data[], int left, int right) {
int i;
int min;
int i_min;
int tmp;
/* データ数が１の場合はソート済みなのでソート終了 */
if (left == right) {
return;
}
/* ひとまずソート範囲の先頭を最小値とみなす */
i_min = left;
min = data[left];
/* ソート範囲の中から最小値を探索 */
for (i = left; i <= right; i++) {
if (min > data[i]) {
/* 最小値とその値を持つインデックスを更新 */
min = data[i];
i_min = i;
}
}
/* ソート範囲の終了点と最小値を交換 */
tmp = data[left];
data[left] = data[i_min];
data[i_min] = tmp;
/* ソート範囲を狭めて再度選択ソート */
selectionSort(data, left + 1, right);
}selectionSort 関数の中で selectionSort 関数を呼び出しています。
この時にソート範囲の先頭を表す left を +1 して呼び出すことで、どんどんソート範囲を狭めながらソート処理を行なっていくことになります。
/* ソート範囲を狭めて再度選択ソート */
selectionSort(data, left + 1, right);また、関数の先頭でデータ数が１つかを判断し、１つであれば即座にソート処理を終了するようにしています。
/* データ数が１の場合はソート済みなのでソート終了 */
if (left == right) {
return;
}まとめ
このページでは選択ソートについて解説しました。
選択ソートは下記の考え方でデータを並べ替えるソート方法になります。
- データの集合の中で最小のデータを探索
- 最小のデータを集合の先頭のデータと交換
- 先頭のデータを除いたデータの集合をソート
前述の通り、比較的処理内容が分かりやすいですので、アルゴリズム勉強の入門として最適のテーマだと思います。
今回プログラムで示したように、再帰処理なしの場合と再帰処理ありの場合のプログラムを考えることで再帰処理の復習も行えます。
是非一度はプログラミングしてみることをオススメします！
本サイトでは、選択ソート以外にも下記のソートについても解説しています。
- クイックソート
- マージソート
- 挿入ソート
下記リンク先でそれぞれについて解説していますので、他のソートアルゴリズムにも興味のある方は是非こちらも読んでみてください！
クイックソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）
マージソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）
挿入ソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）
