timakin.log

╭( ・ㅂ・)و ̑̑

文系が学ぶコンピューターサイエンス╭( ・ㅂ・)و ̑̑:第6回【単純挿入ソート】

単純挿入ソートとは?

左(あるいは右)端からソート済みの区間がどんどん広がっていくというイメージでとらえる。
ソート済みの値より小さいものがあったら、それを挿入するために、
その値より大きい挿入済みの配列を1個ずつずらすやり方。


  // 単純挿入ソート。最悪計算量O(n^2)。ループ回数から考えるとまあわかる。
  insersionSort: function(data) {
    // 最初から最後までソート完了になるまで繰り返す
    var tmp, i;
    for (var sorted = 0; sorted < data.length - 1; sorted++) {
      // ソート完了している領域の直後の値を取り出す。
      insert = data[sorted+1];
      // ソート済みの中で、挿入できる場所があるかを調べる。
      for (i = 0; i <= sorted; i++) {
        if (data[i] > insert) {
          break; //ずれている部分を記憶しつつ、サーチを止める。
        }
      }
      // ずれていた箇所まで、1個ずつ要素をずらしていく。
      // 最終的にずれていた部分、1つの要素で比べようとすると止まる。
      while(i <= sorted + 1) {
        tmp = data[i];
        data[i] = insert;
        insert = tmp;
        i++;
      }
    }
    return data;
  }