TheStrabusiness - 3 months ago 17

Ruby Question

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`

`left`

`< pivot`

`right`

`Return pivot`

`left`

`right`

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`

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

- 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`

) - The pivot
- 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.

Source (Stackoverflow)

Comments