To quicksort an array, you pick one of the array elements to use as a pivot point. Then divide the array into two different arrays; the left array is very element less than the pivot and the right array is everything that is greater than the pivot.
Then recursively call quicksort on the left and right arrays until they are split into one element arrays. Join all the one element arrays into the final sorted array.
# Quick Sort
# Select element closest to middle (called pivot element)
# puts all elements <= pivot to the left
# puts all elements > pivot to the right
# recursively call this method on the sublists
# solution one
def quick_sort(list)
sl = list.clone
return sl if sl.size <= 1
pivot = sl.pop # last element of array
left, right = sl.partition {|e| e < pivot} # partion divides the array into two arrays
# left = ( e < pivot) and right is ( e > pivot)
quick_sort(left) + [pivot] + quick_sort(right) # recursively divide and sort left and right arrays
end
# solution two
def qsort(list)
return [] if list.size == 0
# splat operator splits list into x & xs
# x is the pivot and first element in arrray, xs is the rest of the list
x, *xs = list
less, more = xs.partition{|y| y < x}
qsort(less) + [x] + qsort(more)
end
#solution three
def quicksort(list)
return if not list || list == []
x, *xs = list
# uses select to create array with elements where condition is true
# recursively keeps checking
# uses select to create array with elements where condition is true
# recursively keeps checking
quicksort(xs.select { |i| i < x }) + [x] + quicksort(xs.select { |i| i >= x })
end
list = [9,0,2,45,32,6,7,20,19,5]
p list
p quick_sort(list)
p qsort(list)
p quicksort(list)
