13-4. セレクションソート
今週は元の流れにもどって基本アルゴリズムを続けます。
検索・置換ができたので今度はデータの並べ替え(ソート)をやってみます。
今から説明する選択ソートは並べ替えの方法として最も単純なものです。
単純なだけにプログラムもスマートで分かりやすいのですが、データ量が増えると処理負担が一気に増大するという欠点もあります。
◇いわゆる選択法
まずは、選択ソートがどういったものなのか説明します。
ソートしたい配列の先頭から最後尾まで探索し、最小値(または最大値)を検出します。これを先頭と交換し、２回目の探索は先頭から２番目の要素から出発します。
これを繰り返して最後まで到達するとソート終了です。
１．探索開始
■□□□□□□□□□□□☆□□□□□□□□□□□□
├→
２．最小値決定
□□□□□□□□□□□□★□□□□□□□□□□□■
↑ →｜
３．交換
☆□□□□□□□□□□□□□□□□□□□□□□□□
└───────────┘
４．二回目探索
☆■□□□□□□□□□□□□□□□□□□□□□□□
├─────────────────────→｜
こんな感じで最後まで続きます。
◇サンプルプログラム
前回の図をここに引用します。
１．探索開始
■□□□□□□□□□□□☆□□□□□□□□□□□□
├→
２．最小値決定
□□□□□□□□□□□□★□□□□□□□□□□□■
↑ →｜
３．交換
☆□□□□□□□□□□□□□□□□□□□□□□□□
└───────────┘
４．二回目探索
☆■□□□□□□□□□□□□□□□□□□□□□□□
├─────────────────────→｜
#include<stdio.h>
main()
{
int i,arr[]={4,6,2,8,3,1,5,0,9,7};
void selectsort_min(int n, int arr[]);
printf("初期状態 = ");
for(i = 0; i < 10; i++) printf("%d",arr[i]);
printf("\n");
selectsort_min(10,arr);
printf("並び替え = ");
for(i = 0; i < 10; i++) printf("%d",arr[i]);
printf("\n");
}
void selectsort_min(int n, int arr[])
{
int i,j,k,min;
for(i = 0; i < n-1 ; i++){
min = arr[i]; k = i;
for (j = i + 1; j < n; j++ ){
if(arr[j] < min){
min = arr[j];
k=j;
}
}
arr[k] = arr[i];
arr[i] = min;
}
}
/* 実行結果
初期状態 = 4628315097
並び替え = 0123456789
Press any key to continue
*/
この探索法ではデータ数をｎとすると、1/2*n(n-1) 回探索します。
つまりｎが増えればその２乗に比例して探索回数が増えるので大きなデータには不向きです。
セレクションソートのサンプルを解説します。
1:void selectsort_min(int n, int arr[])
2:{
3: int i,j,k,min;
4:
5: for(i = 0; i < n-1 ; i++){
6: min = arr[i]; k = i;
7: for (j = i + 1; j < n; j++ ){
8: if(arr[j] < min){
9: min = arr[j];
10: k=j;
11: }
12: }
13: arr[k] = arr[i];
14: arr[i] = min;
15: }
16:}
◇解説
1:void型selectsort_min関数、第一引数(整数型n)、第二引数(整数配列arr)
5: 計数iは、全体のサーチの最初の要素番号
6: まずサーチの最初の要素をminにセット、同時にiの値をkにセット
7: 計数jはサーチの現在地
8: サーチの途中でminの値より小さいものが見つかれば
9: minに要素をセットし
10: そのときのjをkにセットする。
13: ここでサーチの最初の要素arr[i]を、最小値arr[k]にセットし
14: arr[i]にminをセットする
インデント(空白)は実際のループ処理に合わせてあけています。
実際のソートでは数列ではなく、文字列を使うのが普通だと思います。
以後のソート関係は文字列ソートでやってみます。