Quicksort

The idea of quicksort is similar to merge sort, but we'll be using partitioning instead of a merge function. The idea is to take an array and divide it into 3 partitions.

1. The bottom partition, which should contain numbers lower than a number we call the pivot.
2. The top partition, which should contain numbers higher than the pivot.
3. The pivot (a single element).

Example

[8, 5, 2, 7, 1, 9, 3, 6, 4]

If we choose the last element as the pivot by default (in this case, the number 4), we need to partition the array like so:

  left    pivot      right
[2, 1, 3], [4], [8, 5, 7, 9, 6]

In this case, the pivot (number 4) is considered sorted, and then we call quicksort on the remaining two partitions.

left
[2, 1, 3] <= choose 3 as the pivot
[1], [2], [3] <= partitioned

Now, the left partition pivot (number 3) is considered sorted. Since the left and right partitions are single-element arrays, they're sorted as well.

  left    pivot       right
[1, 2, 3], [4], [8, 5, 7, 9, 6]

Right partition
[8, 5, 7, 9, 6] <= choose 6 as the pivot
[5, 6, 7, 9, 8] <= partitioned
       |                <= now we need to partition again (this is the recursive step)
       V
left2       pivot2  right2
[5],         [6],    [7, 9, 8]

Now, the right partition pivot (number 6) is considered sorted. Since left2 is a single-element array, it's considered sorted as well. Now for right2.

left2 partition
[7, 9, 8] <= choose 8 as the pivot
[7, 8, 9] <= partitioned

Now left2 is sorted. Final right partition:
[5, 6, 7, 8, 9]

Combining the left partitions and right partitions give us:
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Another good explanation (with visuals)

Implementation

Quicksort is one of the more difficult sorts to implement, so a partition function is provided for you. This function partitions a section of an array and returns the array index of the pivot. Implement quicksort while meeting the following requirements:

• written in Ruby
• no built-in functions (such as sort!)
• passes testing

Testing

Test your quicksort algorithm using a shuffled array and compare it to an ordered array.

Example

test = (1..10).to_a.shuffle
quicksort(test, 0, test.length-1)

if test == (1..10).to_a
    puts 'The sort worked!'
else
    puts 'Noooo, the sort failed!'
end

Starter Code (with partition)

# define algorithm here (you'll need lo and hi for the beginning/endpoints on the recursive call)
def quicksort(arr, lo, hi)

end

# partition function (selects a pivot, sorts into partitions, and returns the array index of the pivot)
def partition(arr, lo, hi)
  pivot = arr[hi]

  left = lo
  for element in (lo...hi)
    if arr[element] <= pivot
      arr[left], arr[element] = arr[element], arr[left]
      left += 1
    end
  end

  arr[left], arr[hi] = arr[hi], arr[left]
  return left
end

# testing quicksort
test = (1..10).to_a.shuffle
quicksort(test, 0, test.length-1)

if test == (1..10).to_a
  puts 'The sort worked!'
else
  puts 'Noooo, the sort failed!'
end