Results 1 to 3 of 3
Thread: problem with quicksort
 03042009, 07:34 PM #1Member
 Join Date
 Jan 2008
 Posts
 36
 Rep Power
 0
problem with quicksort
hello all, so far i am working on a quicksort program and have the following done.
Java Code:public static <AnyType extends Comparable<? super AnyType>> void insertionSort( AnyType [ ] a ) { for( int p = 1; p < a.length; p++ ) { AnyType tmp = a[ p ]; int j = p; for( ; j > 0 && tmp.compareTo( a[ j  1 ] ) < 0; j ) a[ j ] = a[ j  1 ]; a[ j ] = tmp; } } /**** This static method above is designed to be used with class that has the following properties: (1) It must implement Comparable interface (2) either be AnyType or a subclass of AnyType ****/ public static <AnyType extends Comparable<? super AnyType>> void mergeSort( AnyType [ ] a ) { AnyType [ ] tmpArray = (AnyType []) new Comparable[ a.length ]; mergeSort( a, tmpArray, 0, a.length  1 ); } static <AnyType extends Comparable<? super AnyType>> void merge( AnyType [ ] a, AnyType [ ] tmpArray, int leftPos, int rightPos, int rightEnd ){ } public static <AnyType> void swap( AnyType [ ] a, int index1, int index2 ) { AnyType tmp = a[ index1 ]; a[ index1 ] = a[ index2 ]; a[ index2 ] = tmp; } static <AnyType extends Comparable<? super AnyType>> void quicksort( AnyType [ ] a, int low, int high ){ }
This programming assignment is to implement and compare the following sorting algorithms :
1. quicksort (recursive version ) , use the median of three as the pivot element.
2. quicksort (recursive version ), using median of three for pivot and switch to insertion sort when size of array is less than certain predetermined integer  the cutoff size
3. quicksort (nonrecursive)
4. mergesort recursive
Java Generic must be used for each of the sorting method.
You should use arrays instead of ArrayLists or LinkedList to store
data.
(I will test your sorting methods on arrays of different class of
comparable objects, such as Double, Rational number etc .)
Put all the sorting methods in one class ( Sort.java ).
Do not package.
You also have to provide Tester class that
1. generates arrays of Integers of any given size .
2. use each sorting method to sort the array and measure the
running time for each case.
3. You might also include other utility methods.
You must submit the following:
• All the Java source codes
• Documentation that describes what you did, and how to run your program
The output should look like out.txt
Here are some java class files :
Rational.class Sort.class Test1.class
To run the program :
Type the command : java Test1 10000
Last edited by jvasilj1; 03042009 at 07:36 PM. Reason: mistake
 03042009, 07:37 PM #2Member
 Join Date
 Jan 2008
 Posts
 36
 Rep Power
 0
The output should look like this
Testing Integer Arrays of size 1000000:
Generate array takes 422 ms
Mergesort takes 1860 ms
Quicksort (cutoff size = 10, median of 3) takes 1375 ms
Quicksort (cutoff size = 10, median of 3) sorted takes 1485 ms
Quicksort (cutoff size = 20, median of 3) takes 1391 ms
Quicksort (cutoff size = 20, median of 3) sorted takes 1609 ms
Quicksort (nonrecursive) takes 2109 ms
Quicksort (nonrecursive) sorted takes 1719 ms
Quicksort (nonrecursive median of 3) takes 1969 ms
Quicksort (nonrecursive median of 3) sorted takes 4344 ms
Testing Rational Arrays of size 1000000 :
Generate Rational array takes 734 ms
Copy Rational array takes 344 ms
Mergesort takes 2109 ms
Quicksort (cutoff size = 10, median of 3) takes 1594 ms
Quicksort (cutoff size = 10, median of 3) sorted takes 2047 ms
Quicksort (cutoff size = 20, median of 3) takes 1531 ms
Quicksort (cutoff size = 20, median of 3) sorted takes 2016 ms
Quicksort (nonrecursive) takes 2141 ms
Quicksort (nonrecursive median of 3) takes 1859 ms
Quicksort (nonrecursive median of 3) sorted takes 2343 ms
 03052009, 12:09 AM #3Member
 Join Date
 Jan 2008
 Posts
 36
 Rep Power
 0
Similar Threads

quicksort program
By jvasilj1 in forum New To JavaReplies: 5Last Post: 03032009, 03:47 AM 
Quicksort
By little_polarbear in forum New To JavaReplies: 12Last Post: 07122008, 09:20 PM
Bookmarks