13-4. セレクションソート
今週は元の流れにもどって基本アルゴリズムを続けます。
検索・置換ができたので今度はデータの並べ替え(ソート)をやってみます。
今から説明する選択ソートは並べ替えの方法として最も単純なものです。
単純なだけにプログラムもスマートで分かりやすいのですが、データ量が増えると処理負担が一気に増大するという欠点もあります。
◇いわゆる選択法
まずは、選択ソートがどういったものなのか説明します。
ソートしたい配列の先頭から最後尾まで探索し、最小値(または最大値)を検出します。これを先頭と交換し、2回目の探索は先頭から2番目の要素から出発します。
これを繰り返して最後まで到達するとソート終了です。
1.探索開始
■□□□□□□□□□□□☆□□□□□□□□□□□□
├→
2.最小値決定
□□□□□□□□□□□□★□□□□□□□□□□□■
↑ →|
3.交換
☆□□□□□□□□□□□□□□□□□□□□□□□□
└───────────┘
4.二回目探索
☆■□□□□□□□□□□□□□□□□□□□□□□□
├─────────────────────→|
こんな感じで最後まで続きます。
◇サンプルプログラム
前回の図をここに引用します。
1.探索開始
■□□□□□□□□□□□☆□□□□□□□□□□□□
├→
2.最小値決定
□□□□□□□□□□□□★□□□□□□□□□□□■
↑ →|
3.交換
☆□□□□□□□□□□□□□□□□□□□□□□□□
└───────────┘
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 */
この探索法ではデータ数をnとすると、1/2*n(n-1) 回探索します。
つまりnが増えればその2乗に比例して探索回数が増えるので大きなデータには不向きです。
セレクションソートのサンプルを解説します。
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をセットする
インデント(空白)は実際のループ処理に合わせてあけています。
実際のソートでは数列ではなく、文字列を使うのが普通だと思います。
以後のソート関係は文字列ソートでやってみます。