[Java] Quick Sort

quick_sort.java

// https://en.wikipedia.org/wiki/Quicksort
// with upper pivot selection
public static void quickSort(int[] nums) {
    qsSub(nums, 0, nums.length-1);
}

private static void qsSub(int[] nums, int lo, int hi) {
    // base-case
    if (lo >= hi) {
        return;
    }
    int p = qsPartition(nums, lo, hi); // find the pivot
    // values left of p are lower than nums[p] while values right of p are greater than nums[p]
    qsSub(nums, lo, p - 1); // sort lower half
    qsSub(nums, p + 1, hi); // sort upper half
}

private static int qsPartition(int[] nums, int lo, int hi) {
    int pivot = nums[hi]; // simply pick right most value as the pivot
    int p = lo - 1; // temp next pivot index
    for (int j = lo; j < hi; j++) {
        // swap values <= current pivot to place them left of the new pivot index
        if (nums[j] <= pivot) {
            swap(nums, ++p, j);
        }
    }
    // swap the current and new pivot values
    swap(nums, ++p, hi);
    return p;
}

private static void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}


//
//
// Slightly more compacted version
//
//

// https://en.wikipedia.org/wiki/Quicksort
public static void quickSort(int[] nums) {
    qs(nums, 0, nums.length-1);
}

private static void qs(int[] nums, int lo, int hi) {
    if (lo >= hi) {
        return;
    }
    int p = qp(nums, lo, hi);
    qs(nums, lo, p-1);
    qs(nums, p+1, hi);
}

private static int qp(int[] nums, int lo, int hi) {
    int p = lo - 1;
    for (int j = lo; j < hi; j++) {
        if (nums[j] <= nums[hi]) {
            swap(nums, ++p, j);
        }
    }
    swap(nums, ++p, hi);
    return p;
}

private static void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}