Sorting algorithms, such as quicksort, are indispensable when preparing for a technical interview as a software developer. Partitioning is a crucial part of the quicksort algorithm and can be implemented in several ways. Software engineers need to know the various ways in which algorithm implementations can be altered and customized to be best suitable for meeting the space and time constraints of any problem. 

Coding engineers who direct their interview prep to master this skill will be preferred candidates over those who don’t. This article will discuss two ways of partitioning we can use while implementing quicksort, compare their merits and demerits, and the best use cases for the two.

If you need to, it will be helpful to revisit quicksort before reading ahead. Essentially, quicksort involves repeatedly partitioning an array into two sub-arrays based on a pivot element. The goal is to have numbers less than the pivot to its left and the numbers greater than the pivot to its right, ensuring that the pivot is at its rightful place. Numbers equal to the pivot can go either way. The subarrays to the left and right aren’t sorted, and the same quicksort algorithm is run on the subarrays until the subarray contains only one element and the input array is fully sorted. 

In this article, we’ll discuss:

• What Is the Hoare Partition Algorithm?
• Hoare's Partition Scheme  Example
• What Is the Lomuto Partition Algorithm?
• Lomuto’s Partition Scheme Example
• Comparison Between Hoare’s and Lomuto’s Partition
• Tech Interview Problems and Questions on Hoare’s vs. Lomuto’s Partition
• FAQs on Hoare’s vs. Lomuto’s Partition

What Is the Hoare Partition Algorithm? 

Tony Hoare invented quicksort and also developed the Hoare’s partitioning algorithm. Hoare’s partition involves having a pivot element and two indexes: one index at the start of the array and the other at its end. A pivot element can be anything in theory, but we typically use the first element as the pivot for Hoare’s Partition Algorithm. 

Ideally, we want a pivot that is the middle value, so the array is evenly partitioned to ensure optimal efficiency. These two indexes move towards each other from opposite ends till the inversion criterion is met. Let’s break it down: 

• We say that an inversion is detected when a pair of elements, one greater than the pivot and one smaller than the pivot element (at start index and end index, respectively), is found to occur in the wrong order relative to each other. 
• These two elements at the start and end index are then inter-changed, and the process continues as long as the start index <= end index holds. 
• Once the start index moves past and becomes greater than the end index, the values at the end index and the pivot element are swapped. The pivot element is now at the end index, which also represents its rightful place. (When we swap the value at endIndex with pivot element, we are storing the pivot element at the location endIndex points to.) This process continues till the sorting is complete. 

Hoare's Partition Scheme Example

We’ll now look at the pseudocode for Hoare’s partition scheme with the help of an example:

Pseudocode for Hoare's Partition Scheme

partition(inputHoare[], lowerboundIndex, upperboundIndex)

   pivot = inputHoare[lowerboundIndex]

   // Initializing the start and end index

   startIndex = lowerboundIndex - 1  

   endIndex = upperboundIndex + 1  

   while (true) 

    {

   // Finding a value from the left that’s greater

   // than or equal to the pivot element

   do

      startIndex++ 

   while inputHoare[startIndex] < pivot

   // Finding a value from the right that’s smaller

   // than or equal to the pivot element

   do

      endIndex--; 

   while (inputHoare[endIndex] > pivot);

   if startIndex >= endIndex  

     { return endIndex }

   //If start index has not met or crossed end index, we’ve 

   //found an inversion and need to swap the values in them.

   swap inputHoare[startIndex] with inputHoare[endIndex]

}

Example

Step 1: Start index and end index are at the beginning and end of the array, respectively. We’ve taken the first element as the pivot. We find that for the start index, 5 is the first element from the left that isn’t less than the Pivot; it’s equal. We also find that for the end index, 3 is the first element from the right that is less than the pivot. Our start and end indexes hence move and stop at 5 and 3, respectively. We’ve detected an inversion.

