Pranav Kasetti

Why make this post?

Solving Algorithm questions takes practice, and problem-solving skills. Algorithms is a vast topic, so that's why it's my strategy to hone the fundamental concepts in Algorithms theory. I think that I can use my knowledge bank to solve harder problems by nailing the foundation, or solve similar questions.

In this post, I dive into the Hoare and Lomuto QuickSort partitioning schemes. I've decided to blog about it because QuickSort is included in the foundation material across most Algorithms courses. In this post however, I add variations for stability, in-place and optimal partitioning. QS is a complex topic, but is very useful across a variety of problems. I focus here on the core of the algorithm, and add discussion rather than re-implementing the sort.

Paradigm for partitions

If you've done an algorithms course at University level, you will probably hear about a paradigm called: "Divide and Conquer".

"Divide and Conquer" is an algorithmic solving approach that I describe as:

1. Divide the input. ("Divide")
2. Solve the problems with smaller inputs. ("Conquer")
3. Gather the subproblem solutions to solve the original problem.

I find the Divide and Conquer paradigm highly useful across a variety of problems, beyond sorting. I usually divide the input in half, and this is also how Binary Search solves efficient lookup.

Partitioning by definition divides the input, so it's natural that D&C is relevant for Hoare + Lomuto.

QuickSort description (for context)

For those of you who are new to QuickSort, let's quickly walk through how QuickSort works (for context).

1. Choose a pivot in the array. Randomized QuickSort chooses the pivot at a random index and swaps this with the initial array index. Randomized QuickSort is more efficient than regular QuickSort across more input combinations.
2. Partition the array into two halves where the first half has all values with value < pivot, and the second half has all values with value > pivot.
3. Combine the two halves with the pivot in the middle.
4. Repeat steps 1-3 on each half (excluding the pivot).

We won't focus on outlining QuickSort because this has been well covered in other blog posts and online courses. Instead, I focus on exploring the Partitioning code because this is the essential solution to the sorting problem.

Partition description

We are focusing here on step 2 of QuickSort. i.e.

Partition the array into two halves where the first half has all values with value < pivot, and the second half has all values with value > pivot.

We only perform the partitioning function once here, however, to fully partition the code we would have to recursively call the partition for each half.

We can either implement the partitioning scheme as in-place or not. In-place means that we modify the original array rather than returning new array(s).

We also consider sorting algorithms to be stable if the relative order of equal elements is preserved after the algorithm.

1. Hoare can be modified to be in-place, but isn't stable.
2. Lomuto can be stable with a 3-way partition and also be completed in-place.

In-place is the preferred variant for these methods to optimise space complexity. Stability is often a trade-off for high efficiency.

Hoare Partition

Hoare partitions the array into two halves using fewer swaps than Lomuto.

Hoare also uses 2 pointers. One points to the rightmost value in the first partition and one to the leftmost value in the second partition.

While the left pointer is less than the right pointer, we keep swapping pairs of misplaced values. The algorithm works because of symmetry. For every mislocated value in the left partition, there is a corresponding mislocated value in the right partition. Hoare is intuitive, however we lose stability with higher efficiency.

Hoare Code (randomized)

extension Array where Element == Int {
  mutating func hoarePartition() {
    // Step 1
    let random = Int.random(in: indices)
    swapAt(random, startIndex)
    var left = startIndex + 1
    var right = endIndex - 1
    // Step 2
    while left <= right {
      while self[left] < self[pivot] {
        left += 1
      } 
      while self[right] >= self[pivot] {
        right -= 1
      }
      swapAt(left, right)
      left += 1
      right -= 1
    }
    swapAt(startIndex, right)
  }
}

Best Case Time Complexity: O(N)

Average Case Time complexity: O(N)

Worst Case Time Complexity: O(N)

Space Complexity: O(1)

Lomuto Partition

The main idea behind Lomuto is to iterate through the array, and keep track of the rightmost value of the left partition. When we encounter a value not in the left partition already but less than the pivot, we increment the left pointer and swap the two values.

We can further optimize Lomuto with a 3-way partition to improve the efficiency of Lomuto further for specific inputs as well as make the algorithm stable.

Let's cover 2-way Lomuto first.

Lomuto Code (2-way randomized)

extension Array where Element == Int {
  mutating func lomutoPartition() {
    guard !self.isEmpty else {
      return []
    }
    // Step 1
    let random = Int.random(in: startIndex, endIndex)
    self.swapAt(startIndex, random)
    let pivot = startIndex
    var left = startIndex
    // Step 2
    for i in (startIndex + 1) ..< endIndex {
      if self[i] <= self[pivot] {
        left += 1
        swapAt(i, left)
      }
    }
    swapAt(startIndex, left)
  }
}

Best Case Time Complexity: O(N)

Average Case Time complexity: O(N)

Worst Case Time Complexity: O(N)

Space Complexity: O(1)

The changes between 2-way and 3-way complexities is found in the Gather step 3 of QS rather than Lomuto.

Lomuto Code (3-way randomized)

The above code can be easily modified with a third partition containing only values that equal the pivot. This ensures stability of the partitioning code. We use an additional pointer to track the rightmost value within a middle partition.

Swapping a value from the right partition with the middle partition is the same logic as the 2-way partition algorithm from above. We also need additional logic for 3-way partitioning to increment the middle partition pointer when swapping a value from the right partition to the left partition. We achieve this via 2 swaps from the right to the middle and then from the middle to the left partitions.

extension Array where Element == Int {
  mutating func lomutoPartition() {
    guard !self.isEmpty else {
      return []
    }
    // Step 1
    let random = Int.random(in: startIndex, endIndex)
    self.swapAt(startIndex, random)
    let pivot = self.startIndex
    var left = startIndex - 1
    var mid = startIndex - 1
    // Step 2
    for i in (startIndex + 1) ..< endIndex {
      if self[i] < self[pivot] {
        mid += 1
        swapAt(i, mid)
        left += 1
        swapAt(mid, left)
      } else if self[i] == self[pivot] {
        mid += 1
        swapAt(i, mid)
      }
    }
    swapAt(startIndex, mid + 1)
  }
}

Best Case Time complexity: O(N)

Average Case Time complexity: O(N)

Worst Case Time Complexity: O(N)

Space Complexity: O(1)

Summary

QuickSort divides and conquers the problem of sorting efficiently as well as with stability (Lomuto 3-way). The same technique of partitioning can be useful in a wide variety of contexts outside QS.

There are multiple partitioning schemes available, and these may be useful for different situations depending on whether we want stability or efficiency.

Partial sorts are useful for problems where we don't need a fully sorted array, but only want the position of a particular pivot value in the sorted output.

Happy coding! :D