3.10 PROGRAMMING EXERCISES 103
3.2.4. Does your test show any differences? How do your results relate to
the analysis done in this chapter and as part of the exercises? Try to explain
any differences.
- Use the technique above with quicksort using the versions of PivotList
given in the chapter and in the exercises in Section 3.7.3. Does your test
show any differences? How do your results relate to the analysis done in this
chapter and as part of the exercises? Try to explain any differences.
- Using the previous general technique, investigate the impact of the incre-
ment on shellsort. You should create a version of the ShellSort function
that has an additional parameter, which is just an array with the increment
values to use in decreasing order. You will need to alter this function so it
uses the values passed in instead of the increments that are calculated based
on the powers of 2. You should work with random lists of 250 elements and
make sure that each of the sets of increments discussed in Section 3.3 is used
with each list generated. How do your results relate to the analysis done in
Section 3.3? Try to explain any differences.
- Some people find it easier to understand an algorithm if they can visualize it
in action. The numeric values in a list can be visualized by drawing a vertical
bar for each list element with the first element to the left and the last to the
right. The height of each bar is based on the value stored at that element.
For example, if we have a list with the values from 1 to 500, the location
where the 1 is stored would have a bar 1 unit high and the location where
the 500 is stored would have a bar 500 units high. A random list would have
the bars all mixed up, but a list sorted in increasing order would appear as a
triangle with the shortest bar to the left and the largest to the right.
The operation of a sorting algorithm can be seen if the list is displayed as
described above after each pass of the sorting algorithm. This allows the
viewer to watch as the elements are moved into their proper position by the
sort algorithm. Write a program (or programs) using randomly arranged lists
for the cases below. You should use lists of between 250 and 500 elements,
depending on capabilities of the computer(s) you are using. On fast com-
puters, you may need to put in a short delay so that the visualization does
not happen too quickly.
a. Insertion sort—displaying the list at the end of each pass of the outer
loop
