Module: RubyLabs::RecursionLab

Defined in:
lib/recursionlab.rb

Overview

RecursionLab

The RecursionLab module has definitions of methods from Chapter 5 of Explorations in Computing.

The methods implemented in this module show how a divide and conquer strategy can lead to more efficient algorithms for searching and sorting. The method defined here include bsearch (binary search), msort (merge sort), and qsort (QuickSort).

The module also contains ‘helper methods’ that can be used to trace the execution of the algorithms.

Instance Method Summary collapse

Instance Method Details

#brackets(a, left, right = a.length-1, mid = nil) ⇒ Object

A helper method that can be called from a probe to display the contents of an array during a search or sort. See also IterationLab#brackets.

The version implemented in this module accepts an additional argument, which specifies the location of the right bracket in the output string (if this argument is not give the right bracket is inserted at the end).

An optional third argument, intended for experiments with binary search, tells the method where to insert an asterisk before an item.

Examples:

>> a = TestArray.new(15)
=> [22, 3, 70, 74, 35, 0, 82, 64, 90, 54, 88, 26, 75, 18, 17]
>> puts brackets(a, 8, 10)
 22  3  70  74  35  0  82  64 [90  54  88] 26  75  18  17
=> nil
>> puts brackets(a, 8, 10, 9)
 22  3  70  74  35  0  82  64 [90 *54  88] 26  75  18  17
=> nil



118
119
120
121
122
123
124
125
126
127
128
129
 
# File 'lib/recursionlab.rb', line 118

def brackets(a, left, right = a.length-1, mid = nil)
  left = 0 if left < 0
  right = a.length-1 if right >= a.length
  pre = left == 0 ? "" : " " + a.slice(0..(left-1)).join("  ") + " "
  inner = left <= right ? a.slice(left..right).join("  ") : ""
  post = " " + a.slice(right+1..-1).join("  ")
  res = pre + "[" + inner + "]" + post
  if mid && left < right
    res[res.index(a[mid].to_s)-1] = ?*
  end
  return res
end

#bsearch(a, k) ⇒ Object

Search array a for item k using the binary search algorithm. Returns the location of k if it’s found, or nil if k is not in the array. Note that the array must be sorted or the results are unpredictable.

Example:

>> a = TestArray.new(10).sort 
=> [5, 9, 10, 22, 38, 43, 74, 78, 86, 88]
>> bsearch(a, 38)
=> 4
>> bsearch(a, 26)
=> nil

:call-seq:

bsearch(a,k) => Fixnum

Based on the specification in Introduction to Algorithms, by Cormen et al. – :begin :bsearch



54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
# File 'lib/recursionlab.rb', line 54

def bsearch(a, k)
  lower = -1
  upper = a.length
  while true                              # iteration ends with return statement
    mid = (lower + upper) / 2             # set the mid point for this iteration
    return nil if upper == lower + 1      # search fails if the region is empty
    return mid if k == a[mid]             # search succeeds if k is at the midpoint
    if k < a[mid]
      upper = mid                         # next search: lower half of the region
    else
      lower = mid                         # next search: upper half
    end
  end   
end

#less(x, y) ⇒ Object

A copy of the less method from iterationlab.rb, reimplemented here so students can attach probes without loading IterationLab – :begin :less



199
200
201
 
# File 'lib/recursionlab.rb', line 199

def less(x, y)  # :nodoc:
  return x < y
end

#merge(a, i, gs) ⇒ Object

A helper method called from merge_groups. A call of the form merge(a, i, n) creates a list formed by merging n-element lists starting at a[i] and a[i+n]. – :begin :merge



178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
 
# File 'lib/recursionlab.rb', line 178

def merge(a, i, gs)
  ix = j = min(i + gs, a.length)
  jx = min(j + gs, a.length)
  res = []
  while i < ix || j < jx
    if j == jx || i < ix && less( a[i], a[j] )
      res << a[i]
      i += 1
    else
      res << a[j]
      j += 1
    end
  end
  return res
end

#merge_groups(a, gs) ⇒ Object

A helper method called from msort, used to merge adjacent groups of size gs in array a. – :begin :merge_groups



163
164
165
166
167
168
169
170
 
# File 'lib/recursionlab.rb', line 163

def merge_groups(a, gs)
  i = 0                            # first group starts here
  while i < a.length
    j = i + 2*gs - 1               # end of second group
    a[i..j] = merge(a, i, gs)      # merge groups at a[i] and a[i+g]
    i += 2*gs                      # next groups starts 2*g places to the right
  end
