C言語: 2007年1月アーカイブ
挿入ソート、シェルソートと来まして今回は選択ソート(セレクションソート)を紹介いたします。
選択ソートはとても単純な考え方のソートです。
まず、データの中から最も小さな値を見つけ出してそれを抜き出す。
次に残った中から最も小さな値を見つけ出してそれを抜き出す。
その繰り返しを最後の一つになるまで続けます。
非常に分かりやすいですが、比較回数が多いため、実際にほとんど使われることはないようです。
データが「８５４２６３７１」のときの数値の変化例を以下に書いてみます。
・一番小さい数値を見つけて一番左に持ってくる。「(１)８５４２６３７」
・残った中で一番小さい数値を見つけて残った中の一番左に持ってくる。「１(２)８５４６３７」
・残った中で一番小さい数値を見つけて残った中の一番左に持ってくる。「１２(３)８５４６７」
・残った中で一番小さい数値を見つけて残った中の一番左に持ってくる。「１２３(４)８５６７」
・残った中で一番小さい数値を見つけて残った中の一番左に持ってくる。「１２３４(５)８６７」
・残った中で一番小さい数値を見つけて残った中の一番左に持ってくる。「１２３４５(６)８７」
・残った中で一番小さい数値を見つけて残った中の一番左に持ってくる。「１２３４５６(７)８」
以下、C言語で書いた選択ソートのプログラムです。
ソートを行う関数部分のみです。
/* 選択ソート関数ここから */
/* data[]:データ格納配列 num:配列要素数 */
void sort(int data[],int num){
int i,j,n,temp;
for(i=0;i<num-1;i++){
n=i;
for(j=i+1;j<num;j++)if(data[j]<data[n])n=j;
/*データの入れ替え*/
temp=data[i];
data[i]=data[n];
data[n]=temp;
}
}