Quick sort

Quick sort

def partition(a,p,r)
  q = 0
  pivot = a[r]
  if p < r
    (0).upto(r-1) do |j|
      if a[j] < pivot
        a[q],a[j] =  a[j],a[q]
        q += 1
      end
    end
  end
  a[q],a[r] =  a[r],a[q]
  q
end

def quick_sort(a, start = 0, _end = a.length - 1)
  if start < _end
    q = partition(a, start, _end)
    quick_sort(a, start, q - 1)
    quick_sort(a, q + 1, _end)
  end
  a
end