Module: RubyLabs::IterationLab

Defined in:
lib/iterationlab.rb

Overview

IterationLab

The IterationLab module has definitions of methods from Chapter 4 of Explorations in Computing.

The methods demonstrate how a simple strategy of repeatedly comparing items in an array can be used to search the array and to sort it. The module has two implementations of linear search (contains? and search) and an implementation of insertion sort (isort).

Helper methods called by the searching and sorting methods are also documented here.

Instance Method Summary collapse

Instance Method Details

#brackets(a, i) ⇒ Object

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

A call to brackets(a,i) will return a string that includes all the items in a, with a left bracket before a[i] and a right bracket after the last item.

See also RecursionLab#brackets.

Example:

>> a = TestArray.new(10)
=> [55, 29, 72, 33, 14, 57, 85, 42, 26, 97]
>> puts brackets(a, 3)
29  55  72 [33  14  57  85  42  26  97]
=> nil

:call-seq:

brackets(a,i) => String



144
145
146
147
148
149
150
151
152
153
154
 
# File 'lib/iterationlab.rb', line 144

def brackets(a, i)
  if i <= 0
    return ("[" + a.join("  ") + "]")
  elsif i >= a.length
    return " " + a.join("  ") + "  [ ]"
  else
    pre = a.slice(0..(i-1))
    post = a.slice(i..-1)
    return " " + pre.join("  ") + " [" + post.join("  ") + "]"
  end
end

#contains?(a, k) ⇒ Boolean

The RubyLabs implementation of Ruby’s include? method. Does a linear search of array a to find item k, returning true or false depending on whether the item was found.

Example:

>> a = TestArray.new(10)
=> [89, 41, 69, 14, 4, 7, 8, 26, 81, 12]
>> contains?(a, 7)
=> true
>> contains?(a, 42)
=> false

:call-seq:

contains?(a,k) => Boolean

– :begin :contains?

Returns:

  • (Boolean) 


39
40
41
42
 
# File 'lib/iterationlab.rb', line 39

def contains?(a, k)
  a.each { |x| return true if x == k}
  return false
end

#isort(array) ⇒ Object

Return a copy of a, sorted using the insertion sort algorithm.

On each iteration remove an item from the array, find a location for it to the left of its original position, and insert it back into the array at the new location.

Example:

>> a = TestArray.new(10)
=> [97, 87, 16, 2, 81, 80, 7, 64, 5, 71]
>> isort(a)
=> [2, 5, 7, 16, 64, 71, 80, 81, 87, 97]

:call-seq:

isort(a) => Array

– :begin :isort :move_left :less



89
90
91
92
93
94
95
96
97
 
# File 'lib/iterationlab.rb', line 89

def isort(array)
  a = array.clone           # don't modify the input array....
  i = 1
  while i < a.length
    move_left(a, i)       # find a place for a[i] somewhere to the left
    i += 1
  end
  return a
end

#less(x, y) ⇒ Object

less is called by isort to compare two items. It is implemented as a helper method in order to allow users to attach a probe to count the number of comparisons. – :begin :less



120
121
122
 
# File 'lib/iterationlab.rb', line 120

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

#move_left(a, i) ⇒ Object

Helper method called by isort to remove the item at locaton i and reinsert it at a location between 0 and i (i.e. move the item to the left in the array). – :begin :move_left



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

def move_left(a, i)
  x = a.slice!(i)                 # remove the item at location i
  j = i-1                         # start scanning from the left of i
  while j >= 0 && less(x, a[j])
    j = j-1                       # move left
  end
  a.insert(j+1, x)                # insert x back into a at location j    
end

#search(a, k) ⇒ Object

The RubyLabs implementation of Ruby’s index method. Does a linear search of array a to find item k, returning the index of the first occurrence of k or nil if k is not found.

Example:

>> a = TestArray.new(10)
=> [89, 41, 69, 14, 4, 7, 8, 26, 81, 12]
>> search(a, 42)
=> nil
>> search(a, 7)
=> 5

:call-seq:

search(a,k) => Fixnum

– :begin :search



63
64
65
66
67
68
69
70
 
# File 'lib/iterationlab.rb', line 63

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