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.
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:
2 Call us over to discuss your answers.
java Demo avgNumbers.txtThe 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.
23 17 5 90 12 44 38 84 77 ^ | sortedThe 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 ^ | sortedThen 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 ^ | sortedNext 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 ^ | sortedEach 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 ^ | sortedand 5 is copied into where it belongs, completing the second pass.
temp = 5 5 17 23 15 12 44 38 84 77 ^ | sortedNext 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 ^ | sortedThen 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 ^ | sortedand 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
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.
45 23 17 67 78 89 90 92 99When a pass is made on this array, the 45 and 23 will be exchanged
23 45 17 67 78 89 90 92 99and the 45 and the 17 will be exchanged
23 17 45 67 78 89 90 92 99That 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:
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.
8
When you are ready, call us over to see your results and
explain them.