挿入ソートは今までのソートアルゴリズムよりも簡単と言うけれど、ソースコードは今までで一番長いものになってしまいました。
処理を全て関数化してみたという事もあるし、できるだけ関数依存しない書き方をしたという事もあるからかもしれませんが、とりあえずjavascript版が完成したので、掲載しておきます。
ソースコード
/**
* [ insertSort ] 基本関数
*/
function insertSort(numbers){
// 数値配列を最初から順番に評価していく
for(var i=1; i<numbers.length; i++){
// 確定数値リストを取得
var confirmLists = getConfirmLists(numbers , i);
// 対象外の数値リストを取得
var lastLists = getLastLists(numbers , i);
// 確定数値リストに挿入数値の挿入
var firstLists = setInsert(confirmLists , numbers[i]);
// リストの結合
numbers = setUnionLists(firstLists , lastLists);
}
return numbers;
}
/**
* 確定数値リストに対象数値が挿入される位置を取得する
* [Summery]
* 返り値の手前に挿入される
* 数値リストよりも指定数値の方が大きい場合はnullが返る->数値の後ろに追加
* @param : confirmLists | 確定数値リスト
* @param : targetNum | 対象数値
* @return : number or null | 挿入位置番号
*/
function getInsertPlace(confirmLists , targetNum){
var num = null;
for(var i=0; i<confirmLists.length; i++){
if(targetNum < confirmLists[i]){
num = i;
break;
}
}
return num;
}
/**
* 全体数値リストから確定数値リストを取得
* @param : numbers | 全体数値リスト
* @param : targetNum | 対象数値番号
* @return : array | 確定数値リスト
*/
function getConfirmLists(numbers , targetNum){
var arr = [];
for(var i=0; i<numbers.length; i++){
if(i == targetNum){
break;
}
arr.push(numbers[i]);
}
return arr;
}
/**
* 数値リストの挿入
* @param : confirmLists | 確定数値リスト
* @param : targetNum | 対象数値
* @return : array | 数値入れ替え後の全体数値リスト
*/
function setInsert(confirmLists , targetNum){
// 確定数値リストに対象数値が挿入される位置を取得する
var replaceNum = getInsertPlace(confirmLists , targetNum);
// 挿入操作
var arr = [];
for(var i=0; i<confirmLists.length; i++){
if(i == replaceNum){arr.push(targetNum)}
arr.push(confirmLists[i]);
}
// 挿入番号がnullの場合は入れ替えなし
if(replaceNum === null){
arr.push(targetNum)
}
return arr;
}
/**
* リストの結合
* @param : firstLists | 確定数値リスト
* @param : lastLists | 対象外数値リスト
* @return : array | 入れ替え後の全体数値リスト
*/
function setUnionLists(firstLists , lastLists){
var arr = [];
if(firstLists.length >0){
for(var i=0; i<firstLists.length; i++){
arr.push(firstLists[i]);
}
}
if(lastLists.length >0){
for(var i=0; i<lastLists.length; i++){
arr.push(lastLists[i]);
}
}
return arr;
}
/**
* 対象外の数値リストを取得
* @param : numbers
* @param : targetNum
* @return : array | 対象外リスト
*/
function getLastLists(numbers , targetNum){
var arr = [];
for(var i=targetNum+1; i<numbers.length; i++){
arr.push(numbers[i]);
}
return arr;
}
insertSort([10,2,12,7,16,8,13]);
解説
仕様書に近いようなコメントを付けておいたのでそれだけである程度理解してもらえると思いますが、とりあえず、トピックを書いておきます。
配列の結合
配列の結合は何気に言語によっては難しいものがあるので、要素分解して都度配列を新規作成しています。
少し処理が増えてもったいない感じですが、多言語対応を考えるとこの方がいいかも・・・という今回限りの判断です。
言語別の効率化はまた別の機会に行いたいと思います。
挿入処理
このアルゴリズムの核である「挿入」処理は、配列の挿入位置を取得して、その位置にはめ込む処理を別途で関数化しています。
その時に挿入される数値が一番大きい数値の場合は、配列の最後に追加される形になりますが、今回はそれをnullと判定してpush処理で行うようにしています。
どうしてもここがシンプルな書き方ができませんでした。
実行
プログラム全体をブラウザのコンソールに貼り付けてENTERを押すと関数がメモリ保存されます。
その後、最後の行の関数実行処理を同じくコンソールで実行すると、結果が得られます。
結果は以下の通り
insertSort([10,2,12,7,16,8,13]);
> [2, 7, 8, 10, 12, 13, 16]
関連リンク
いろいろなプログラム言語でアルゴリズム学習
