15110 SUMMER SESSION ONE - 2013

Lab 5 - Thursday, May 30

Deliverables

1. timings.txt
2. mean.rb
3. bubble_sort.rb

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

CA Demonstration

• setting up RubyLabs
• linear search function

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

• timing linear search for 150 in Array(100...200)

Activities

1. Create an array whose elements contain the integers from 10,000 through 20,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 (10000)
      2. element in middle (15000)
      3. element at back (20000)
      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 do you think the relationship between the position of the item you are searching for in the list and how long it takes to find that item?

   Write your answers in a text file called timings.txt.

2. In mean.rb, write a Ruby function mean(list)to compute the arithmetic mean (or average) of a list of numbers.

   Use the following algorithm:

   1. Set sum to 0.
   2. For each element x of list, do the following:
      1. Add x to sum.
   3. Return \(\frac{\textit{sum}}{\textit{list.length}}\).

   Use floating point division as appropriate.

   Example:

   >> mean([1, -2, 3, 0, -4, -2, 7])
   => 0.428571428571429
   

3. In bubble_sort.rb, write a Ruby function bsort!(list) that will arrange the elements of the array list in ascending 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 greater 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 nil.

   Example:

   >> a = [1, -2, 3, 0, -4, -2, 7]
   => [1, -2, 3, 0, -4, -2, 7]
   >> bsort!(a)
   => nil
   >> a
   => [-4, -2, -2, 0, 1, 3, 7]
   

   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.

   • (harder) 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.