Module: RubyLabs::RecursionLab

Defined in:
lib/recursionlab.rb

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.



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

def brackets(a, left, right = a.length-1, mid = nil)    # :nodoc:
   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

:begin :bsearch



45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
# File 'lib/recursionlab.rb', line 45

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

#bsearch_count(n) ⇒ Object

A test harness for bsearch – makes an array, gets an item not in the array, counts comparisons (assuming user has set a counting probe)



105
106
107
108
109
 
# File 'lib/recursionlab.rb', line 105

def bsearch_count(n)
  a = TestArray.new(n)
  x = a.random(:fail)
  count { bsearch(a,x) }
end

#less(x, y) ⇒ Object

:begin :less



158
159
160
 
# File 'lib/recursionlab.rb', line 158

def less(x, y)
  return x < y
end

#merge(a, i, n) ⇒ Object

:begin :merge



140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
 
# File 'lib/recursionlab.rb', line 140

def merge(a, i, n)    # :nodoc:
  ix = j = min(i + n, a.length)
  jx = min(j + n, 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

#msort(a) ⇒ Object

:begin :msort :merge :less



120
121
122
123
124
125
126
127
128
129
130
131
132
133
 
# File 'lib/recursionlab.rb', line 120

def msort(a)
  g = 1                       # group size
  while g < a.length
 	  tmp = []                  # append merged groups to this array
    i = 0                     # first group starts here
    while i < a.length
      tmp += merge(a, i, g)   # merge groups at a[i] and a[i+g], append to tmp
      i += 2*g                # next groups starts 2*g places to the right of i
    end
    g *= 2                    # double the group size
    a = tmp                   # a now refers to array just built
  end
 	return a
end

#msort_brackets(a, n) ⇒ Object

Helper function to print brackets during merge sort



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

def msort_brackets(a, n)      # :nodoc:
  # return " [" + a[i..i+2*n-1].join(" ") + "] "
	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

:begin :partition



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

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

:begin :qsort :partition



186
187
188
189
190
191
192
193
194
 
# File 'lib/recursionlab.rb', line 186

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



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

def qsort_brackets(a, left, right)       # :nodoc:
  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

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

:begin :rsearch



68
69
70
71
72
73
74
75
76
77
 
# File 'lib/recursionlab.rb', line 68

def rsearch(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 rsearch(a, k, lower, mid)
  else
    return rsearch(a, k, mid, upper)
  end
end

#search(a, k) ⇒ Object

:begin :search



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

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