lib/sorting/quick_sort.rb


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class QuickSort
  def sort(items)
    return items if items.size <= 1

    #pivot = items[rand(items.size)]
    pivot = items.sample
    less, pivots, greater = [], [], []
    items.each do |x|
      comparison = x <=> pivot
      if comparison == -1
        less << x
      elsif comparison == 1
        greater << x
      else
        pivots << x
      end
    end
    sort(less) + pivots + sort(greater)
  end
end