prog*sig

映像でイメージを


重いものは右(下)に行って、一ループごとに右側からソート済みとなり固定される。
2回目の見れば分かるけど、軽いものがどんどん上がってるように見えるからバブルソート。
簡単らしいけどとっても効率は悪い。

1. 交換対象を選ぶのは右側から始める(デクリメントになってるのはそういうこと)
2. 軽いものが左に行くので、j < j-1だったら交換する。
3. 後はこれを繰り返す

正直プログラムにするとあんまり分かりやすくない。++ --が混じって分かりづらい。
もっと分かりやすい書き方が欲しい。

var arr = [3, 2, 8, 7, 4, 6, 1, 0, 5, 9];
function bubbleSort(ary){
    for(var i=0;i<ary.length-1;i++){
        for(var j=ary.length-1;j>i;j--){
            if(ary[j] < ary[j-1]){
                    var t = ary[j];
                    ary[j] = ary[j-1];
                    ary[j-1] = t;
            }         
        }      
    }
    console.log(ary);
}
bubbleSort(arr)

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


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

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;
  }
}

何かアルゴリズムの必要性を感じたので書いてみる。