CODEWITHSUNDEEP
arraysrubyalgorithmsortingrecursion
TheStrabusiness
TheStrabusiness

Reputation: 33

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.

Upvotes: 1

Views: 90

Answers (1)

Arie Xiao
Arie Xiao

Reputation: 14082

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.

Upvotes: 2

Related Questions