A look at three different ways to implement QuickSort in ruby

I am teaching myself computer science concepts like Big Oh notation and different sorting algorithms. I found several ways of implementing quicksort that taught me some Ruby fun that I thought I'd share.

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

    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)