Hoare's Partition

Problem Solved

Hoare's Partition solves the Array Partition problem.

Example

Here is an example of how partition might perform on a small array, with the assumption that the first element is the desired pivot.

Design and Strategy

Hoare’s Partition begins by selecting a pivot element, typically A[low]. It uses two pointers, i and j, to traverse the array. Pointer i starts at low + 1, and pointer j starts at high. The pointer i increments until it finds an element greater than the pivot (A[i] > pivot), and pointer j decrements until it finds an element less than the pivot (A[j] < pivot). When both out-of-place elements are identified, the algorithm swaps A[i] and A[j], and then increments i and decrements j. This process repeats until i ≥ j. Finally, the pivot element A[low] is swapped with A[j], placing the pivot correctly at index j. The partition index j is then returned.

Here is a step-by-step description.

1. Select the pivot element, typically A[low].
2. Initialize two pointers:
   • i = low + 1
   • j = high
3. Repeat the following steps until i ≥ j:
   • Move pointer i forward until A[i] > pivot.
   • Move pointer j backward until A[j] < pivot.
   • If i < j, swap A[i] and A[j], then increment i and decrement j.
4. Finally, swap the pivot element A[low] with A[j].
5. Return the pivot index j.

Hoare’s algorithm kind of exemplifies the decrease-and-conquer paradigm since as the pointers i and j move inward, elements are progressively placed into their correct positions at the array's left and right portions, shrinking the unsorted middle section with each iteration. Thus, the size of the unsolved portion decreases with each iteration. But generally speaking, it is difficult to categorize on its own. Because it is used in Quick Sort, which is a divide-and-conquer algorithm and Quick Select, which is a decrease-and-conquer algorithm, I put it in the decrease-and-conquer category.

Implementation in Java, C++, Python

Here is one implementation of Hoare's Partition algorithm. There are many slight variations of the algorithm, so do not be surprised if you see versions that do not match this one exactly.

int partition(int[] A, int lo, int hi) {
    int p = A[lo];
    int i = lo + 1;
    int j = hi;
    while (true) {
        while (i < hi && A[i] <= p) i++;
        while (j > lo && A[j] >= p) j--;
        if (j <= i) {
            swap(A, lo, j);
            return j;
        } else {
            swap(A, i, j);
            i++;
            j--;
        }
    }
}

void swap(int[] A, int i, int j) {
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

int partition(int A[], int lo, int hi) {
    int p = A[lo];
    int i = lo + 1;
    int j = hi;
    while (true) {
        while (i < hi && A[i] <= p) i++;
        while (j > lo && A[j] >= p) j--;
        if (j <= i) {
            swap(A, lo, j);
            return j;
        } else {
            swap(A, i, j);
            i++;
            j--;
        }
    }
}

void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

def partition(A, lo, hi):
    p = A[lo]
    i = lo + 1
    j = hi
    while True:
        while i < hi and A[i] <= p:
            i += 1
        while j > lo and A[j] >= p:
            j -= 1
        if j <= i:
            swap(A, lo, j)
            return j
        else:
            swap(A, i, j)
            i += 1
            j -= 1

def swap(A, i, j):
    A[i], A[j] = A[j], A[i]

Time/Space Analysis

Time Complexity: The algorithm consistently operates in linear time, O(n), because it involves two pointers traversing the array from opposite ends, moving toward each other until they cross. Each time a pointer moves, a constant number of operations is executed.

Compared to other partitioning methods like Lomuto’s scheme, Hoare's algorithm typically involves fewer swaps and fewer overall operations. Its efficiency arises from the bidirectional scanning of the array and performing swaps only when necessary.

Space Complexity: Hoare’s Partition algorithm operates in-place, requiring only constant additional space, O(1). The algorithm does not need auxiliary arrays or additional significant memory beyond a few pointers and temporary variables.

Variations/Improvements

• Equal Elements: Different implementations may treat elements that are equal to the pivot differently, and how they do so can affect the performance. Thus, when dealing with arrays where many duplicates are expected, careful thought is needed to choose the best varition.
• Lomuto Partition Scheme: An alternative partitioning method where the pivot is typically the last element. It maintains three distinct regions: elements smaller than the pivot, elements greater than or equal to the pivot, and an unknown region yet to be examined. A single pointer moves forward to manage these regions, placing smaller elements in the correct region. The algorithm is slightly more complicated conceptually than Hoare's Partition, and it tends to perform more swaps.
• Randomized Pivot Selection: Instead of always choosing the first or last element as the pivot, this approach selects a pivot randomly from the range, swapping it with the first element at the beginning. This can be useful in cases where you want to increase the likelihood of the pivot being closer to the center (especially if the array is sorted or mostly sorted), which increases the efficiency of certain algorithms that use partitioning (e.g. Quicksort, Quickselect).
• Median-of-Three Pivot: A refinement that picks the pivot as the median of the first, middle, and last elements. Like random pivot selection, this heuristic often yields better-balanced partitions.
• Three-Way Partitioning: Useful when dealing with arrays containing many duplicate values. This strategy partitions the array into three parts: less than pivot, equal to pivot, and greater than pivot. It enhances performance by reducing redundant comparisons.

Links to Resources

• Wikipedia: Quicksort (includes Hoare partition)
• GeeksforGeeks: Hoare's vs Lomuto Partition Scheme

Reading Comprehension Questions

1. What is the role of the two pointers i and j in Hoare's Partition algorithm?
2. Why does Hoare’s Partition algorithm swap between the pivot and A[j] at the end?
3. In what way is Hoare’s Partition an example of the decrease-and-conquer strategy?
4. What are the best and worst time complexities of Hoare's Partition?
5. Why might 3 be a bad pivot value for the array [3,34,93,68,4,49,24,32,23,88,49]?
6. Given the array [7, 4, 9, 6, 2, 8, 3] with low = 0 and high = 6, apply Hoare's Partition with the pivot as the first element. What does the array look like after partitioning, and what is the returned pivot index?

In-Class Activities

1. Go over a few examples of Hoare's Partition algorithm.
2. Explains the scenarios of what bad and good pivot values might look like and discuss why.
3. Go over some techniques that can be used to avoid getting bad pivoting values, such as random pivot values and median of three.
4. Go over the difference between the Hoare's and Lomuto partitioning algorithms.
5. Provide students with an unsorted array and have them manually trace through Hoare’s Partition step-by-step.

Problems

1. Implement Hoare's Partition in your chosen programming language. Generate and test arrays with:
   • Random pivots
   • Pivots chosen using the median-of-three method
   Compare performance (swaps, comparisons) across multiple arrays of varying sizes.
2. Given the array [34, 23, 54, 21, 11, 45, 67, 89, 10], perform Hoare’s Partition step-by-step. Count and document each swap and comparison made.
3. Describe a scenario where Hoare’s Partition significantly outperforms Lomuto’s scheme and explain why.
4. Provide a detailed walkthrough of Hoare's Partition using an array of your choice (minimum of 8 elements), clearly marking pivot movements, pointer updates, swaps, and final partition index.