【アルゴリズムの勉強】Rubyでクイックソートを書いてみる

アルゴリズムの勉強としてRubyでクイックソートを実装する。

クイックソートとは

クイックソート (quicksort) は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。
n個のデータをソートする際の最良計算量および平均計算量はO {\displaystyle (n\log n)} (n\log n)である。他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はO {\displaystyle (n^{2})} (n^{2})である。また数々の変種がある。 安定ソートではない。

クイックソート - Wikipedia

Rubyで実装

arr = [4, 20, 6, 10, 15, 2, 60, 9, 25, 12]
number_of_elements = arr.count

def quick_sort(arr, left_end, right_end)
  left_point = left_end
  right_point = right_end
  pivot = arr[(left_point + right_point) / 2]

  while left_point <= right_point
    while arr[left_point] < pivot
      left_point += 1
    end
    while arr[right_point] > pivot
      right_point += -1
    end
    if (left_point <= right_point)
      arr[left_point], arr[right_point] = arr[right_point], arr[left_point]
      left_point += 1
      right_point += -1
    end
  end

  quick_sort(arr, left_end, right_point) if left_end < right_point
  quick_sort(arr, left_point, right_end) if left_point < right_end
end

quick_sort(arr, 0, number_of_elements - 1)
p arr
# => [2, 4, 6, 9, 10, 12, 15, 20, 25, 60]

参考文献

• 明解 Javaによるアルゴリズムとデータ構造