// 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;
}

Posted: March 20, 2023

Return to the snippets listing