選択ソート(昇順)は「与えられた配列内から最小値要素を取り出し、次に残った要素群から最小要素を取り出す」という動作を繰り返し、要素を取り出した順に並べることで動作する整列アルゴリズムです。
1 》選択ソート図解
(昇順に並び替える)- 未ソート部から最小のキーを持つ要素を選択する
- 最小のキーを持つ要素を未ソート部の先頭要素と交換する
- この操作を(n - 1)回繰り返すと未ソート部がなくなり完了
具体例を次に示す
未ソート部左端に比較基準点を決定
比較基準点より右で比較基準点の値より小さな値を探索。見つけ次第交換
右端まで探索終了で1順目終了。このとき未ソート部最小値が未ソート部左端に入っている
以降、比較基準点を右に1つずらし同じ操作を繰り返す
(h.length - 1)回上記の操作を繰り返すとソート完了(上の例では4回)
特徴
- バブルソートに似ているが選択ソートのほうが高速なアルゴリズム
- 同一キーを持つ要素の順序がソート前後で維持されない
計算量
データ数をNとすると
合計の比較演算の回数は N(N - 1)/ 2
選択ソートのオーダーは O(N^2)
2 》選択ソートプログラム
配列の中身を昇順に並べ替える
【JavaScript】
//選択ソートを行う関数
function selectionSort(hairetu)
{
//値を交換するための変数
var temp;
//交換する配列の位置
for(var i=0;i < (hairetu.length-1);i++)
{
//iの位置より右を探索
for(var j=i+1;j < hairetu.length;j++)
{
if(hairetu[i] > hairetu[j])
{
temp = hairetu[i];
hairetu[i] = hairetu[j];
hairetu[j] = temp;
}
}
}
}
//ここから開始
var h=[6,3,8,4,5,1,2,9,7,0];
document.write("整列前:");
for(var i=0;i < h.length;i++)
{
document.write(h[i]+" ");
}
document.write("<br>");
//選択ソート
selectionSort(h);
document.write("整列後:");
for(var i=0;i < h.length; i++)
{
document.write(h[i]+" ");
}
【実行結果】
整列前:6 3 8 4 5 1 2 9 7 0
整列後:0 1 2 3 4 5 6 7 8 9
コメント
このブログにコメントするにはログインが必要です。
さんログアウト
この記事には許可ユーザしかコメントができません。