prog*sig

この映像でイメージを持つ


やり方的にはこれ
単純挿入ソート

1,2,3,4というように昇順にするのが目標
ソート済み | これからソートする値
という感じに分けて、ソート済み+1個目が次にソートしたい(挿入したい)値となる。
挿入したい値をinsertとすると

1. insertとソート済みの値を比較して、insertより大きい値があったらストップ
2. ストップした場所にinsertを挿入する(挿入を交換によって表す)
3. 挿入したらbreakして、次に挿入したい値をinsertに入れて繰り返していく。

var arr = [3, 2, 8, 7, 4, 6, 1, 0, 5, 9];
function InsertSort(ary){
    for(var i=0;i<ary.length-1;i++){
        var insert = ary[i+1];//挿入する値
        for(var j=0;j<=i;j++){// i(ソート済み)まで挿入する場所を探す
            if(insert < ary[j]){// 挿入値の方が小さい
            // 挿入値を入れて、そこから一個右にずらす作業
            while(j<=i+1){
                var tmp = ary[j];
                ary[j] = insert;
                insert = tmp;
                ++j;
            }
            break;
            }        
        }      
    }
    console.log(ary);//  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
}
InsertSort(arr)

下みたいにも書けるとかっこいいな。
一回挿入すればそれ以上ソート済みの値を見ていく必要がない。

function insertionSort(data) {
  var n = data.length, i, temp, j;
  for(i = 1; i < n; ++i) {
    temp = data[i];
    for(j = i; j > 0 && data[j-1] > temp; --j) {
      data[j] = data[j-1];
    }
    data[j] = temp;
  }
}