Skip to content

Instantly share code, notes, and snippets.

@Bablzz
Last active October 21, 2019 09:57
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Bablzz/b4b5b9f1d023c03d4e0d48971599bd9c to your computer and use it in GitHub Desktop.
Save Bablzz/b4b5b9f1d023c03d4e0d48971599bd9c to your computer and use it in GitHub Desktop.
quicksort in ruby
=begin
Worst time: O(n2) if choose bad pivot element
Approximate time: O(n log n)
=end
def quicksort array
if array.length < 2
array
else
pivot = array[rand(array.length)]
less = array.find_all { |element| element < pivot }
greater = array.find_all { |element| element > pivot }
quicksort(less) + Array(pivot) + quicksort(greater)
end
end
arr = [45,17,89,0,-19,99,2]
puts quicksort(arr)
# =>
#-19
# 0
# 2
# 17
# 45
# 89
# 99
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment