基本選択法(選択ソート、selection sort)

前に、基本交換法(隣接交換法・BubbleSort)についてで、BubbleSortのアルゴリズムを書きました。

このアルゴリズムは、基本情報技術者のテキストに乗っていて、読んだだけだとわからないと思い、実際ソースを組んだところから始まりました。



で、他にもまだ、ソートのアルゴリズムがあって、今回は、基本選択法(selection sort)を書きたいと思います。

下のような乱数が与えられたとき、降順か昇順で並び変えを行います。

昇順降順

では、実際のアルゴリズムを見ていきたいと思います。

昇順の場合

js_selectArray = new Array(); var k; for(var i=0;i<=js_selectArray.length-2;i++){   k = i;   for(var j=i+1; j<=js_selectArray.length-1;j++){     if(js_selectArray[k] > js_selectArray[j]){       k = j;     }   }   js_selectdummy = js_selectArray[i];   js_selectArray[i] = js_selectArray[k];   js_selectArray[k] = js_selectdummy;   js_selectdummy = ""; }

降順の場合

js_selectArray = new Array(); var k; for(var i=0;i<=js_selectArray.length-2;i++){   k = i;   for(var j=i+1; j>=js_selectArray.length-1;j++){     if(js_selectArray[k] > js_selectArray[j]){       k = j;     }   }   js_selectdummy = js_selectArray[i];   js_selectArray[i] = js_selectArray[k];   js_selectArray[k] = js_selectdummy;   js_selectdummy = ""; }

というアルゴリズムで展開されています。

前回のBubble Sortとは違って、基本選択法は、

対象集合から最も小さい(または最も大きい)要素を順次取り出して、端に置いていくことで整列を行う方法

via:栢木先生の基本情報技術者教室：基本選択法

と書かれていました。

う～～～ん、頭の中で整理しながらソースを組まないとわけがわからなくなってきます。