Results 1 to 3 of 3
  1. #1
    jvasilj1 is offline Member
    Join Date
    Jan 2008
    Posts
    36
    Rep Power
    0

    Default 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

  2. #2
    jvasilj1 is offline Member
    Join Date
    Jan 2008
    Posts
    36
    Rep Power
    0

    Default

    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

  3. #3
    jvasilj1 is offline Member
    Join Date
    Jan 2008
    Posts
    36
    Rep Power
    0

Similar Threads

  1. quicksort program
    By jvasilj1 in forum New To Java
    Replies: 5
    Last Post: 03-03-2009, 03:47 AM
  2. Quicksort
    By little_polarbear in forum New To Java
    Replies: 12
    Last Post: 07-12-2008, 09:20 PM

Posting Permissions

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