Java Reference
In-Depth Information
Modify the Bubble Sort implementation to add this flag and test. Compare
the modified implementation on a range of inputs to determine if it does or
does not improve performance in practice.
7.2 Double Insertion Sort is a variation on Insertion Sort that works from the
middle of the array out. At each iteration, some middle portion of the array
is sorted. On the next iteration, take the two adjacent elements to the sorted
portion of the array. If they are out of order with respect to each other, than
swap them. Now, push the left element toward the right in the array so long
as it is greater than the element to its right. And push the right element
toward the left in the array so long as it is less than the element to its left.
The algorithm begins by processing the middle two elements of the array if
the array is even. If the array is odd, then skip processing the middle item
and begin with processing the elements to its immediate left and right.
First, explain what the cost of Double Insertion Sort will be in comparison to
standard Insertion sort, and why. (Note that the two elements being processed
in the current iteration, once initially swapped to be sorted with with respect
to each other, cannot cross as they are pushed into sorted position.) Then, im-
plement Double Insertion Sort, being careful to properly handle both when
the array is odd and when it is even. Compare its running time in practice
against standard Insertion Sort. Finally, explain how this speedup might af-
fect the threshold level and running time for a Quicksort implementation.
7.3 Perform a study of Shellsort, using different increments. Compare the ver-
sion shown in Section 7.3, where each increment is half the previous one,
with others. In particular, try implementing “division by 3” where the incre-
ments on a list of length n will be n=3, n=9, etc. Do other increment schemes
work as well?
7.4 The implementation for Mergesort given in Section 7.4 takes an array as in-
put and sorts that array. At the beginning of Section 7.4 there is a simple
pseudocode implementation for sorting a linked list using Mergesort. Im-
plement both a linked list-based version of Mergesort and the array-based
version of Mergesort, and compare their running times.
7.5 Starting with the Java code for Quicksort given in this chapter, write a series
of Quicksort implementations to test the following optimizations on a wide
range of input data sizes. Try these optimizations in various combinations to
try and develop the fastest possible Quicksort implementation that you can.
(a) Look at more values when selecting a pivot.
(b) Do not make a recursive call to
qsort
when the list size falls below a
given threshold, and use Insertion Sort to complete the sorting process.
Test various values for the threshold size.
(c) Eliminate recursion by using a stack and inline functions.
