お疲れ様です。サンチョです！
今回は「選択ソート」について触れてみます。
今回の記事を読んで得られるものは以下の通りです。
（１）選択ソートのイメージ
（２）プログラムに落とし込む際の思考の流れ
選択ソートとは
配列の中から要素を１つ選択して、それをほかの要素の値と比較し、最小値、または最大値を見つけだして入れ替えていくソート処理のことです。
選択ソートのイメージ
ソート前の情報が [ 4 ][ 1 ][ 3 ][ 5 ][ 2 ] だったしてイメージを説明します。
今回はこれを降順（大きい順）で並べ替える例を紹介します。
1つ目の要素を最大値と仮定する
まず最大値の格納場所となる変数を用意して、1つ目の要素を退避します。
1つ目の要素を最大値と仮定するということです。
最大値と2つ目以降の要素を順番に比較して最大値をみつける
続いて、最大値と残りの要素（ [ 1 ][ 3 ][ 5 ][ 2 ] ）を順番に比較していきます。
すると [ 4 ] より大きな値である [ 5 ] が見つかるで、最大値を [ 5 ] に変更します。
そのあとも引き続き、最大値と残りの要素を比較していきます。
もし残りの要素の中に [ 5 ] より大きな値が見つかれば、再び最大値を変更します。
これを繰り返すと最大値が判明します。
1つ目の要素と最大値の要素を入れ替える
次に1つ目の要素と最大値を入れ替えます。
これによって1つ目の要素を最大値とすることができました。
次は2つ目の要素を2つ目の最大値と仮定して、同様の処理を繰り返していけば、最終的に降順に並び替えることができます。
実際にやってみよう
まずは考えを整理する
まずはイメージを元にどういう処理が必要か整理しましょう。
（１）配列の要素を１つずつ取り出さないといけないので、ループ処理が必要。
（２）選択された最大値を、配列の各要素と比較するには、もうひとつループ処理が必要。
（３）比較するということは、条件分岐（if文）が必要。
（４）配列のデータを入れ替える処理が必要。
続いて、上記の処理を実行するために必要な変数を整理しましょう。
（１）int型の配列変数が必要。
（２）２つのループを回すために、２つのカウンタ変数が必要。
（３）最大値の要素番号を退避するための int型の変数が必要。
（４）データの入れ替えを行うために、値を退避するための int型の変数が必要。
整理した流れを元にプログラミングする
整理した流れを元に完成したのが以下のプログラムです。
ソート前とソート後の結果を比較しやすいように、オマケで表示用の関数も作ってみました。
#include<stdio.h>
void printArray(int data[]);
int main() {
int data[5] = { 4, 1, 3, 5, 2 }; // 配列
int outCnt, // 外側のループを回すためのカウンタ変数
inCnt; // 内側のループを回すためのカウンタ変数
int temp; // 配列の値を交換するための退避用変数
int max; // 最大値が格納されている要素番号を記憶するための変数
printf("ソート前\n");
printArray(data);
for (outCnt = 0; outCnt < 5; outCnt++) {
/* 最初は data[outCnt] を最大値と仮定して考えるので、
max には ourCnt の値をセットする。 */
max = outCnt;
/* inCnt には outCnt + 1 をセットする。 */
for (inCnt = outCnt + 1; inCnt < 5; inCnt++) {
/* 最大値が格納されている要素番号を見つける。 */
if (data[max] < data[inCnt]) {
max = inCnt;
}
}
/* このif文は無くても動く */
if (outCnt != max) {
temp = data[outCnt];
data[outCnt] = data[max];
data[max] = temp;
}
}
printf("ソート後\n");
printArray(data);
}
/* 配列の内容を表示するための関数 */
void printArray(int data[]) {
int cnt;
for (cnt = 0; cnt < 5; cnt++) {
printf("data[%d]：%d\n", cnt, data[cnt]);
}
}初心者がもっとも躓きやすいポイントは、２つ目のループ処理の回し方です。
for (inCnt = outCnt + 1; inCnt < 5; inCnt++) 初心者は「 inCnt = outCnt + 1 」を思いつけないことが多いです。
2つ目のループを0から回し始めると、以下のイメージのような判定が発生してしまうので、うまくソートできずに詰みます。
こうならないように、以下の点を覚えておいてください。
・現在位置から左側は既に順序が確定している。
・右側だけで比較すれば良い。
まとめ
今回は「選択ソート」のイメージとプログラムに落とし込む際の思考の流れを紹介しました。
選択ソートは
・最大値を探し出して、1つ目の要素と入れ替える。
・1つ目の最大値が判明したら、次の最大値を探し出して2つ目の要素と入れ替える。
・上記の流れを配列の数だけ繰り返すとソートが完成する。
プログラムにおいては
・二重ループが必要になる。
・変数が持つべきは「最大値」そのものではなく、「最大値が格納されている要素番号」。
・要素番号を元に入れ替えを行う。
選択ソートは、授業や新人研修などでもよく出てきますので、覚えておいて損は無いと思います。
特に新人研修でこれに躓くと「進捗が遅い＝できない子」の評価になってしまうので、イメージを事前に頭に叩き込んで、サクッと突破しちゃいましょう！
では、本日はここまでにしたいと思います。
お疲れ様でした！
コメント