読者です 読者をやめる 読者になる 読者になる

timakin.log

╭( ・ㅂ・)و ̑̑

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

コームソートとは?

f:id:u_tis:20150219220109p:plain

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