Ruby コームソート

コームソートとは

コムソート（英: comb sort）やコームソートや櫛（くし）ソートは、ソートのアルゴリズムの一つ。1980年に Włodzimierz Dobosiewicz が発表し^[2][1]、1991年に Stephen Lacey と Richard Box が再発見しコムソートと命名した。

バブルソートの改良版。内部ソートだが、安定ソートではない。実行速度は、ほぼO(n log n)になる。[wikipedia引用]

アルゴリズム

挿入ソートをシェルソートに改良したときと同様の改良を施す。適当な間隔で整列後、間隔を少しずつ狭めて整列していく。

1. 総数 n を 1.3 で割り、小数点以下を切り捨てた数を間隔 h とする。
2. i=0 とする。
3. i 番目と i+h 番目を比べ、i+h 番目が小さい場合入れ替える。
4. i=i+1 とし、i+h>n となるまで3を繰り返す。
5. hがすでに1になっている場合は入れ替えが発生しなくなるまで上の操作を繰り返す。
6. h を 1.3 で割り、小数点以下を切り捨てた数を新たに間隔 h とし、操作を繰り返す。[wikipedia引用]

実装

def combSort(data)
    h = data.length * 10 / 13; # 総数 n を 1.3 で割り、小数点以下を切り捨てた数を間隔 h
    
    while (true) do
        swaps = 0;
        # i+hが h番目から総数のインデックス番目(data.length-1)まで=>iが0~(data.length-1-h)
        (data.length-h).times do |i|
            if (data[i] > data[i + h])
                swap(data, i, i + h) # dataのi番目とi+h番目を交換
                swaps+=1
            end
        end

        # hが1で、一回も交換が行われなかったとき、ソートが完了する
        # hが1だが、交換が発生した場合、ここはスキップされて、入れ替えが発生しなくなるまで比較が繰り返される
        # hがまだ1じゃないとき、hを更新して比較が繰り返される
        if (h == 1) 
            if (swaps == 0)
                break
            end
        else
            h = h * 10 / 13
        end
    end
end

def swap(a, i, j)
    t = a[i]
    a[i] = a[j]
    a[j] = t
end

arr=[588, 836, 378, 16, 295, 448, 767, 648, 447, 147]
combSort(data)
p arr

<実行結果>

[94, 198, 243, 351, 408, 740, 761, 767, 796, 996]

きちんとソートされました。

今度は乱数でテストしてみる。

class CombSort
  def initialize( n )
    @target = Array.new(n)
  end
  
  def main
    puts "準備中"
    
    @target.each_index do |i|
      @target[i] = rand(1000)
    end
    
    p @target
    
    puts "並び替え開始"
    combSort(@target)
    puts "終了"
    
    p @target
  end
  
  private
  # ----- ソートアルゴリズム
  def combSort(data)
    h = data.length * 10 / 13;
    
    while (true) do
        swaps = 0;
        (data.length-h).times do |i|
            if (data[i] > data[i + h])
                swap(data, i, i + h)
                swaps+=1
            end
        end
        if (h == 1) 
            if (swaps == 0)
                break
            end
        else
            h = h * 10 / 13
        end
    end
  end
  
  def swap(a, i, j)
      t = a[i]
      a[i] = a[j]
      a[j] = t
  end
end


N = 100
comb = CombSort.new(N)
comb.main

<実行結果>

準備中
[566, 803, 958, 633, 914, 703, 480, 900, 765, 806]
並び替え開始
終了
[480, 566, 633, 703, 765, 803, 806, 900, 914, 958]

バッチリ、コームソートできました！！以上です。