1. Overview
The Quicksort algorithm operates on the foundational concept of divide and conquer, an elegant strategy for solving complex problems. When applying Quicksort to an array, this approach involves breaking down the array into smaller subarrays through the selection of a pivot point (pivot selection will be discussed in more detail later in this article).
The pivot serves as a reference point, determining the division of elements within the array. That is, elements that are smaller than the pivot are positioned to the left, while those greater than the pivot are placed to its right. This recursive process of partitioning and sorting leads to efficiently arranging the array’s elements in their proper order.
2. How Does Quicksort Work?
The first step is to select a pivot – an element that serves as a reference point for comparison. Although various implementations exist with distinct methods for choosing a pivot, common strategies involve selecting the first, last, or middle element.
Once the pivot is established, the array is divided into two subarrays: one for elements smaller than the pivot and another for elements greater than the pivot. It’s important to note that these subarrays are not entirely new arrays but partitions within the original array.
The algorithm then engages in recursion, a technique where a function calls itself on progressively smaller subarrays. This process continues until the subarrays become so small that further subdivision is unnecessary – often when the subarray size reaches one element. Indeed, an array containing only one element is inherently sorted.
As the recursive calls return, the subarrays are progressively merged back together. Consequently, elements are added to their right positions, effectively constructing the sorted array.
All of these operations are encapsulated within a method typically named ‘partition’. It’s important to note that the specific implementation of this method can vary depending on the chosen Quicksort algorithm. For instance, different partitioning schemes, such as the Lomuto Partition Scheme, the Hoare Partition Scheme, the Median-of-Three Partitioning, and Randomized Partitioning, offer diverse strategies for rearranging elements during the partitioning step.
3. Java Implementation of Quicksort
Bear in mind that Quicksort algorithms, like all algorithms, are language-independent. That is, they are not tied to any particular programming language. Instead, they rely on logical operations and mathematical functions to tackle specific problems. Naturally, the number of steps involved might vary based on the language used. Nonetheless, our Java implementation will provide you with a comprehensive understanding of the subject.
Let’s begin by introducing two methods: one (public
) that accepts an array of integers and another (private
) that takes the array along with its boundaries. This approach eliminates the necessity of passing three separate parameters, which can be error-prone, and instead simplifies the user’s interaction by only requiring the array as input.
// Allows us to call 'sort' by passing just the array, simplifying user interaction. public static void sort(int[] arr) { sort(arr, 0, arr.length - 1); } // Private method for sorting within a specific range. private static void sort(int[] arr, int start, int end) { // Base case to stop recursion. if (start >= end) return; // Rearrange the array based on the pivot and return the pivot index. int pivotIndex = partition(arr, start, end); // Partition method // Sort the elements to the left of the pivot. sort(arr, start, pivotIndex - 1); // Sort the elements to the right of the pivot. sort(arr, pivotIndex + 1, end); }
The code above lays the foundation of our sorting method. However, the heart of Quicksort lies within the partition
method. This is where the crucial division of elements occurs. In the context of this article, we will present you with two distinct implementations of the partition method: Hoare’s and Lomuto’s. Select the implementation that best aligns with your specific requirements.
3.1 Hoare’s Partition Method
Please note that, for the sake of simplicity, we will be selecting the last element as the pivot. However, it’s worth mentioning that there is an alternative approach advocated by some experts – randomizing the pivot selection and subsequently swapping it with the last element. Feel free to adapt this strategy as per your preferences.
Below, you will find an animation illustrating the Hoare’s partition in action. It displays the process until the point where two arrays split, initiating a repetition of the process for each of them.
Hoare’s Partition method, a key component of Quicksort, employs two pointers that converge towards each other. The left pointer scans for elements greater than the pivot, while the right pointer searches for elements smaller than the pivot. When a pair of such elements is found, they are swapped. This process continues until the pointers cross or meet. At that point, the pivot is positioned at its correctly sorted index, and the array is effectively partitioned into elements greater and smaller than the pivot.
3.1.1 Hoare’s Partition Implementation
private static int partition(int[] arr, int start, int end) { int pivot = arr[end]; int lp = start; // Left pointer int rp = end - 1; // Right pointer. -1 to skip the pivot. while (true) { // loops to increment lp & rp while conditions are true. while (arr[lp] <= pivot && lp < end) lp++; while (arr[rp] >= pivot && rp > start) rp--; if (lp < rp) { swap(arr, lp, rp); } if (lp >= rp) { swap(arr, lp, end); return lp; } } // End of while }
Keep in mind that the code above isn’t the shortest one and it does have some repetition, such as calling the swap method twice. And, although it is possible to avoid it, we opt to keep the code more readable and easier to follow for teaching purposes.
3.1.2 The Swap Method
Swapping is a fundamental part of the Quick Sort algorithm. While the concept itself is straightforward—exchanging the positions of two elements—it’s important to note that we’ve introduced a validation step to optimize our swapping process. This validation helps us avoid unnecessary swaps, improving the efficiency of the Quick Sort algorithm.
public static void swap(int[] arr, int firstIndex, int secondIndex) { if (firstIndex != secondIndex) { int temp = arr[firstIndex]; arr[firstIndex] = arr[secondIndex]; arr[secondIndex] = temp; } }
3.2 Lomuto’s Partition Method
Please note that, for the sake of simplicity, we will be selecting the last element as the pivot. However, it’s worth mentioning that there is an alternative approach advocated by some experts – randomizing the pivot selection and subsequently swapping it with the last element. Feel free to adapt this strategy as per your preferences.
Below, you will find an animation illustrating the Hoare’s partition in action. It displays the process until the point where two arrays split, initiating a repetition of the process for each of them.
Lomuto’s partition method exhibits a distinct approach compared to Hoare’s in terms of pointer manipulation. In Lomuto’s method, two pointers traverse the array from left to right, engaging in a sequence of element swaps based on the pivot. Eventually, the pivot itself is relocated into its rightful position through an additional swap. On the other hand, Hoare’s approach employs two pointers positioned at opposite ends of the array. These pointers facilitate the element swaps by evaluating their relation to the pivot, thereby segregating them to the left or right side of the pivot.
3.2.1 Lomuto’s Partition Implementation
private static int partition(int[] arr, int start, int end) { int pivot = arr[end]; int i = start - 1; for (int j = start; j < end; j++) { if (arr[j] < pivot) swap(arr, ++i, j); } swap(arr, ++i, end); return i; }
3.3 Running Results for Hoare’s and Lomuto’s Partitions
Upon executing the algorithm using both a ten-element fixed array and larger randomly generated arrays, we have obtained the following performance outcomes.
- Hoare’s Partition
- 10 elements – 161µs – 12 swaps.
- 100 elements – 221µs – 135 swaps.
- 1,000 elements – 437µs – 2,093 swaps.
- 10,000 elements – 4,159µs – 28,888 swaps.
- 100,000 elements – 26,394µs – 358,717 swaps.
- 1,000,000 elements – 357,310µs – 4,384,239 swaps
- 10,000,000 elements – 2,538,040µs – 51,580,038 swaps.
- 100,000,000 elements – 28,022,636µs – 591,002,189 swaps.
- 1,000,000,000 elements – java.lang.OutOfMemoryError.
- Lomuto’s Partition
- 10 Elements – 367µs – 9 swaps.
- 100 elements – 693µs – 329 swaps.
- 1,000 elements – 945µs – 6,050 swaps.
- 10,000 elements – 4,579µs – 74,030 swaps.
- 100,000 elements – 28,440µs – 971,946 swaps.
- 1,000,000 elements – 336,437µs – 10,889,577 swaps.
- 10,000,000 elements – 3,174,945µs – 141,080,209 swaps.
- 100,000,000 elements – 24,891,802µs – 1,607,631,185 swaps.
- 1,000,000,000 elements – java.lang.OutOfMemoryError.
Bear in mind that after executing those tests several times, we could observe that the number of swaps varied, but not much. However, the execution time varied considerably upon running the code many times in a row.
4. Generalization of the Quicksort Method to Accept Arrays of Classes.
Alternatively, we would like to provide an implementation where you could provide any array of classes, as long as they implement Comparable
. That is, we need to inform Java how it should perform this comparison. For instance, which fields should be used for comparison? In what order? Which ones should be left out?
Keep in mind that the String class and all wrapper classes already implement Comparable
. So, there is no need to implement it for those classes. Therefore, all you need to do for both sorting methods is to change their signatures and parameter type.
// Note that T extends Comparable<T> and our array is of type T[]. public static <T extends Comparable<T>> void sort(T[] arr) { sort(arr, 0, arr.length - 1); }
Then, for the private sorting method.
// Note that T extends Comparable<T> and our array is of type T[]. private static <T extends Comparable<T>> void sort(T[] arr, int start, int end) { if (start >= end) return; int pivotIndex = partition(arr, start, end); sort(arr, start, pivotIndex - 1); sort(arr, pivotIndex + 1, end); }
Also, we must change the partition method. Not only its signature and parameter type, but also some of its variables and comparisons. That is, we must compare using the compareTo
method instead of using the comparison operator directly.
4.1 Generalization of the Partition Method
Besides its signature, we only need to change three parts of the code. Firstly, the pivot
variable type to T
. Finally, in the two inner-while loops, the comparison is done by directly comparing the array content with the pivot using a comparison operator. However, we cannot compare classes using comparison operators, we must use the compareTo
method from Comparable
. Then, compare the resulting value to determine whether it is greater than zero, less than zero, or equal to zero.
// Note that T extends Comparable<T> and our array is of type T[]. private static <T extends Comparable<T>> int partition(T[] arr, int start, int end) { // Note that the pivot variable is of type T as well. T pivot = arr[end]; int lp = start; int rp = end - 1; // Finally, we must modify both while loops comparison expressions. while (true) { // Note that here we invoke the compareTo method and check whether // it returns a result greater than 0, less than 0, or equals 0. while (arr[lp].compareTo(pivot) <= 0 && lp < end) lp++; while (arr[rp].compareTo(pivot) >= 0 && rp > start) rp--; if (lp < rp) swap(arr, lp, rp); if (lp >= rp) { // Note that the swap method also requires modification. swap(arr, lp, end); return lp; } } // End of while(true) }
4.2 Generalization of the Swap Method
Finally, we have the swap
method, which is simple, yet a crucial component in this algorithm.
// Note that T extends Comparable<T> and our array is of type T[]. public static <T extends Comparable<T>> void swap(T[] arr, int firstIndex, int secondIndex) { if (firstIndex != secondIndex) { T temp = arr[firstIndex]; // Note that the pivot variable is of type T as well. arr[firstIndex] = arr[secondIndex]; arr[secondIndex] = temp; } }
5. Conclusion
So, now you’re equipped to implement Quicksort in Java using both Hoare’s and Lomuto’s partition methods. You have a solid understanding of how to apply them to primitives or any array of classes. If you’re eager to dive deeper and access the source code, along with more valuable content like this, don’t hesitate to visit our GitHub page.
6. Further Considerations
Having learned how to apply a generalization to Hoare’s partition, it’s time to tackle Lomuto’s partition. Feel free to take on this new challenge to broaden your understanding of how to adapt sorting algorithms for various scenarios. Also, if you like learning about algorithms, do not forget to check our article on Insertion Sort and Shell Sort.