Step 2: Values 5 and 3 are swapped to correct this inversion. Start index now points at 3. End index points at 5. We detect that 9 is the next element from the left that is not less than the pivot. We also see that 5 is the next element from the right that is not greater than the pivot. 

Step 3: We move and stop our start index at 9, and the end index stops at 5. We swap the two values as we’ve detected an inversion. The start index now contains 5, the pivot, and the end index contains 9.

Step 4: We now find that 5 is the next element from the left that is not less than the pivot (5). And 5 is also the next element from the right that is not greater than the pivot (5). Our start index and end index both move to and stop at 5. We find that the start index and end index have met or crossed each other. This is not an inversion; we now do not need to swap. We stop the process.

Step 5: Finally, we swap the value at the end index with the pivot. (It doesn’t mean much in this call, as the end index already points to the pivot 5, but it could matter in future calls, where that’s not the case.) We then return the end index, which contains the pivot. Elements to the left of the pivot are now smaller than it, and those at the right are larger.

Step 6: The same process is applied to the subarrays to the left of the pivot and right of it. The left half of the subarray for Hoare’s partition scheme also includes the pivot element, unlike in Lomuto’s partition example. This process is done till only one element remains, in which case, the pivot element is already at the end index, which is returned. This leads to the array finally being sorted in place.

What Is the Lomuto Partition Algorithm?

In Lomuto’s partition, the pivot element is typically chosen to be the last element. Once sorted in its rightful place, this pivot element is no longer considered a participant in the subsequent recursive calls for subarrays.

• The process involves starting from the leftmost element as the current index. Whenever an element < pivot is encountered, we increment the current index. 
• We then swap the smaller-than-pivot element we’ve found with the element at the current index. This process continues for all elements. 
• Finally, the pivot element and the element at the current index at the end of this process are swapped. 
• This process places elements smaller than the pivot to its left, greater elements to it at its right. 
• It then returns the current index, which is now the index of the pivot at its sorted position. Note that this is different from Hoare’s partitioning, where the pivot element isn’t necessarily at its sorted place; hence we include the pivot in subsequent recursive calls in Hoare’s partitioning, but we don’t need to for Lomuto’s partitioning.

Lomuto Partition Scheme Example

Let us now look at the pseudocode for Lomuto’s scheme and try to understand this better through an example.

Pseudocode for Lomuto Partition Scheme

LomutoPartition(Array, lowerboundIndex, upperboundIndex)

pivot = Array[lowerboundIndex]

//currentIndex stores the position to swap with

currentIndex = lowerboundIndex 

for( i= lowerboundIndex+1; i<upperboundIndex;i++)

{

   If (Array[i]<pivot)

  {

    currentIndex++;

    swap(Array[i], Array[currentIndex]);

  }

}

  swap(pivot, Array[currentIndex])

  return currentIndex;

}

Example

Let us look at how Lomuto’s partition scheme works using an example:

Input Array: 5, 4, 9, 8, 3, 7

Step 1: Current index and pivot are at the beginning. Index i is at 4, which is also less than the pivot element. Any time we find that the element at i is less than the Pivot element, we increment the current index and swap the values at the current index and index i.

Step 2: We’ve found that the element at i is less than the Pivot, but current and i represent the same index, so swapping causes no change in this step. We notice that the index i should move to 3 as it is the next element less than the pivot.

Step 3: Index i has moved to element 3, and the current index has been incremented yet again after this find.

Step 4: Values at current index and index i are swapped. This time, since the indexes point to different locations, change occurs in the order.

Step 5: i reaches the end of the array; there are no more elements further that are less than the pivot. Now the element finally at the current index is swapped with the pivot. The current index is then returned, which now holds the pivot in its sorted place. The elements to the left of the pivot now are less than it, and elements on the right of the pivot are greater than it.

Step 6: The same procedure is followed for the sub-arrays to the left and right of the pivot index we just returned (current index) till only one element is left. In that case, the current index and pivot index are already the same, and that current index is returned. This finally leads to the array being sorted in place.

