今回は「選択法」とか「セレクションソート」と呼ばれる方法で、並べ替えを行ってみます。
最初に考え方を説明しますので、次のアニメーションを良く見てください。
※３周目以降は割愛しています。
前回の方法と違って、比較する２つの要素が隣り合っていません。
最初の１周は０番目の値とそれ以降の値をすべて比較しています。
２周目は１番目の値とそれ以降の値を比較しています。
３周目は２番目の値とそれ以降の値、４周目は３番目の値とそれ以降を・・・
最後の９周目は８番目の値とそれ以降の値を比較します。
それぞれ、基準となる要素（１周目は０番目）の値と比較する値の大小を調べ、基準となる要素の値の方が大きい場合に入れ換えが行われます。
次は図を１枚ずつ見ていきます。
初期状態です。
まずは基準となる要素を０番目として、基準の右隣（１番目）と比較します。
基準はそのままで、比較対象を右へずらし比較します。
基準となる値の方が大きい場合、入れ換えを行います。
さらに比較対象を右にずらし比較します。
最後に９番目の要素と比較して１周目が完了です。
２周目は基準を１番目にずらし、比較は基準の右隣から開始します。
最後に９番目の要素と比較して２周目が完了です。
３週目は２番目の要素を基準として、基準の右隣から９番目まで比較します。
４週目は３番目の要素を基準として、基準の右隣から９番目まで比較します。
５週目は４番目の要素を基準として、基準の右隣から９番目まで比較します。
６週目は５番目の要素を基準として、基準の右隣から９番目まで比較します。
７週目は６番目の要素を基準として、基準の右隣から９番目まで比較します。
８週目は７番目の要素を基準として、基準の右隣から９番目まで比較します。
９週目は８番目の要素を基準として、基準の右隣から９番目まで比較します。
この時点で一番大きな数が右端（９番目）に入っていますので、これで終わりです。
今回のソートのポイントは以下の通りです。
| 周目 | 基準 | 比較対象 |
|---|---|---|
| １周目 | ０番目 | １〜９番目 |
| ２周目 | １番目 | ２〜９番目 |
| ３周目 | ２番目 | ３〜９番目 |
| ４周目 | ３番目 | ４〜９番目 |
| ５周目 | ４番目 | ５〜９番目 |
| ６周目 | ５番目 | ６〜９番目 |
| ７周目 | ６番目 | ７〜９番目 |
| ８周目 | ７番目 | ８〜９番目 |
| ９周目 | ８番目 | ９番目 |
１．基準は０から１ずつ増えています。
２．比較対象は基準＋１から９まで変化します。
３．基準の方が大きければ入れ換えを行います。
ポイント１と２は二重ループで作成できそうです。
では、↓のプログラムを元に作成してみましょう。
<sample program 069-00>
#include <stdio.h>
#define COUNT 10
int main(void)
{
int data[COUNT] = { 23, 45, 9, 67, 98, 55, 32, 76, 12, 88 };
int i;
int j;
int work;
/* ここにプログラムを追加 */
for (i = 0; i < COUNT; i++) {
printf("data[%d] = %d\n", i, data[i]);
}
return 0;
}
|
<実行結果>
data[0] = 9 data[1] = 12 data[2] = 23 data[3] = 32 data[4] = 45 data[5] = 55 data[6] = 67 data[7] = 76 data[8] = 88 data[9] = 98 続行するには何かキーを押してください・・・
解答例です。
<sample program 069-01>
#include <stdio.h>
#define COUNT 10
int main(void)
{
int data[COUNT] = { 23, 45, 9, 67, 98, 55, 32, 76, 12, 88 };
int i;
int j;
int work;
for (i = 0; i < COUNT - 1; i++) {
for (j = i + 1; j < COUNT; j++) {
if (data[i] > data[j]) {
work = data[i];
data[i] = data[j];
data[j] = work;
}
}
}
for (i = 0; i < COUNT; i++) {
printf("data[%d] = %d\n", i, data[i]);
}
return 0;
} |
<実行結果>
data[0] = 9 data[1] = 12 data[2] = 23 data[3] = 32 data[4] = 45 data[5] = 55 data[6] = 67 data[7] = 76 data[8] = 88 data[9] = 98 続行するには何かキーを押してください・・・
基準は０から８まで変化しますので、
for (i=0; i<COUNT-1; i++) {
}
|
↑のループで実現できます。
基準が１増える間に比較対象は基準＋１から９まで変化しますから、
for (i=0; i<COUNT-1; i++) {
for (j=i+1; j<COUNT; j++) {
}
}
|
内側に基準＋１から始まるループを入れれば完成です。
前回に引き続きソートのプログラムを作成しましたが、他にもソートの実現方法は沢山あります。
比較的考え方が簡単な２種類のソートを紹介しましたが、色々調べて他の方法も試してください。
ちなみに小さい順に並べ替えることを昇順ソート、大きい順だと降順ソートと言います。