The Partition Subroutine

Internal

• Algorithms

Problem Statement

Given an array and an element of it - the pivot element - rearrange the array so it has the following property: any element that is at the left of the pivot should be smaller or equal with the pivot, and any element that is at the right of the pivot should be grater that the pivot.

Discussion

After partitioning, the pivot element ends up in its rightful position in the (eventually) sorted array. The implementation is linear time and in-place. The partition subroutine is an essential part of the Quicksort algorithm.

Implementation

The algorithm assumes the pivot is the first element in the array. This implementation does not come with loss of generality because if we want a different pivot, we just simply swap it with the first element.

We do a single linear scan and when we maintain two indices: i is the partition boundary- the split between smaller or equal than pivot and larger than pivot - in the section of the array containing the element we've seen so far, and j points to the section of the array we have not seen so far.

We maintain the following invariant: everything we looked at so far is already partitioned.

public static void partition(int[] a, int first, int last) {
    // fix the pivot
    int pivot = a[first];
    int i = first + 1;
    // linear scan over the rest of the array
    for(int j = first + 1; j <= last; j ++) {
        if (a[j] <= pivot) {
            // swap
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
            i ++;
        }
    }
    // place the pivot in the final position
    a[first] = a[i - 1];
    a[i - 1] = pivot;
}

Playground

https://github.com/ovidiuf/playground/blob/master/learning/stanford-algorithms-specialization/03-quicksort/src/main/java/playground/stanford/quicksort/Partition.java