java left logo
java middle logo
java right logo
 

Home arrow Java SE Tips
 
 
Main Menu
Home
Java Tutorials
Book Reviews
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Java Network
Java Forums
Java Blog




Most Visited Tips
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Book Reviews
Top Rated Tips
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Book Reviews


Statistics
Registered Users: 4092
Java SE Tips: 614
Java ME Tips: 202
Java EE Tips: 183
Other API Tips: 779
Java Applications: 298
Java Libraries: 209
Java Games: 16
Book Reviews:
 
 
 
Quick Sort Implementation with median-of-three partitioning and cutoff for small arrays E-mail
User Rating: / 62
PoorBest 

Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, makes Θ(n log n) comparisons to sort n items. However, in the worst case, it makes Θ(n^2) comparisons. Typically, quicksort is significantly faster in practice than other Θ(n log n) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data it is possible to make design choices which minimize the possibility of requiring quadratic time. Quicksort is a comparison sort and, in efficient implementations, is not a stable sort.

Quicksort sorts by employing a divide and conquer strategy to divide a list into two sub-lists.

The steps are:

  1. Pick an element, called a pivot, from the list.
  2. Reorder the list so that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
  3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

The base case of the recursion are lists of size zero or one, which are always sorted. The algorithm always terminates because it puts at least one element in its final place on each iteration.

Quicksort with median-of-three partitioning functions nearly the same as normal quicksort with the only difference being how the pivot item is selected. In normal quicksort the first element is automatically the pivot item. This causes normal quicksort to function very inefficiently when presented with an already sorted list. The divison will always end up producing one sub-array with no elements and one with all the elements (minus of course the pivot item). In quicksort with median-of-three partitioning the pivot item is selected as the median between the first element, the last element, and the middle element (decided using integer division of n/2). In the cases of already sorted lists this should take the middle element as the pivot thereby reducing the inefficency found in normal quicksort.

The following code shows how to implement quick aortwith median-of-three partitioning and cutoff for small arrays:

    /**
     * Quicksort algorithm.
     @param a an array of Comparable items.
     */
    public static void quicksortComparable [ ] ) {
        quicksorta, 0, a.length - );
    }
    
    private static final int CUTOFF = 10;
    
    /**
     * Internal quicksort method that makes recursive calls.
     * Uses median-of-three partitioning and a cutoff of 10.
     @param a an array of Comparable items.
     @param low the left-most index of the subarray.
     @param high the right-most index of the subarray.
     */
    private static void quicksortComparable [ ] a, int low, int high ) {
        iflow + CUTOFF > high )
            insertionSorta, low, high );
        else {
            // Sort low, middle, high
            int middle = low + high 2;
            ifamiddle ].compareToalow ] ) )
                swapReferencesa, low, middle );
            ifahigh ].compareToalow ] ) )
                swapReferencesa, low, high );
            ifahigh ].compareToamiddle ] ) )
                swapReferencesa, middle, high );
            
            // Place pivot at position high - 1
            swapReferencesa, middle, high - );
            Comparable pivot = ahigh - ];
            
            // Begin partitioning
            int i, j;
            fori = low, j = high - 1; ; ) {
                whilea++i ].compareTopivot )
                    ;
                whilepivot.compareToa--j ] ) )
                    ;
                ifi >= j )
                    break;
                swapReferencesa, i, j );
            }
            
            // Restore pivot
            swapReferencesa, i, high - );
            
            quicksorta, low, i - );    // Sort small elements
            quicksorta, i + 1, high );   // Sort large elements
        }
    }
    
    /**
     * Method to swap to elements in an array.
     @param a an array of objects.
     @param index1 the index of the first object.
     @param index2 the index of the second object.
     */
    public static final void swapReferencesObject [ ] a, int index1, int index2 ) {
        Object tmp = aindex1 ];
        aindex1 = aindex2 ];
        aindex2 = tmp;
    }
    
    
    /**
     * Internal insertion sort routine for subarrays
     * that is used by quicksort.
     @param a an array of Comparable items.
     @param low the left-most index of the subarray.
     @param n the number of items to sort.
     */
    private static void insertionSortComparable [ ] a, int low, int high ) {
        forint p = low + 1; p <= high; p++ ) {
            Comparable tmp = a];
            int j;
            
            forj = p; j > low && tmp.compareToaj - ] ) 0; j-- )
                a= aj - ];
            a= tmp;
        }
    }

 Related Tips

 
< Prev   Next >

Page 1 of 0 ( 0 comments )

You can share your information about this topic using the form below!

Please do not post your questions with this form! Thanks.


Name (required)


E-Mail (required)

Your email will not be displayed on the site - only to our administrator
Homepage(optional)



Comment Enable HTML code : Yes No



 
       
         
     
 
 
 
   
 
 
java bottom left
java bottom middle
java bottom right
RSS 0.91 FeedRSS 1.0 FeedRSS 2.0 FeedATOM FeedOPML Feed

Home - About Us - Privacy Policy
Copyright 2005 - 2008 www.java-tips.org
Java is a trademark of Sun Microsystems, Inc.