One post tagged with "quicksort"

This article explores the implementation of the QuickSort algorithm using Hoare's Partitioning scheme. While slightly more challenging to implement, this partitioning approach proves more efficient than Lomuto's scheme, performing three times fewer swaps on average [Wikipedia].

Algorithm Complexity​

• Average Time Complexity: O(n log n)
• Worst Time Complexity: O(n²)
• Space Complexity: O(1)

Understanding Hoare Partition Intuitively​

The key distinction between Hoare and Lomuto partitioning schemes lies in their approach to array division. As explained by Kartikey Gupta on StackExchange:

Lomuto divides the array into three parts: elements smaller than the pivot, the pivot itself, and elements greater than the pivot. Hoare takes a different approach by dividing the array into two parts: elements smaller than the pivot, and elements equal to or greater than the pivot.

A common misconception arises from the fact that Lomuto's partition returns the final position of the pivot, whereas Hoare's partition returns the position just before the final position of the pivot. This explains why Lomuto quicksorts from lo to p-1, while Hoare quicksorts from lo to p.

Implementation in Java​

Here's a complete implementation of QuickSort using Hoare's partitioning scheme:

public class QuickSortHoare {
    int[] arr;
    
    public QuickSortHoare(int[] arr) {
        this.arr = arr;
    }

    private void sort(int i, int j) {
        if (i < j) {     
            int p = partition(i, j);
            sort(i, p);
            sort(p + 1, j);
        }
    }

    private void sort() {
        sort(0, arr.length - 1);
    }
    
    private int partition(int left, int right) {
        int pivot = (left + right) / 2;
        int pivotValue = arr[pivot];
        int i = left - 1;
        int j = right + 1;
        
        while (true) {
            do {
                i++;
            } while (arr[i] < pivotValue);
            
            do {
                j--;
            } while (arr[j] > pivotValue);

            if (i < j) {
                swap(i, j);
            } else {
                return j;
            }
        }
    }

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

Key Implementation Details​

1. The partition method uses the middle element as the pivot
2. Two pointers (i and j) move towards each other until they find elements that are on the wrong side
3. The algorithm swaps elements when both pointers find elements to swap
4. The process continues until the pointers meet or cross each other

Additional Resources​

For more information about Hoare's partitioning scheme, check out Michael Cotterell's implementation. Note that his version returns the low pointer from partitioning, requiring recursive sorting on [low: partition-1] and [partition+1: high] intervals.

Conclusion​

Hoare's partitioning scheme offers a more efficient approach to QuickSort implementation, despite its slightly more complex nature. Understanding the key differences between Hoare and Lomuto partitioning schemes is crucial for implementing and optimizing sorting algorithms in practice.