quick_sort.rb

# First is to check if the array.length is less or equal to 1. If it is, it means the array is already sorted.
# Pick a pivot at random
# Delete the item at a specific index using ruby delete_at inbuild method
# We will using rand to get a randomized index from the array to make as our pivot.
# Save that item as the pivot
# Create a new left and right subarray
# Loop through all the items on the array and compare them with the pivot
# If an item is less than the pivot it should be added to the left subarray and if the item is more than the pivot, it should be added to the right subarray.

def quick_sort(array)

  # check if array length is less or equal 1
  # if it is, return the array as sorted
  return array if array.length <= 1
  pivot = array.delete_at(rand(array.length)) # pick a pivot at random

  left = Array.new
  right = Array.new

  # For each item on array, check it is less or greater than the pivot
  # push to the left or right sub arrays depending if the item is less or
  # greater than the pivot.
  array.each do |x|
    if x <= pivot
      left << x
    else
      right << x
    end
  end

  return *quick_sort(left), pivot ,*quick_sort(right)

end

p quick_sort([12,34,6,2,7,8,9,9,3,5,21,6,23,6,23,5,23])