java left logo
java middle logo
java right logo
 

Home arrow Java SE Tips arrow java.lang arrow Quickselect Implementation with median-of-three partitioning and cutoff for small arrays
 
 
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: 4084
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:
 
 
 
Quickselect Implementation with median-of-three partitioning and cutoff for small arrays E-mail
User Rating: / 18
PoorBest 

In computer science, quickselect is an algorithm to select the nth smallest element of an array, based on the quicksort algorithm.

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 select algorithm in Java:

    /**
     * Quick selection algorithm.
     * Places the kth smallest item in a[k-1].
     @param a an array of Comparable items.
     @param k the desired rank (1 is minimum) in the entire array.
     */
    public static void quickSelectComparable [ ] a, int ) {
        quickSelecta, 0, a.length - 1, k );
    }
    
    /**
     * Internal selection method that makes recursive calls.
     * Uses median-of-three partitioning and a cutoff of 10.
     * Places the kth smallest item in a[k-1].
     @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.
     @param k the desired rank (1 is minimum) in the entire array.
     */
    private static void quickSelectComparable [ ] a, int low, int high, int ) {
        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 - );
            
            // Recurse; only this part changes
            ifk <= i )
                quickSelecta, low, i - 1, k );
            else ifk > i + )
                quickSelecta, i + 1, high, k );
        }
    }
    
    
    /**
     * 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;
        }
    }
    
    
    private static final int CUTOFF = 10;
    
    /**
     * 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;
    }

 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.