Quicksort (In-Place)

Description: Sorts an array of integers using the standard in-place version of quicksort. For simplicity the right most index is chosen as pivot. If you wish to alter this, simply choose a different pivot and swap it to the end.
Tested Platform: Java SE 7, Windows 7
Language: Java
// Takes an array, along with the left and right indexes
// Partitions it and then recursively calls itself on 
// left and right halfs of array.
public static int[] quickSort(int[] data, int left, int right){
    if (left < right) {
        int i = partition(data,left,right);
        quickSort(data, left, i - 1);
        quickSort(data, i + 1 , right);	
    }
    return data;
}
	
public static int partition(int[] data, int left, int right){
    // Select a pivot value in the right most index
    int pivot = data[right];
    int i = left;
    int temp;
		
    for (int j = left; j < right; j++) {
        if (data[j] < pivot) {
            // Swap i with j, increment i
            temp = data[i];	
            data[i] = data[j];
            data[j] = temp;
            i++;
        }
    }
		
    // Move pivot to last index "i"
    temp = data[i];
    data[i] = data[right];
    data[right] = temp;
		
    return i;
}

Submitted: January 06, 2013

Return to the snippets listing