Rubyでクイックソートあれこれ

独学コンピューターサイエンティストやアルゴリズム図鑑を始点に今更ながらアルゴリズムやデータ構造について学んでいるので、その流れでRubyでクイックソートを実装してみた。

他のソートの実装に比べるとやっぱクイックソートはちょっと難しい。

最初に実装したもの

配列の中からピボットになる数を選んでそれより小さいものと大きなものに分けて再帰させる、という説明からselectを使って実装。

def outer_quick_sort(numbers)
  return numbers if numbers.count <= 1 # 一番大きいか小さい数がpivotに選ばれると要素0の配列になる場合がある

  pivot = numbers[numbers.count / 2]
  smaller = numbers.select { |n| n < pivot }
  equal = numbers.select { |n| n == pivot }
  larger = numbers.select { |n| n > pivot }

  numbers = outer_quick_sort(smaller) + equal + outer_quick_sort(larger)

  return numbers
end

numbers = ((1..9).to_a + (1..9).to_a).shuffle
p outer_quick_sort(numbers)
# => [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9]

分かりやすく実装できたが、外部ソートになってしまった。
ググって出てくるコードでも割とこんなかんじでクイックソートとしているものは多い。

内部ソートで実装したもの

内部ソートでやろうとしたら大小を左右に分けるところで早くもつまづいたので、以下のイメージ図を参考に実装した。

ソートを極める！ 〜 なぜソートを学ぶのか 〜を参考に

def quick_sort(numbers, first_index, last_index)
  return if first_index >= last_index # 始点と終点のインデックスが等しいか始点の方が大きければ何もしないで抜ける

  pivot_index = (last_index - first_index) / 2 + first_index # 中間点をpivotとする
  pivot = numbers[pivot_index]
  numbers[last_index], numbers[pivot_index] = numbers[pivot_index], numbers[last_index] # pivotを一番右に移動
  pivot_insert_index = first_index
  # iにpivotより小さい値を詰めていく
  (first_index..last_index).each do |i|
    # pivotより小さな値を探す線形探索
    # 対象範囲はi以降（前回のループのiを含まない）
    (i..last_index).each do |j|
      if numbers[j] < pivot
        # pivotより小さな値が見つかればiとjを入れ替える これでiループのiの位置の値は確定
        numbers[i], numbers[j] = numbers[j], numbers[i]

        # ループ後にpivotと入れ替える位置 ループが進むごとに書き換わり、最終的には最後にpivotより小さい数が見つかったところの次の位置となる 
        pivot_insert_index = i + 1
        break
      end
    end
  end
  # ループ後にpivotを小と大の間に置く
  numbers[pivot_insert_index], numbers[last_index] = numbers[last_index], numbers[pivot_insert_index]

  quick_sort(numbers, first_index, pivot_insert_index)
  quick_sort(numbers, pivot_insert_index + 1, last_index)
end

numbers = ((1..9).to_a + (1..9).to_a).shuffle
quick_sort(numbers, 0, numbers.count - 1)
p numbers
# => [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9]

ググるとwhileを使ってがんばってるやつがよく出てくるんだけど、それに比べると分かりやすく実装できたのではないかと。
再帰ごとにRangeオブジェクトができるのを気にするならeach使ってるとこをfor文にするとよいかもしれない。

しかし最初にピボットを一番右に移動するって言うアイデアが自力では浮かばなかった。
ピボットを中心のままループすると入れ替えた後の数をまた対象に入れ替えしてしまう、というところではまっていた。

あともうひとつ注意点としてはfirst_indexとlast_indexの範囲内ではないインデックスを使わないようにすること（先頭のつもりで0とか）

しかしよくこんなアルゴリズム考えつくものだなあ。