CS Labs: Lab 11

CS Labs: Lab 11


To accompany Chapter 11 of An Introduction to Object-Oriented Programming with Java by C. Thomas Wu.

Searching (and Sorting) Questions

There are 9 checkpoints in this lab. If you need help with any exercise, raise your hand.

Copy the lab materials to your account by entering

             cp -r /home/Classes/Cs1/Labs/Lab11 .
     
Everything you need for the lab exercises today is contained in this new directory.

For this lab, get out some paper and pens or pencils.

Searching

Change into subdirectory InSearchOf1. Examine the code for the Demo class. Two arrays of a random size (at least 2000 elements) are created for array1 and array2. array1 is filled with random values between 0 and MAX_SIZE / 2 . These same values are copied into array2. Here the two arrays differ: array2 is sorted.

Compile and run the program. Note that the program takes noticeable time to sort if the arrays happen to be on the large side.

Carry out several (at least 10) searches for values, and pay attention to the results of the searches, both successful and unsuccessful; it will help you to write down the values and the results in a table. Searching for 0 will halt the program.

Judging only by the behaviors of the searches on the two arrays that you have just observed, how does the search algorithm used on the first array differ from the one being used on the second array? (Go ahead and look at the code if you need help.) Which one is generally faster?

1 Call us over to explain your answer.

Go into subdirectory InSearchOf2.

Compile and run the program, and perform several searches, again paying close attention to the results.

Judging only by your observations, answer the following questions:

  1. Is array1 sorted or unsorted?
  2. Which search algorithm is being used on array1?
  3. Is array2 sorted or unsorted?
  4. Which search algorithm is being used on array2?
  5. When searching array2, what was the smallest number of comparisons you observed? What was the most?

2 Call us over to discuss your answers.

Comparing Sorting Algorithms: Worst, Best and Average Cases

Go into subdirectory SortComparison, and examine the implementation of the class Demo. This program takes a command line argument. When you compile and run the Demo class, you must supply the name of a file. This program opens the file named and uses it for input. For example, to use the data file avgNumbers.txt enter
        java Demo avgNumbers.txt
The file named avgNumbers.txt contains 2000 integers. It reads the numbers in the file, stores them in an array named data, then sorts the array. At the end, it writes the contents of the sorted array to a file named sorted.txt. There are two more data files in this subdirectory: worstNumbers.txt and bestNumbers.txt. All three data files contain the same 2000 integer values. In avgNumbers.txt, integers are in random order. In contrast, in worstNumbers.txt they are descending order, the reverse of what we want, and the worst case more many sorts. In bestNumbers.txt the values are already sorted in ascending order. This is the best case for some sorts.

Right now, the Demo class is set up to do a selectionSort().

Answer this question without running the program: How many key comparisons (that is, comparisons of data values) will be performed when the program is executed using the data in avgNumbers.txt? (Remember, we are using Selection Sort on an array of 2000 data values.)

Now run the program and compare its results to your answer. If they differ significantly, explain why.

