quick_sort.rb

def  partition(ar) 
  p = ar[0]
  i = 1
  j = ar.size - 1

  while i<j
    i+=1 while i < j && ar[i]<p
    j-=1 while j>=i && ar[j]>p
    swap(ar,i,j) if i < j
  end
  swap(ar,i-1,0)
  puts ar.join(" ")
end

def quickSort(ar) 
  p = ar[0]

  return ar if ar.size < 2

  above = []
  below = []
  equal = [p]

  ar[1..-1].each do |i|
    if p > i
      below << i
    elsif p < i
      above << i
    else
      equal << i
    end
  end

  below = quickSort(below)
  above = quickSort(above)

  result = [below, equal, above].flatten
  puts result.join(" ")
  result
end

_ar_cnt = gets.to_i
_ar = gets.split(" ")[0.._ar_cnt].map!(&:to_i)
quickSort(_ar)