Thread: problem with quicksort

1. Member 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 ){ }
now i am not a java guy at all and i was wondering if someone could help me implement what i have so far to meet the requirments of the following.
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 (non-recursive)
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
Thanks very much to anyone that helps
Last edited by jvasilj1; 03-04-2009 at 07:36 PM. Reason: mistake  Reply With Quote

2. Member 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 (non-recursive) takes 2109 ms
Quicksort (non-recursive) sorted takes 1719 ms
Quicksort (non-recursive median of 3) takes 1969 ms
Quicksort (non-recursive 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 (non-recursive) takes 2141 ms
Quicksort (non-recursive median of 3) takes 1859 ms
Quicksort (non-recursive median of 3) sorted takes 2343 ms  Reply With Quote

3. Member Join Date
Jan 2008
Posts
36
Rep Power
0 anyone availble to help?  Reply With Quote Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•