In this article, we have explained Hoare Partition Scheme/ Algorithm in depth. This algorithm is widely used to partition an array into two parts based on a condition and is used in Quick Sort algorithm.

Table of content:

1. Introduction to Hoare Partition
2. Algorithm of Hoare Partition
3. Example: Dry Run of Hoare Partition
4. Implementation of Hoare Partition
5. Time & Space Complexity of Hoare Partition

Let us get started with Hoare Partition.

Introduction to Hoare Partition

Hoare partition is an algorithm that is used to partition an array about a pivot. All elements smaller than the pivot are on it's left (in any order) and all elements greater than the pivot are on it's right (in any order).

Quicksort algorithm uses hoare paritition to partition the array. Check out this article to more about it.

Few widely used partition algorithms include:

• Naive partition
• Lomuto partition
• Hoare partition

The partition algorithm is chosen based on the expected time and space complexity as well as the degree of randomness of the array (If tentatively known because some algorithms work better for sorted arrays while others do not.)

Note that, Hoare's partiiton returns the correct index of the chosen pivot in the array, but does not put the element at the correct place. Do take a look at the Time complexity section for a detailed discussion on this.

Algorithm of Hoare Partition

While partitioning arrays using Hoare Partition scheme, we make an assumption:
The pivot element is always the first element of the array.

1. Initialize two pointers L and H where L is for the element at the smallest index and the other, H is for the element at the highest index.
2. The pivot is the element at the smallest index.
3. Do this:
   3.1 Keep increasing L while arr[i] < pivot.
   3.2 Keep decreasing H while arr[j] > pivot.
   3.3 If i >= j, return j.

Example: Dry Run of Hoare Partition

Given an array, arr = [5,3,8,4,2,7,1,10]

• l = 0, h = 7
• pivot = arr[l] = 5
• i = l-1 = -1
• j = h+1 = 8

Now,

• while arr[i] < pivot, i++. This results in i = 0

• while arr[j] > pivot, j--. This results in j = 6
  Swap arr[0] and arr[6] => arr = [1,3,8,4,2,7,5,10]

• while arr[i] < pivot, i++. This results in i = 2

• while arr[j] > pivot, j--. This results in j = 4
  Swap arr[2] and arr[4] => arr = [1,3,2,4,8,7,5,10]

• while arr[i] < pivot, i++. This results in i = 4

• while arr[j] > pivot, j--. This results in j = 3
  However, as i >= j, return j=3

Implementation of Hoare Partition

Following is the implementation of Hoare Partition in Java:

public static int partition(int arr[], int l,int h)   // Initially, l = 0, h = size of array - 1
{
    int pivot = arr[l];

    int i = l-1, j = h+1;
    while(true)
    {
        do
        {
            i++;
        } while(arr[i] < pivot)
        do
        {
            j--;
        } while(arr[j] > pivot)

        if(i >= j)
            return j;
        swap(arr[i], arr[j]);
    }
    return -1;
}

Following is the implementation of Hoare Partition in C++:

int partition(int arr[], int l,int h)   
// Initially, l = 0, h = size of array - 1
{
    int pivot = arr[l];

    int i = l-1, j = h+1;
    while(true)
    {
        do
        {
            i++;
        } while(arr[i] < pivot)
        do
        {
            j--;
        } while(arr[j] > pivot)

        if(i >= j)
            return j;
        swap(arr[i], arr[j]);
    }
    return -1;
}

Time & Space Complexity of Hoare Partition

We traverse the array exactly once, the time complexity is O(N). This algorithm is said to be almost 3 times faster than Lomuto paritioning.

Lomuto partitioning is also a O(N) time complexity, O(1) space complexity algorithm and does the work in just one array traversal like hoare's partition but Lomuto partition requires more swaps and hence is relatively inefficient in this respect. However, Lomuto partition puts the pivot at the correct position in the array as well as returns the index whereas Hoare's partition only returns the correct index of the pivot.

Space Complexity
The algorithm does not use any auxiliary space, hence space complexity is O(1).

With this article at OpenGenus, you must have the complete idea of Hoare Partition. Enjoy.