3 Call us over when you can explain why the program reported that number of comparisons. (You don't have to be able to explain the exact quantity, just why the comparisons are close to that amount.)

Fill in the number of comparisons made when you did the Selection Sort in the first row of the table below. By the end of today's lab, you will have filled the entire table.

                                  NUMBERS OF KEY COMPARISONS OBSERVED

                          avgNumbers.txt   worstNumbers.txt   bestNumbers.txt
                       +-----------------+------------------+-----------------+
                       |                 |                  |                 |
Selection Sort         |                 |                  |                 |
                       |                 |                  |                 |
                       +-----------------+------------------+-----------------+
                       |                 |                  |                 |
Bubble Sort            |                 |                  |                 |
                       |                 |                  |                 |
                       +-----------------+------------------+-----------------+
                       |                 |                  |                 |
Insertion Sort         |                 |                  |                 |
                       |                 |                  |                 |
                       +-----------------+------------------+-----------------+
                       |                 |                  |                 |
Bubble Sort (Modified) |                 |                  |                 |
                       |                 |                  |                 |
                       +-----------------+------------------+-----------------+
                       |                 |                  |                 |
Heap Sort              |                 |                  |                 |
                       |                 |                  |                 |
                       +-----------------+------------------+-----------------+

Now run the program again with selectionSort() and read data from worstNumbers.txt. Put the number of comparisons in the table. Repeat the selectionSort() once more using the data in bestNumbers.txt. Note the results in the table.

Now repeat the sorts on the three data files, but comment out the call to selectionSort() and uncomment the call to bubbleSort(). Put all your results in the table.

4 When you are ready, call us over and explain why the algorithms are similar in the situation(s) in which they are similar and why the algorithms are different in the situation(s) in which they are significantly different.

insertionSort()

Now let's examine a sort not explained in the textbook: insertionSort(). The idea behind insertionSort() is to assume that the very first cell of the array represents a one-element array that is already sorted. For example:
        23  17   5  90  12  44  38  84  77
        ^
        |
      sorted
The problem is to insert the element after the sorted part of the array into the proper position. In this case the 17 must come before the 23. That is, it must go in the cell occupied by 23 and 23 must shift back one cell. So 17 is copied into a temporary variable and 23 is copied back one cell.
        temp = 17

        23  23   5  15  12  44  38  84  77
            ^
            |
         sorted
Then 17 is copied into where 23 was and the first two cells are the sorted portion of the array. This completes the first pass of the algorithm.
        temp = 17

        17  23   5  15  12  44  38  84  77
            ^
            |
         sorted
Next the 5 must be inserted. The spot it must in is where 17 is. So the 5 is put in a temporary variable
        temp = 5

        17  23   5  15  12  44  38  84  77
            ^
            |
         sorted
Each value in the sorted portion of the array is moved back one cell starting with the 23
        temp = 5

        17  17  23  15  12  44  38  84  77
                ^
                |
             sorted
and 5 is copied into where it belongs, completing the second pass.
        temp = 5

        5  17  23  15  12  44  38  84  77
                ^
                |
             sorted

Next the 15 must be inserted. It must go where the 17 currently is, so 17 and every sorted value after it must move back one. First, 15 is placed in a temporary variable
        temp = 15

        5  17  23  15  12  44  38  84  77
                ^
                |
             sorted

Then starting with the last sorted value, copy the values back one cell, but this time, only go as far as the 17
        temp = 15

        5  17  17  23  12  44  38  84  77
                   ^
                   |
                sorted

and then copy 15 into the spot occupied by 17. This completes the third pass.
        temp = 15

        5  15  17  23  12  44  38  84  77
                   ^
                   |
                sorted

5 Perform the next two passes of this sort on paper. When you are done, show us how you completed them.

Go into the Demo class and comment out the call to bubbleSort() and uncomment the call to insertionSort(). Run insertionSort() with all three files of test data and put your results in the table above. What can you conclude about insertionSort() compared to the other two?

6 Call us over to explain your conclusions when you are ready.

A Modified Bubble Sort

We can make bubbleSort() slightly more efficient. Note the following property: If the last exchange during a pass of the sort occurs between positions i and i + 1, then the positions from i + 1 to the end of the array must already be sorted. Therefore, we don't need to check them anymore. In other words, we can move bottom up faster than one at a time. For example, consider the array
           45  23  17  67  78  89  90  92  99
           
When a pass is made on this array, the 45 and 23 will be exchanged
           23  45  17  67  78  89  90  92  99
           
and the 45 and the 17 will be exchanged
           23  17  45  67  78  89  90  92  99
           
That is the last exchange of this pass. Therefore, we know that every element from 45's position through the end is already sorted.

Modify the bubbleSort() implementation to work this way. Here is some help:

  1. You will need to add a new variable (call it lastExchangeIndex). Use this to remember the value of i when you make an exchange.
  2. After you are done making a pass, update bottom based on lastExchangeIndex instead of just decrementing bottom by one.
  3. Initialize lastExchangeIndex. Think about what its initial value should be.

After you have modified bubbleSort(), run with the three files of data (avgNumbers.txt, worstNumbers.txt, and bestNumbers.txt) to see the improvement that occurs. Record the results in the table above.

7 When you are ready, call us over to see your modified bubbleSort() and your results from running it.

Heap Sort

Finally, comment out bubbleSort() in the Demo class and uncomment heapSort(). Run this program with the three data files and put results in the table above. Are the results consistent with what you know about heap sort?

8 When you are ready, call us over to see your results and explain them.

After the Lab

Don't forget to exit Netscape before you log out.

9 Show us that you have logged out, cleaned up, and pushed in your chairs for this last checkpoint.

End of Lab


Susan Haller and Timothy Fossum, University of Wisconsin-Parkside