15110 Fall 2012 [Kaynar/Touretzky]

Lab 4 - Thursday, February 7, 2013

Deliverables

timings.txt
all_even.rb
bubble_sort.rb

Place these files in a lab4 folder. Before leaving lab, zip up the lab4 folder and hand in the zip file.

CA Demonstration

Configure your gedit: enable line numbers and bracket matching; change default tab width to 2.
Setting up RubyLabs
Creating an array containing a range of elements, for example, (1..10).to_a() or Array(1..10)
Creating an array with a given size, initialized with a given value, using RubyLabs: Array.new(10,0)

Linear search function

def search(list, key)
  len = list.length
  index = 0
  while index < len do
    if list[index] == key then
      return index
    end
    index = index + 1
  end
  return nil
end

Timing linear search for 700 in Array(100..1000) using RubyLabs: time { search(a, 700) } where a is an array

Activities

Create an array whose elements contain the integers from 100,000 through 300,000, inclusive and set the variable big_list to contain that array.
1. Use the Rubylabs time { expr } construct to time how long it takes the search function above to find each of the following in big_list:
  1. element at front (100000)
  2. element in middle (200000)
  3. element at back (300000)
  4. element not in the list (3)
  How long does each take?
2. If you repeat the same searches, does it take exactly the same amount of time? Why do you think this is?
3. How would you describe the relationship between the position of the item you are searching for in the list and how long it takes to find that item? (Is the search time independent of the position, or is there some mathematical relationship between the two quantities?)
Write your answers in a text file called timings.txt.
In all_even.rb, write a Ruby function all_even?(list) that takes an integer list as an argument and returns true if all the elements in the list are even numbers and false otherwise.
Example:
```
>> 4.even?
=> true
>> 5.even?
=> false
>> all_even?([1, 2, 8, 12, 99])
=> false
>> all_even?([4, 10, 14, 100])
=> true
```
In bubble_sort.rb, write a Ruby function bsort!(list) that will arrange the elements of the array list in descending order. (Note, the "!" is part of the name of the function. There is a convention among Ruby programmers to add exclamation points to the names of functions that modify their arguments or the object to which they belong.)

Use the following algorithm:
1. Set n to the length of list.
2. Repeat the following \(n-1\) times:
  1. For each integer \(j\) from 0 through two less than the length of list, do the following:
    1. If the element at index \(j\) in list is less than the element at index \(j+1\) in list, then do the following:
      1. Set temp to the value of the element at index \(j\) in list.
      2. Set the value of the element at index \(j\) in list to the value of the element at index \(j+1\) in list.
      3. Set the value of the element at index \(j+1\) in list to the value of temp.
3. Return list.
Example:
```
>> a = [-2, 5, 0, -4, 8, 0, 9]
=> [-2, 5, 0, -4, 8, 0, 9]
>> bsort!(a)
=> [9, 8, 5, 0, 0, -2, -4]
>> a
=> [9, 8, 5, 0, 0, -2, -4]
```
Challenge:
- The above algorithm repeats step II.A.1 more times than is necessary. Modify your code to restrict the range of \(j\), so that unnecessary executions of II.A.1 are avoided.
- In the algorithm given above, the number of times the loop is repeated is independent of the contents of list. Modify the algorithm so that it detects when list has become sorted and returns nil immediately.