# problem with quicksort

Printable View

• 03-04-2009, 08:34 PM
jvasilj1
problem with quicksort
hello all, so far i am working on a quicksort program and have the following done.
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.
Quote:

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
• 03-04-2009, 08:37 PM
jvasilj1
The output should look like this
Quote:

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
• 03-05-2009, 01:09 AM
jvasilj1
anyone availble to help?