文系が学ぶコンピューターサイエンス╭( ･ㅂ･)و ̑̑：第４回【コームソート】

コームソートとは？

今回は特に書くことがない。。。
コームとは櫛という意味。
バブルソートで少し間隔をとって比較して、徐々に近づけてくソート。
バブルソートと違って、すべての値の交換じゃなく、間隔を調整していくことで回数を減らすという原理。
計算量はO(nLogn)。

コームソートの実装

  combSort: function(data) {
      var N = data.length;
      var gap = N;
    while((gap > 1) || flag) {
      // 収縮率（間隔調整の度合い）は1.3。
      var gap = gap*10/13;
      if (gap < 1) { gap = 1 };
      var flag = 0;
      for (var i = 0; i < N - gap; i++) {
        if (data[i] > data[i+gap]) {
          this.swap(data, i, i+gap);
          flag = 1;
        }
      }
    }
    return data;
  }