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
-
#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.
-
#bsearch(a, k) ⇒ Object
Search array
a
for itemk
using the binary search algorithm. -
#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. -
#mark(a, i, color) ⇒ Object
Set the fill color of the specified bar (called by qsort to indicate active regions).
-
#merge(a, i, gs) ⇒ Object
A helper method called from
merge_groups
. -
#merge_groups(a, gs) ⇒ Object
A helper method called from
msort
, used to merge adjacent groups of sizegs
in arraya
. -
#move_down(a, i) ⇒ Object
Move one of the bars from the main array to the next location in the auxilliary area.
-
#move_up(a) ⇒ Object
Move all the bars from auxilliary region back up to the main array.
-
#msort(array) ⇒ Object
Return a copy of
a
, sorted using the merge sort algorithm. -
#msort_brackets(a, n) ⇒ Object
A method designed to be used in experiments with the merge sort algorithm.
-
#partition(a, p, r) ⇒ Object
Helper method for
qsort
. -
#qsort(a, p = 0, r = a.length-1) ⇒ Object
Return a sorted copy of
a
, sorted using the QuickSort algorithm. -
#qsort_brackets(a, left, right) ⇒ Object
Helper procedure used to trace the execution of qsort.
-
#rbsearch(a, k, lower = -1,, upper = a.length) ⇒ Object
An alternative implementation of binary search, using a recursive method.
-
#search(a, k) ⇒ Object
The linear search method from iterationlab.rb is replicated here so it can be used for baseline tests.
-
#show_bsearch_region(a, lower, upper, mid) ⇒ Object
Note this method is not called by bsearch itself.
-
#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.
-
#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.
-
#touch(a, i) ⇒ Object
Update the color of a bar (cycling through the palette of colors).
-
#view_array(a, userOptions = {}) ⇒ Object
Visualization for msort and qsort.
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 |
# 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 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
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
221 222 223 |
# File 'lib/recursionlab.rb', line 221 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)
388 389 390 391 392 |
# File 'lib/recursionlab.rb', line 388 def mark(a, i, color) rect = @@drawing.rects[i] rect.fill = color sleep(@@drawing.[: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
196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 |
# File 'lib/recursionlab.rb', line 196 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
181 182 183 184 185 186 187 188 |
# File 'lib/recursionlab.rb', line 181 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
371 372 373 374 375 376 377 |
# File 'lib/recursionlab.rb', line 371 def move_down(a,i) rect = @@drawing.rects[i] a.touch(rect, @@drawing.history, @@drawing.palette) sleep(@@drawing.[:delay]) a.move_down(rect, @@drawing.groupstart, @@drawing.group, @@drawing.) sleep(@@drawing.[:delay]) end |
#move_up(a) ⇒ Object
Move all the bars from auxilliary region back up to the main array.
381 382 383 384 |
# File 'lib/recursionlab.rb', line 381 def move_up(a) a.move_up(@@drawing.rects, @@drawing.groupstart, @@drawing.group, @@drawing.) sleep(@@drawing.[: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
166 167 168 169 170 171 172 173 174 |
# File 'lib/recursionlab.rb', line 166 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
240 241 242 243 244 245 246 247 248 |
# File 'lib/recursionlab.rb', line 240 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
287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 |
# File 'lib/recursionlab.rb', line 287 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
267 268 269 270 271 272 273 274 275 276 |
# File 'lib/recursionlab.rb', line 267 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.
316 317 318 319 320 321 322 323 324 |
# File 'lib/recursionlab.rb', line 316 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.
350 351 352 353 354 355 356 |
# File 'lib/recursionlab.rb', line 350 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., @@drawing.) sleep(@@drawing.[: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.
362 363 364 365 366 |
# File 'lib/recursionlab.rb', line 362 def start_group(a,i,j) @@drawing.groupstart = i @@drawing.group = [] a.set_region(i, j, @@drawing., @@drawing.) 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
307 308 309 310 311 312 313 |
# File 'lib/recursionlab.rb', line 307 def swap(a, i, j) a[i], a[j] = a[j], a[i] if @@drawing a.(@@drawing.rects, i, j, @@drawing.) sleep(@@drawing.[:delay]) end end |
#touch(a, i) ⇒ Object
Update the color of a bar (cycling through the palette of colors)
396 397 398 399 |
# File 'lib/recursionlab.rb', line 396 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.
330 331 332 333 334 335 336 337 338 339 340 341 342 |
# File 'lib/recursionlab.rb', line 330 def view_array(a, userOptions = {}) Canvas.init(800, 400, "RecursionLab") = @@viewOptions.merge(userOptions) rects = TestArray.(a, ) progress = Canvas::Rectangle.new( [:x0], [:y1] + 10, [:x0] + a.length*[:dx], [:y1]+15, :fill => [:bar_fill] ) palette = Canvas.palette( [0,0,128], [182,224,234], 4) palette[-1] = '#BADFEB' @@drawing = ArrayView.new(a, rects, progress, palette, [], 0, [], ) return true end |