TheStrabusiness TheStrabusiness - 3 months ago 17
Ruby Question

How is the final array constructed in this Ruby quicksort implementation?

I'm learning some soring algorithms in Ruby, and learned this recursive implementation of quicksort:

class Array
def quicksort
return [] if empty?

pivot = delete_at(rand(size))

left, right = partition(&pivot.method(:>))

return *left.quicksort, pivot, *right.quicksort
end
end

array = [5,3,2,18,1,6,4,7,5,9,0]
p array
#=> [5, 3, 2, 18, 1, 6, 4, 7, 5, 9, 0]

p array.quicksort
#=> [0, 1, 2, 3, 4, 5, 5, 6, 7, 9, 18]


I think I understand basically what's happening here. Do I have this right?

Chose an arbitrary pivot, store the number and delete that index from the array. Then partition the array, putting numbers
> pivot
in an array
left
, and the numbers
< pivot
in
right
.
Return pivot
and call quicksort recursively on
left
and
right
arrays if they have anything in them.

What I don't understand is how the final array is constructed; I don't see where the returned numbers are assigned the appropriate index. Does it happen when
pivot
is returned? How does it end up in the right index?

I think some of my confusion is coming from a lack of understanding about recursion.

Thanks in advance for any help.

Answer

When you call return with a list of values, Ruby turns the list into an array and returns the array.

def return_array
  return 1, 2
end
return_array
#=> [1, 2]

This can be used in conjunction with the Array to Arguments Conversion, which turns an array into a list of elements with the splat operator '*'.

a = [1, 2]
def add(c, d)
  c + d
end
add(*a)
#=> 3

The return statements in the quicksort method does this trick, it returns a list with

  1. The splat quick sort result of the left, which are all the elements that's less than the pivot (pivot.method(:>).call(elem), i.e., pivot > elem)
  2. The pivot
  3. The splat quick sort result of the right, which are all the elements that's greater or equal than the pivot (! (pivot > elem))

And Ruby turns them into an array and return that array.

Comments