Quick_sort.rb

This content was produced by an LLM and could include errors.

このスクリプトはクイックソートです。先頭要素をピボットとして残りを「小さい左グループ」「大きい右グループ」へ振り分け、各グループを再帰的にソートして [pivot] を挟んで結合します。バラバラの [5,3,...,1] が昇順 [0..9] に整列します。shift でピボットを取り除くため、元の配列は空になる点に注意してください。

# frozen_string_literal: true
#=> nil

def quick_sort(data)
  return data if data.size <= 1
  pivot = data.shift
  left = []
  right = []
  
  data.each do |element|
    pivot > element ? (left << element) : (right << element)
  end
  quick_sort(left) + [pivot] + quick_sort(right)
end
#=> :quick_sort

data = [5, 3, 4, 0, 2, 9, 6, 8, 7, 1]
#=> [5, 3, 4, 0, 2, 9, 6, 8, 7, 1]
p quick_sort(data)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
#=> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Ruby 4.0.6