Quick Sort
Quick Sort is also an algorithm based on divide and conquer, similar to Merge Sort. We select an element from the array called the pivot. The array is then rearranged so that all elements smaller than the pivot are placed to its left, and all elements greater are placed to its right. At this point, the pivot is in its correct final position. We then recursively apply the same process to the left and right halves until the entire array is sorted.
Let’s see how the pivot partitions the array
How Quick Sort works
Let’s use the following array:
[14, 25, 4, 6, 8]
In this implementation, we select the last element as the pivot.
We can choose any element as the pivot, although this implementation uses the last element.
Pivot = 8
We also initialize two pointers:
- leftPointer starts from the beginning of the array.
- rightPointer starts from the end of the array.
[14, 25, 4, 6, 8]
^ ^
leftPointer RightPointerNotice that the right pointer initially starts at the pivot position. During the partition process it immediately moves left until it finds an element smaller than the pivot.
Step 1: Move the Left Pointer
The left pointer moves to the right until it finds an element greater than the pivot.
14 > 8
Since 14 is already greater than the pivot, the left pointer stops.
Step 2: Move the Right Pointer
The right pointer moves to the left until it finds an element smaller than the pivot.
8 >= 8
Move left.
[14, 25, 4, 6, 8]
^ ^
leftPointer RightPointer6 < 8
Stop.
Step 3: Swap Elements
Since the pointers have not crossed, we swap the elements.
Swap 14 and 6
[6, 25, 4, 14, 8]
Step 4: Continue Moving the Pointers
Move the left pointer again.
6 <= 8
Move right.
[6, 25, 4, 14, 8]
^ ^
leftPointer RightPointer25 > 8
Stop.
Move the right pointer.
14 >= 8
Move left.
[6, 25, 4, 14, 8]
^ ^
leftPointer RightPointer4 < 8
Stop.
Swap:
Swap 25 and 4
[6, 4, 25, 14, 8]
Step 5: Place the Pivot
Continue moving the pointers until they meet.
At this point:
[6, 4, 25, 14, 8]
^^
leftPointer RightPointer At this point, leftPointer is no longer less than rightPointer, so the partition loop ends.
Now we swap the pivot with the element at leftPointer.
Since all elements smaller than the pivot have been moved to the left side and all larger elements are on the right side, swapping the pivot into this position places it in its final sorted location.
Swap 25 and 8
[6, 4, 8, 14, 25]
The pivot is now in its correct sorted position.
[6, 4] 8 [14, 25]
[6, 4] 8 [14, 25]
^
pivotAll elements on the left are smaller than the pivot, and all elements on the right are greater.
Step 6: Recursively Sort Both Halves
Quick Sort now repeats the same process on:
[6, 4] and [14, 25]
until the entire array becomes:
[4, 6, 8, 14, 25]
QuickSort Code
public class Quicksort {
public static void main(String[] args) {
int[] numbers = {4, 9, 10, 3, 2, 7, 6, 1, 8, 5};
System.out.println("Before:");
printArray(numbers);
quicksort(numbers, 0, numbers.length - 1);
System.out.println("\nAfter:");
printArray(numbers);
}
private static void quicksort(int[] array, int lowIndex, int highIndex) {
if (lowIndex >= highIndex) {
return;
}
int pivot = array[highIndex];
int leftPointer = lowIndex;
int rightPointer = highIndex;
while (leftPointer < rightPointer) {
while (array[leftPointer] <= pivot && leftPointer < rightPointer) {
leftPointer++;
}
while (array[rightPointer] >= pivot && leftPointer < rightPointer) {
rightPointer--;
}
if (leftPointer < rightPointer) {
swap(array, leftPointer, rightPointer);
}
}
swap(array, leftPointer, highIndex);
quicksort(array, lowIndex, leftPointer - 1); // Recurse left side
quicksort(array, leftPointer + 1, highIndex); // Recurse right side
}
private static void swap(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
private static void printArray(int[] array) {
for (int num : array) {
System.out.print(num + " ");
}
System.out.println();
}
}Let’s see how the Quicksort function works
Understanding the Quick Sort Code
Base Case
if (lowIndex >= highIndex) {
return;
}This is the stopping condition of the recursion.
When lowIndex becomes equal to or greater than highIndex, the subarray contains one or zero elements. Since such a subarray is already sorted, there is no need to continue partitioning, so the function returns.
Assign the Pivot and Initialize Pointers
int pivot = array[highIndex];int leftPointer = lowIndex;
int rightPointer = highIndex;In this implementation, the last element of the current subarray is selected as the pivot.
Get Janith Nishen’s stories in your inbox
Join Medium for free to get updates from this writer.
The pointers are initialized as follows:
leftPointerstarts at the beginning of the current subarray (lowIndex).rightPointerstarts at the end of the current subarray (highIndex).
These pointers move toward each other while partitioning the array around the pivot.
Partition the Array
while (leftPointer < rightPointer) {
while (array[leftPointer] <= pivot && leftPointer < rightPointer) {
leftPointer++;
}
while (array[rightPointer] >= pivot && leftPointer < rightPointer) {
rightPointer--;
}
if (leftPointer < rightPointer) {
swap(array, leftPointer, rightPointer);
}
}The main loop continues as long as leftPointer is less than rightPointer.
First, the leftPointer moves to the right until it finds an element greater than the pivot.
while (array[leftPointer] <= pivot && leftPointer < rightPointer)Next, the rightPointer moves to the left until it finds an element smaller than the pivot.
while (array[rightPointer] >= pivot && leftPointer < rightPointer)If the pointers have not crossed, the elements at those positions are swapped.
swap(array, leftPointer, rightPointer);This process gradually moves smaller elements to the left side of the pivot and larger elements to the right side.
The loop continues until the pointers meet or cross each other.
Place the Pivot in Its Correct Position
swap(array, leftPointer, highIndex);Once the partitioning process is complete, the pivot is swapped with the element at leftPointer.
At this point:
- All elements on the left side are smaller than the pivot.
- All elements on the right side are greater than the pivot.
Therefore, the pivot is now in its final sorted position.
Recursive Calls
quicksort(array, lowIndex, leftPointer - 1);
quicksort(array, leftPointer + 1, highIndex);After placing the pivot in its correct position, Quick Sort recursively sorts the two remaining subarrays:
- The left side of the pivot.
- The right side of the pivot.
The same partitioning process is repeated until every subarray is sorted.
The Swap Function
private static void swap(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}The swap() function exchanges the values stored at two positions in the array.
It temporarily stores one value, replaces it with the second value, and then places the stored value into the second position.
For example:
Before:
[14, 25]Swap 14 and 25After:
[25, 14]
This function is used throughout the partitioning process to move elements to their correct side of the pivot.
Let’s see how the code change as we choose differenet elements as pivot
Pivot Selection Strategies
In the previous example, we selected the last element as the pivot. However, Quick Sort allows us to choose any element as the pivot. The choice of pivot can significantly affect the performance of the algorithm.
There are several common strategies for selecting a pivot.
1. Last Element (what we used)
The simplest approach. Works well on random data but performs poorly on already sorted or reverse sorted arrays, because the pivot always ends up being the smallest or largest element, creating highly unbalanced partitions.
2. First Element
Similar to the last element strategy. The only difference is that the first element is selected as the pivot. It has the same weakness — sorted arrays cause worst case O(n²) performance.
To implement this, simply swap the first element with the last element before partitioning, then apply the same logic:
// Pivot as first element
swap(array, lowIndex, highIndex);
// Now the original first element is at highIndex, same partition logic applies3. Random Element
A random index is selected and swapped with the last element before partitioning. This significantly reduces the chance of hitting the worst case since the pivot is unlikely to always be the smallest or largest element.
// Pivot as random element
int randomIndex = lowIndex + (int)(Math.random() * (highIndex - lowIndex + 1));
swap(array, randomIndex, highIndex);
// Now apply the same partition logic4. Middle Element
The middle element of the current subarray is selected and swapped with the last element before partitioning. This tends to create more balanced partitions than always picking the first or last element.
// Pivot as middle element
int midIndex = lowIndex + (highIndex - lowIndex) / 2;
swap(array, midIndex, highIndex);
// Now apply the same partition logicTime Complexity of Quick Sort
The performance of Quick Sort depends heavily on how well the pivot divides the array.
- Best Case: O(n log n) The pivot divides the array into two nearly equal halves at each step.
- Average Case: O(n log n) In most real-world situations, the pivot creates reasonably balanced partitions.
- Worst Case: O(n²) This occurs when the pivot repeatedly becomes the smallest or largest element, creating highly unbalanced partitions.
For example: [1, 2, 3, 4, 5] If the last element is always chosen as the pivot on an already sorted array, each partition leaves one side empty and the other side containing almost all elements.
Therefore:
- Best Case =O(n log n)
- Average Case = O(n log n)
- Worst Case = O(n²)
Space Complexity
- Average Space Complexity: O(log n) Quick Sort does not create temporary arrays like Merge Sort. However, it uses recursive function calls, which consume stack memory. In the average case, the recursion depth is approximately log n, resulting in O(log n) space complexity.
- Worst Case Space Complexity: O(n) This happens when partitions become extremely unbalanced (like in the sorted array example above), forcing the recursion stack to go n levels deep.
Advantages of Quick Sort
- Fast in Practice: Quick Sort is one of the fastest sorting algorithms for arrays in real-world scenarios.
- In-Place Sorting: Unlike Merge Sort, it does not require additional memory arrays for merging.
- Cache Friendly: Elements are processed within the same array, making excellent use of CPU cache locality (since elements are processed within the same array, it performs faster in practice).
- Efficient for Large Datasets: Quicksort’s average case time complexity of O(n log n) makes it highly suitable for massive collections of data.
Disadvantages of Quick Sort
- Worst-Case Performance: Quick Sort can degrade to a terrible O(n²) when poor pivot choices are made on specific datasets.
- Not Stable: Equal elements may not maintain their original relative order after sorting.
- Recursive Calls: Deep recursion can increase stack memory usage and may lead to a stack overflow for extremely large or unbalanced datasets.
Conclusion
Quick Sort is a powerful Divide and Conquer algorithm that sorts data by repeatedly partitioning the array around a pivot. Its average-case performance of O(n log n) and its memory-saving in-place nature make it one of the most widely used and practical sorting algorithms in computer science today.