Implementation of Hoare’s and Lomuto’s Partition Scheme 

We’ve implemented Hoare’s and Lomuto’s partition schemes in C++. Use this as a reference to implement them in a programming language of your choice.

#include <iostream>

using namespace std;

//Partitioning using Hoare's partition scheme.

int partitionHoare(int inputHoare[], int lowerboundIndex, int upperboundIndex)

{

    int pivot = inputHoare[lowerboundIndex];

    int startIndex = lowerboundIndex - 1;

    int endIndex = upperboundIndex + 1;

    while (true) 

     {

        // Finding the first element from the left that's greater than or 

        // equal to the pivot.

        do 

        {

            startIndex++;

        } while (inputHoare[startIndex] < pivot);

        // Finding the first element from the right that's element smaller 

        // than or equal to the pivot.

        do {

            endIndex--;

        } while (inputHoare[endIndex] > pivot);

        // If the left index and right index meet or cross each other, 

        // partition returns the index of the right index that now 

        // represents a smaller index than the left index. That is, it

        // returns the endIndex.

        if (startIndex >= endIndex)

            return endIndex;

        // If start and end index have not met or crossed each other, we've 

        // found an inversion so we swap the two values.

        swap(inputHoare[startIndex], inputHoare[endIndex]);

    }

}

//Implementing quick sort using Hoare's partition.

void quickSortHoare(int inputHoare[], int lowerboundIndex, int upperboundIndex)

{

    if (lowerboundIndex < upperboundIndex) {

        //Partitioning puts the element inputHoare[partitionIndex] at its 

        //rightful place.

        int partitionIndex = partitionHoare(inputHoare, lowerboundIndex, upperboundIndex);        

        // Sorting the subarray till the partition element. It contains  

        // elements lower than the partition element.

        quickSortHoare(inputHoare, lowerboundIndex, partitionIndex);

        // Sorting the subarray after the partition element. It contains 

        // elements larger than the partition element.

        quickSortHoare(inputHoare, partitionIndex + 1, upperboundIndex);

    }

}

// Lomuto’s partition C++ code.

// Partitioning using Lomuto's partition scheme.

int partitionLomuto(int inputLomuto[], int lowerboundIndex, int upperboundIndex)

{

    // Taking the upperbound index as pivot.

    int pivot = inputLomuto[upperboundIndex];    

    int smallerElementIndex = lowerboundIndex - 1; 

    for (int currentIndex = lowerboundIndex; currentIndex <= upperboundIndex- 1; currentIndex++)

    {

        // If the current element is less than or equal to the pivot.

        if (inputLomuto[currentIndex] <= pivot)

        {

            smallerElementIndex ++;    

            swap(inputLomuto[smallerElementIndex], inputLomuto[currentIndex]);

        }

    }

    // Placing the pivot element inputLomuto[upperboundIndex] at its 

    // rightful position smallerElementIndex  + 1.

    swap(inputLomuto[smallerElementIndex  + 1], inputLomuto[upperboundIndex]);

    // Returning the index of the pivot element at its rightful place.

    return smallerElementIndex + 1;

}

// Implementing quick sort using Lomuto's partition scheme.

void quickSortLomuto(int inputLomuto[], int lowerboundIndex, int upperboundIndex)

{

    if (lowerboundIndex < upperboundIndex)

    {

        // Partitioning puts the element inputLomuto[partitionIndex] at its    

        // rightful place.

        int partitionIndex = partitionLomuto(inputLomuto, lowerboundIndex, upperboundIndex);

        // Sorting the subarray before the partition element. It contains 

        // elements lower than the partition element.

        quickSortLomuto(inputLomuto, lowerboundIndex, partitionIndex - 1);

        // Sorting the subarray after the partition element.It contains 

        // elements larger than the partition element.

        quickSortLomuto(inputLomuto, partitionIndex + 1, upperboundIndex);

    }

}

