アルゴリズム講座―選択ソート法

「アルゴリズム講座―選択ソート法」の編集履歴（バックアップ）一覧に戻る

アルゴリズム講座―選択ソート法 - (2010/09/19 (日) 19:19:33) の編集履歴(バックアップ)

---

選択ソート法とは、

選択ソート (selection sort) は、ソートのアルゴリズムの一つ。
配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをおこなうこと。
最悪計算時間がO(n^2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　―Wikipedia『選択ソート』

要するに、

1. ソートする変数のうち最大(最小)のものを見つける
2. 最大(最小)の変数と最後(最初)の変数を交換
3. 残りの変数についてもこれを繰り返す

でソートを実現します。大きい数は後ろに来るから、その中で一番のものを後ろに持っていき続けたら並ぶというわけです。

例えば、a[5]={5,8,1,4,7}とします。このとき、

• まず{5,8,1,4,7}で最大の8と、一番後ろの7を交換して{5,7,1,4,8}とします。
• 次に、最後に持っていった8以外の数で最大の7と、後ろから2つめの4を交換して{5,4,1,7,8}とします。
• また次に、残りの3つから最大の5と、一番後ろの1を交換して{1,4,5,7,8}とします。

これで終了です(実際は最後の2つについても判定をしますが)。

ここでは、void型関数selection_sort(int a[],int n)の例を示します。

仕様
機能:渡されるアドレスを先頭とする配列変数を昇順に選択ソートする
引数:int a[]…ソートする配列変数の先頭アドレス
     int n  …ソートする配列変数の要素数
返値:なし

void selection_sort(int a[],int n){
	int temp,max,i,j;
	for(i=n-1;i>0;i--){
		max=0;
		for(j=1;j<=i;j++){
			if(a[max]<=a[j]) max=j;
		}
		temp=a[i];
		a[i]=a[max];
		a[max]=temp;
	}
}

次に実装例です。これに、前述の関数を付け加えて実行してみてください。

#include <stdio.h>
#define N_DATA 10

int main(void)
{
	int data[N_DATA],i;
	printf("%d個の整数を入力してください。\n",N_DATA);
	for(i=0;i<N_DATA;i++) scanf("%d", &data[i]);
	select_sort(data,N_DATA);
	for(i=0;i<N_DATA;i++) printf("%d ",data[i]);
	
	return 0;
}