CSC 207 | Algorithms and Object Oriented Design | Spring 2011 |
Summary: In this lab, you will gain greater exposure to the theoretical and practical finer points of sorting.
mkdir somewhere/sorting
cd somewhere/sorting
cp ~weinman/public_html/courses/CSC207/2011S/labs/code/sorting/TrackingComparable.java . cp ~weinman/public_html/courses/CSC207/2011S/labs/code/sorting/Sort4.java . cp ~weinman/public_html/courses/CSC207/2011S/labs/code/sorting/TestSort4.java .
(You may wish to verify this with others near you.)
Hint, you may want to start by putting the first two items in order and the last two items in order. ... that takes two comparisons. Then try to get the max and min items in place (two more comparisons). Then just one step left ...
Sort4
contains an ArrayList
of
Comparable
objects called items
. Fill in
the body of the doSort()
routine with your
algorithm. You should use the get
method
of ArrayList
on
items
, the objects' compareTo
methods,
and the Sort4
object's swap(i,j)
routine
provided.
isSorted()
using either a for loop or three
comparisons.
TrackingComparable
object HAS-A Comparable
object, but also implements the Comparable
interface, so
that it can add functionality to the compareTo
call (in
order to count the number of times it has been used). What design
pattern is this?
TestSort4
iterates through all the
permutations of 4 non-equal integers, creates a Sort4
object and verifies the number of comparisons and (trustingly)
whether the objects are sorted.
Use this class to test and verify your implementations from Exercise 2. If they are all in the same directory, you should be able to run
java TestSort4after compiling it of course. If it reports no errors, then your code is presumably correct. If it does report errors, be sure fix them!
i
is initialized
to low
but is immediately
incremented. Similarly, j
is initialized
to high-1
and is immediately decremented. What would
happen if we changed lines 211-216 (inclusive) to the following,
modifying the initialization and moving the increment/decrement to
inside the while loops.
for ( i = low+1, j = high-2 ; ; )
{
while ( a[i].compareTo( pivot ) < 0 )
i++;
while ( pivot.compareTo( a[j] ) < 0 )
j--;
Sort.java
to reflect the changes
given above.
public class Driver {
public static void main(String[] args) {
Sort.quicksort( new Integer[] {5,3,3,2,1,3,2,1,4,7,2});
}
}
println
statements to determine why.
Adapted from Mark Allen Weiss, Data Structures and Problem Solving Using Java 3/e Exercises 8.20 and 8.14.