// Function to print an array, just to avoid repeated code for printing 

// arrays.

void outputArray(int array[], int arraySize)

{

    for (int index = 0; index < arraySize; index++)

        cout<< array[index]<<" ";

        cout<<"\n";

}

int main()

{

// Using the same input for both: Quicksort using Hoare's and Lomuto's

// partition.

    int inputHoare[] = { 5, 4, 9, 8, 3, 7}; 

    int inputLomuto[]= { 5, 4, 9, 8, 3, 7}; 

    int inputSize = 6;

    // Quick sorting the input array using Hoare's partition scheme, which 

    // sorts it in place.

    quickSortHoare(inputHoare, 0, inputSize - 1); 

    cout<< "Quicksort using Hoare's partition gives: \n";

    // Printing the in place sorted array.

    outputArray(inputHoare, inputSize); 

    // Quick sorting the input array using Lomuto's partition scheme, which 

    // also sorts it in place.

    quickSortLomuto(inputLomuto, 0, inputSize - 1);

    cout<< "Quicksort using Lomuto's partition gives: \n";

    // Printing the in place sorted array.

    outputArray(inputLomuto, inputSize);

    return 0;

}

Output

As expected and discussed in the case of both partition methods, the output of the code is the same: the input array sorted in ascending order.

Quicksort using Hoare's partition gives: 
3 4 5 7 8 9 

Quicksort using Lomuto's partition gives: 
3 4 5 7 8 9

Comparison between Hoare’s vs. Lomuto’s partition

Tech Interview Problems and Questions on Hoare’s vs. Lomuto’s Partition

1. Implement quicksort using Hoare’s as well as Lomuto’s partition scheme in Python/Java/C.
2. Implement and show the difference between Hoare’s and Lomuto’s partition schemes for quicksort in the language of your choice.
3. What is the difference between Hoare’s and Lomuto’s partition schemes?
4. Analyze quicksort’s implementation when using Hoare’s partition scheme vs. Lomuto’s partition scheme.
5. Which partitioning scheme for quicksort would you use if the efficiency of partitioning was of utmost importance?

FAQs on Hoare’s vs. Lomuto partition ( 3 Questions and Answers)

Question 1: What is common in Hoare’s and Lomuto’s partition scheme?

Answer: Both partition schemes achieve the same goal of partitioning the array into two subarrays based on a pivot element, where elements to the left of the pivot are less than it, and elements to the right of the pivot are greater than it. The subarrays themselves aren’t sorted, but the pivot element is at its rightful position at the end of the process.

Question 2: What is the pivot supposed to be in Hoare’s and Lomuto’s partition scheme?

Answer: There is no strict rule about choosing the pivot element. However, Lomuto’s partition scheme typically uses the last element as the pivot for its implementation. Hoare’s partition scheme typically involves using the first element as the pivot for its implementation.

Question 3: When should we prefer Hoare’s partition scheme over Lomuto’s partition scheme (and vice versa)?

Answer: When the efficiency of the partition is paramount, Hoare’s should be preferred over Lomuto’s as it has a better performance and efficiency in comparison. When the efficiency gain by using Hoare’s over Lomuto’s isn’t significant, it may be preferable to implement Lomuto’s partition scheme than to implement Hoare’s. The reason for this preference is that Lomuto’s partition uses a single pointer i, while Hoare’s uses two. The implementation may be simpler and easier to understand if Lomuto’s partition is used in such cases.

Recommended Reading

• Google Interview Questions 
• Facebook Interview Questions 
• The Hardest and Easiest Programming Languages to Learn for FAANG Interviews
• Best Tech Companies to Work With in 2021

Are You Ready to Nail Your Next Coding Interview?

If you’re looking for guidance and help with getting your prep started, sign up for our free webinar. As pioneers in the field of technical interview prep, we have trained thousands of software engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!

Sign up now!

----------

Article contributed by Tanya Shrivastava