JavaScript 挿入ソート

挿入ソート(単純挿入方)

「データを抜き出して、正しい位置に挿入していく方法」
正しい位置に「挿入していく」ので「挿入ソート」と言われる。

イメージ
トランプで一枚ずつ配られるカードを、手持ちのカードに加えて順番に並べていく方法に似ている。

手順
1 配列の先頭(index0)を整列済みとして扱い、残りのカードを整列する基点になる。
2 残りのカードの先頭を取り出して変数「tmp」に入れる。変数に入れてから挿入する場所を探す。
3 整列済みのどこに置くか判定する。
4 「挿入する値」が小さければ、整列済みの値を後ろへずらしてスペースを空ける。
5 上記の処理を未整列の部分がなくなるまで繰り返す

ポイント
・「整列していない部分から、挿入する値を順番に１つずつ取り出す」繰り返し処理
・「取り出した値を、整列した部分のどこに挿入するのかを判断する」繰り返し処理
上記２つを行う

script.js

//未整列の配列データ
var a = [10,3,1,4,2];

//未整列の部分から値を１つずつ取り出すfor文
for(var i = 1; i<a.length; i++){
    //「挿入する値」を変数に一時保存する
    var tmp = a[i];

    //「整列済みの部分」のどこに挿入すれば良いか後ろから前に向かって順番に判断する
    for(var j = i-1; j>=0; j--){
        //「挿入する値」が小さい場合、調べた値を１つ後ろへずらす
        if(a[j]>tmp){
            a[j+1] = a[j];
        }else{
            //小さくなければ、ずらす処理を止める
            break;
        }
}
    //ずらす処理が終わったところに「挿入する値」を入れる
    a[j+1] = tmp;
}
//ソート後のデータを表示
console.log(a)