end

#msort(array) ⇒ Object

Return a copy of a, sorted using the merge sort algorithm. Each iteration merges successively larger groups of sorted sub-arrays. Since the group size doubles from one iteration to the next, the method needs only log(n) iterations to sort an array with n items.

Example:

>> a = TestArray.new(10)
=> [14, 23, 74, 83, 7, 19, 57, 29, 20, 1]
>> msort(a)
=> [1, 7, 14, 19, 20, 23, 29, 57, 74, 83]

:call-seq:

msort(a) => Array

– :begin :msort :merge :merge_groups :less



148
149
150
151
152
153
154
155
156
 
# File 'lib/recursionlab.rb', line 148

def msort(array)
  a = array.clone
  size = 1
  while size < a.length
    merge_groups(a, size)
    size = size * 2
  end
  return a
end

#msort_brackets(a, n) ⇒ Object

A method designed to be used in experiments with the merge sort algorithm. A call of the form msort_brackets(a, n) will create a string with every item from a, with brackets around each group of size n.

Example:

>> a = TestArray.new(16)
=> [45, 10, 33, 41, 57, 84, 7, 96, 18, 44, 89, 94, 36, 90, 87, 97]
>> puts msort_brackets(a, 4)
[45 10 33 41] [57 84 7 96] [18 44 89 94] [36 90 87 97]
=> nil

:call-seq:

msort_brackets(a,n) => String



218
219
220
221
222
223
224
225
226
 
# File 'lib/recursionlab.rb', line 218

def msort_brackets(a, n)
  res = []
  i = 0
  while i < a.length
    res << a[i..((i+n)-1)].join(" ")
    i += n
  end
  return "[" + res.join("] [") + "]"
end

#partition(a, p, r) ⇒ Object

Helper method for qsort. Rearrange array a so that all the items in the region between a[p] and a[r] are divided into two groups, such that every item in the left group is smaller than any item in the right group. The return value is the location of the boundary between the groups.

– :begin :partition



264
265
266
267
268
269
270
271
272
273
274
275
276
277
 
# File 'lib/recursionlab.rb', line 264

def partition(a, p, r)        # partition the region bounded by p and r
  x = a[p]                    # x is the pivot value
  i = p - 1
  j = r + 1
  while true                  # squeeze i, j until they point at items to exchange
    loop { j = j - 1; break if a[j] <= x }
    loop { i = i + 1; break if a[i] >= x }
    if i < j                  
      a[i], a[j] = a[j], a[i] # exchange items at locations i and j
    else
      return j                # no more exchanges; return location that separates regions
    end
  end
end

#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

#qsort_brackets(a, left, right) ⇒ Object

Helper procedure used to trace the execution of qsort.



281
282
283
284
285
286
287
288
289
 
# File 'lib/recursionlab.rb', line 281

def qsort_brackets(a, left, right)
  tmp = []
  tmp += a[ 0 .. (left-1) ] if left > 0
  tmp << "["
  tmp += a[ left .. right ] if right >= 0
  tmp << "]"
  tmp += a[ (right+1) .. (a.length-1) ] if right < a.length
  return tmp.join(" ")
end

#rbsearch(a, k, lower = -1,, upper = a.length) ⇒ Object

An alternative implementation of binary search, using a recursive method.

Example:

>> a = TestArray.new(10).sort 
=> [5, 9, 10, 22, 38, 43, 74, 78, 86, 88]
>> rbsearch(a, 38)
=> 4
>> rbsearch(a, 26)
=> nil

:call-seq:

rbsearch(a,k) => Fixnum

– :begin :rbsearch



85
86
87
88
89
90
91
92
93
94
 
# File 'lib/recursionlab.rb', line 85

def rbsearch(a, k, lower = -1, upper = a.length)
  mid = (lower + upper) / 2
  return nil if upper == lower + 1      # search fails if the region is empty
  return mid if k == a[mid]             # search succeeds if k is at the midpoint
  if k < a[mid]
    return rbsearch(a, k, lower, mid)
  else
    return rbsearch(a, k, mid, upper)
  end
end

#search(a, k) ⇒ Object

The linear search method from iterationlab.rb is replicated here so it can be used for baseline tests. – :begin :search



26
27
28
29
30
31
32
33
 
# File 'lib/recursionlab.rb', line 26

def search(a, k)  # :nodoc:
  i = 0
  while i < a.length
    return i if a[i] == k
    i += 1
  end
  return nil
end