Method: RubyLabs::RecursionLab#qsort

Defined in:
lib/recursionlab.rb

#qsort(a, p = 0, r = a.length-1) ⇒ Object

Return a sorted copy of a, sorted using the QuickSort algorithm.

The parameters p and q represent the left and right boundaries of the region to sort. The top level call to qsort should not include values for p and q, so they are initially set to the the beginning and ending locations in the array. Recursive calls will pass values for p and q that define successively smaller regions to sort.

Example:

>> a = TestArray.new(10)
=> [58, 94, 62, 63, 85, 22, 64, 45, 30, 77]
>> qsort(a)
=> [22, 30, 45, 58, 62, 63, 64, 77, 85, 94]

Based on the specification in Introduction to Algorithms, by Cormen et al.

– :begin :qsort :partition



245
246
247
248
249
250
251
252
253
 
# File 'lib/recursionlab.rb', line 245

def qsort(a, p = 0, r = a.length-1)       # sort the region bounded by p and r
  a = a.dup if p == 0 && r == a.length-1  # don't modify the input array (top level only)
  if p < r
    q = partition(a, p, r)                # q is boundary between small items and large items
    qsort(a, p, q)                        # sort small items (range from p to q)
    qsort(a, q+1, r)                      # sort large items (range from q+1 to r)
  end
  return a
end