ソートのアルゴリズムを実装するその3　交換ソート

交換ソート系列のソートアルゴリズムを学習する

コムソート

概要

1. 総数 n を 1.3 で割り、小数点以下を切り捨てた数を間隔 h とする。
2. 1 番目と 1+h 番目を比べ、1+h 番目の方が小さい場合入れ替える。
3. 次に2番目と2＋h番目を比べ・・・とリストの最後まで繰り返す
4. h を 1.3 で割り、小数点以下を切り捨てた数を新たに間隔 h とし、2・3を繰り返す。
5. hがすでに1になっている場合は入れ替えが発生しなくなるまで2・3を繰り返す。 このアルゴリズムの目的は交換回数を減らすというもの 最初に大雑把に値を正しい位置に近づけて行き、どんどん精度を上げていくというアルゴリズム

実装

def comb array
  h = array.length * 10 / 13
  while true
    flag = false
    (array.length - h).times do |i|
      if array[i] > array[i + h]
        array[i], array[i + h] = array[i + h], array[i]
        flag = true
      end
    end
    if h == 1
      if flag == false
        break
      end
    else
        h = h * 10 / 13
    end
  end
end

ソートの流れ

ノームソート

概要

挿入ソートに似ている 挿入ソートでは、前から順にそれまでの数値をソートし、次の値を適切な位置に挿入するという方法だった。 ノームソートでは前から順にソートするのは変わらないが、次の値を挿入ではなく、バブルソートで適切な位置にソートするという方法を取る 例： [1, 3, 7, 9, 2] このリストで、四番目の9まではソートが終わっていて、次は5番目の2の値を含めるという場合 まずは一個手前の９と比較して９のほうが大きいので入れ替える [1, 3, 7, 2, 9] その手前の７と比較して入れ替える [1, 3, 2, 7, 9] その手前の３と比較して入れ替える [1, 2, 3, 7, 9] その手前の１と比較して２の方が大きいので次に３の値をソートする ３はその手前の２と比較して大きいのでそのまま次の７の値をソートする ７はその手前の３と比較して大きいのでそのまま次の９の値をソートする ９はその手前の７と比較して大きいのでそのままにして、９が最後の値なのでソート完了 [1, 2, 3, 7, 9]

実装

def gnome array
  i = 1
  while i < array.length
    if array[i] < array[i - 1]
      array[i], array[i - 1] = array[i - 1], array[i]
      if i != 1
        i -= 1
      else
        i += 1
      end
    else
      i += 1
    end
  end
end

コードも単純で、ソート中に値が追加されても適切にソートできる