TheStrabusiness - 1 year ago 118
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.

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]
c + d
end
#=> 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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download