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.

Defined Under Namespace

Classes: ArrayView

Constant Summary collapse

@@viewOptions = 
{
  :array_fill => 'lightblue',
  :bar_fill => 'darkblue',
  :canvas_fill => 'white',
  :mark_color => 'blue',
  :x0 => 10,                  # left edge of leftmost bar
  :dx => 10,                  # distance between left edges of adjacent bars
  :y0 => 50,                  # top edege of tallest bar
  :y1 => 150,                 # bottom edge of array bars
  :gdy => 150,                # distance between array and temp area below
  :ymin => 3,                 # minimum height of bar
  :delay => 0.01,
}
@@drawing = 
nil

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



136
137
138
139
140
141
142
143
144
145
146
147
148
 
# File 'lib/recursionlab.rb', line 136

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
    target = Regexp.new('\b' + a[mid].to_s + '\b')
    res[res.index(target)-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



72
73
74
75
76
77
78
79
80
81
82
83
84
85
 
# File 'lib/recursionlab.rb', line 72

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



222
223
224
 
# File 'lib/recursionlab.rb', line 222

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

#mark(a, i, color) ⇒ Object

Set the fill color of the specified bar (called by qsort to indicate active regions)



389
390
391
392
393
 
# File 'lib/recursionlab.rb', line 389

def mark(a, i, color)
  rect = @@drawing.rects[i]
  rect.fill = color
  sleep(@@drawing.options[:delay])    
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



197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
 
# File 'lib/recursionlab.rb', line 197

def merge(a, i, gs)
  ix = j = min(i + gs, a.length)
  jx = min(j + gs, a.length)
  res = []
  start_group(a,i,jx) if @@drawing
  while i < ix || j < jx
    if j == jx || i < ix && less( a[i], a[j] )
      res << a[i]
      move_down(a,i) if @@drawing
      i += 1
    else
      res << a[j]
      move_down(a,j) if @@drawing
      j += 1
    end
  end
  move_up(a) if @@drawing
  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



182
183
184
185
186
187
188
189
 
# File 'lib/recursionlab.rb', line 182

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

#move_down(a, i) ⇒ Object

Move one of the bars from the main array to the next location in the auxilliary area



372
373
374
375
376
377
378
 
# File 'lib/recursionlab.rb', line 372

def move_down(a,i)
  rect = @@drawing.rects[i]
  a.touch(rect, @@drawing.history, @@drawing.palette)
  sleep(@@drawing.options[:delay])
  a.move_down(rect, @@drawing.groupstart, @@drawing.group, @@drawing.options)
  sleep(@@drawing.options[:delay])
end

#move_up(a) ⇒ Object

Move all the bars from auxilliary region back up to the main array.



382
383
384
385
 
# File 'lib/recursionlab.rb', line 382

def move_up(a)
  a.move_up(@@drawing.rects, @@drawing.groupstart, @@drawing.group, @@drawing.options)
  sleep(@@drawing.options[:delay])    
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



167
168
169
170
171
172
173
174
175
 
# File 'lib/recursionlab.rb', line 167

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



241
242
243
244
245
246
247
248
249
 
# File 'lib/recursionlab.rb', line 241

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



288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
 
# File 'lib/recursionlab.rb', line 288

def partition(a, p, r)        # partition the region bounded by p and r
  x = a[p]                    # x is the pivot value
  i = p
  mark(a, i, 'darkgreen') if @@drawing
  for j in (p+1)..r do
    touch(a, j) if @@drawing
    if a[j] <= x
      i += 1
      touch(a, i) if @@drawing
      swap(a, i, j)
    end
  end
  swap(a, p, i)
  return i
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



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

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-1)                      # sort small items (range from p to q)
    qsort(a, q+1, r)                      # sort large items (range from q+1 to r)
    mark(a, q, 'lightblue') if @@drawing
  end
  return a
end

#qsort_brackets(a, left, right) ⇒ Object

Helper procedure used to trace the execution of qsort.



317
318
319
320
321
322
323
324
325
 
# File 'lib/recursionlab.rb', line 317

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



103
104
105
106
107
108
109
110
111
112
 
# File 'lib/recursionlab.rb', line 103

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



44
45
46
47
48
49
50
51
 
# File 'lib/recursionlab.rb', line 44

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

#show_bsearch_region(a, lower, upper, mid) ⇒ Object

Note this method is not called by bsearch itself. Instead attach a probe and run the method via trace.



351
352
353
354
355
356
357
 
# File 'lib/recursionlab.rb', line 351

def show_bsearch_region(a, lower, upper, mid)
  return unless @@drawing
  rect = @@drawing.rects[mid]
  a.touch(rect, @@drawing.history, @@drawing.palette) 
  a.set_region(lower+1, upper-1, @@drawing.bar, @@drawing.options)
  sleep(@@drawing.options[:delay])    
end

#start_group(a, i, j) ⇒ Object

Method called at the start of each call to merge – position the progress bar below the group and initialize the auxilliary region where merged groups are put.



363
364
365
366
367
 
# File 'lib/recursionlab.rb', line 363

def start_group(a,i,j)
  @@drawing.groupstart = i
  @@drawing.group = []
  a.set_region(i, j, @@drawing.bar, @@drawing.options)
end

#swap(a, i, j) ⇒ Object

Helper method for partition – exchange two items in the array, and if the array is on the canvas, exchange the locations of the two bars



308
309
310
311
312
313
314
 
# File 'lib/recursionlab.rb', line 308

def swap(a, i, j)
  a[i], a[j] = a[j], a[i]
  if @@drawing
    a.swap_bars(@@drawing.rects, i, j, @@drawing.options)
    sleep(@@drawing.options[:delay])
  end
end

#touch(a, i) ⇒ Object

Update the color of a bar (cycling through the palette of colors)



397
398
399
400
 
# File 'lib/recursionlab.rb', line 397

def touch(a, i)
  rect = @@drawing.rects[i]
  a.touch(rect, @@drawing.history, @@drawing.palette) 
end

#view_array(a, userOptions = {}) ⇒ Object

Visualization for msort and qsort. Draw a vertical bar for each item in the array, setting the height of bar i according to the value of a. Merge sort uses auxilliary space for merges, so the window has room below the main array to show the merge steps.



331
332
333
334
335
336
337
338
339
340
341
342
343
 
# File 'lib/recursionlab.rb', line 331

def view_array(a, userOptions = {})
  Canvas.init(800, 400, "RecursionLab")
  options = @@viewOptions.merge(userOptions)

  rects = TestArray.draw_bars(a, options)
  progress = Canvas::Rectangle.new( options[:x0], options[:y1] + 10, options[:x0] + a.length*options[:dx], options[:y1]+15, :fill => options[:bar_fill] )

  palette = Canvas.palette( [0,0,128], [182,224,234], 4)
  palette[-1] = '#BADFEB'
  
  @@drawing = ArrayView.new(a, rects, progress, palette, [], 0, [], options)
  return true
end