Quick Sort Algorithm Partition Pivot is an important DAA topic because it appears in real projects, debugging sessions, and interviews. Learn the meaning first, then connect it to a small working example so the rule does not stay abstract.
For this page, focus on what problem Quick Sort Algorithm Partition Pivot solves, where developers usually make mistakes, and how to verify the result. The audit note for this lesson was: limited checklist/practice/mistake/FAQ notes .
A strong understanding of Quick Sort Algorithm Partition Pivot should include syntax, behavior, one realistic use case, one failure case, and one quick way to check your work with tools or output.
Quick Sort Algorithm Partition Pivot should be studied as a practical algorithm analysis lesson, not as a label. Start by naming the input, the rule that changes the input, and the result a learner should be able to predict after reading the page.
In the daa > quick-sort page, the notes should connect the definition with a working scenario, a mistake that beginners actually make, and the exact check that proves the fix. That makes the topic useful for coding, debugging, and interview revision.
Quick Sort is a divide-and-conquer sorting algorithm. It chooses a pivot, rearranges the array so that smaller elements go to one side and larger elements go to the other side, and then recursively sorts the two parts.
Quick Sort is one of the most important sorting algorithms because it is usually very fast in practice, has low overhead, and works in-place for arrays.
Quick Sort follows these steps:
After partitioning, the pivot reaches a position where all smaller elements are on one side and all larger elements are on the other side. That pivot does not need to be moved again.
Quick Sort is often faster than other O(n log n) algorithms in real systems because:
Even though Merge Sort and Heap Sort also achieve O(n log n), Quick Sort is often preferred for arrays when average-case speed matters most.
The worst case happens when partitions are extremely unbalanced, such as sizes 0 and n - 1 repeatedly. This can happen with poor pivot choice, for example always choosing the last element in an already sorted array.
| Case | Time | Recursion Stack | Stable? |
|---|---|---|---|
| Best | O(n log n) | O(log n) | No |
| Average | O(n log n) | O(log n) | No |
| Worst | O(n^2) | O(n) | No |
If the pivot usually splits the array into reasonably balanced parts, then each level of recursion processes a total of n elements, and there are about log n levels. That gives the average running time O(n log n).
Quick Sort performs badly only when the partitions become too unbalanced again and again.
Partitioning is the heart of Quick Sort. It rearranges the subarray so that:
Different partition schemes do this in slightly different ways. The two most common are Lomuto partition and Hoare partition.
import java.util.Arrays;
public class QuickSort {
// Lomuto partition: pivot is the last element.
static int partitionLomuto(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partitionLomuto(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
// Hoare partition: fewer swaps in many cases.
static int partitionHoare(int[] arr, int low, int high) {
int pivot = arr[low];
int i = low - 1;
int j = high + 1;
while (true) {
do { i++; } while (arr[i] < pivot);
do { j--; } while (arr[j] > pivot);
if (i >= j) return j;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
System.out.println("Before: " + Arrays.toString(arr));
quickSort(arr, 0, arr.length - 1);
System.out.println("After: " + Arrays.toString(arr));
}
}import java.util.Arrays;
import java.util.Random;
public class RandomizedQuickSort {
static Random rand = new Random();
static int randomPartition(int[] arr, int low, int high) {
int randomIndex = low + rand.nextInt(high - low + 1);
int temp = arr[randomIndex];
arr[randomIndex] = arr[high];
arr[high] = temp;
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = randomPartition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
public static void main(String[] args) {
int[] arr = {3, 6, 8, 10, 1, 2, 1};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}| Feature | Lomuto | Hoare |
|---|---|---|
| Pivot position | Usually last element | Often first element |
| Implementation | Simpler to understand | Slightly trickier |
| Swaps | Often more swaps | Often fewer swaps |
| Returned index | Final pivot position | Boundary index, not always pivot position |
| Usefulness | Great for teaching | Often more efficient in practice |
Consider [10, 7, 8, 9, 1, 5] with pivot 5 using Lomuto partition.
One pass gives:
Now Quick Sort recursively sorts [1] and [8, 9, 10, 7].
| Strategy | Pivot Choice | Worst Case Risk | Notes |
|---|---|---|---|
| First element | arr[low] | High on sorted input | Very simple |
| Last element | arr[high] | High on sorted input | Common in textbooks |
| Middle element | Middle index | Better than extremes in many cases | Simple heuristic |
| Median of three | Median of first, middle, last | Lower in practice | Common optimization |
| Random pivot | Random index | Very unlikely repeatedly | Gives expected O(n log n) |
Randomized Quick Sort picks the pivot randomly instead of using a fixed rule like first or last element. This helps avoid consistently bad partitions on already sorted or specially arranged input.
It does not remove the theoretical worst case, but it makes that worst case extremely unlikely for practical use.
Quick Sort can perform poorly when many elements are equal, especially with simple partition schemes. In such cases, a 3-way partition can help by dividing elements into:
This reduces unnecessary recursive work on equal elements and improves performance for inputs with many duplicates.
A sorting algorithm is stable if equal elements remain in the same relative order after sorting. Quick Sort is generally not stable because partitioning may swap equal elements across the array.
The recursion stack of Quick Sort is O(log n) on average but can become O(n) in the worst case. One common optimization is to recursively sort the smaller partition first and handle the larger one iteratively or through tail recursion. This helps reduce stack depth.
| Feature | Quick Sort | Merge Sort | Heap Sort |
|---|---|---|---|
| Best / Average | O(n log n) | O(n log n) | O(n log n) |
| Worst case | O(n^2) | O(n log n) | O(n log n) |
| Extra space | O(log n) | O(n) | O(1) |
| Stable | No | Yes | No |
| Practical performance | Usually fastest for arrays | Very reliable, good for linked lists and stable sorting | Predictable but often slower in practice |
Quick Sort is a good choice when:
It is less suitable when guaranteed worst-case performance is required or when stable sorting is necessary.
1. Define the input for Quick Sort Algorithm Partition Pivot.
2. Apply the rule from the lesson.
3. Compare the actual result with the expected result.
4. Record the fix if the result differs.1. Try empty, missing, duplicate, or invalid data.
2. Identify where Quick Sort Algorithm Partition Pivot changes behavior.
3. Explain the safest correction.
4. Retest the normal path.Memorizing Quick Sort Algorithm Partition Pivot without the situation where it is useful.
Connect Quick Sort Algorithm Partition Pivot to a concrete algorithm analysis task.
Testing Quick Sort Algorithm Partition Pivot only with the perfect input.
Include empty, missing, duplicate, incompatible, or failed cases when relevant.
Changing code before reading the visible symptom or error message.
Inspect the output, state, configuration, or stack trace connected to Quick Sort Algorithm Partition Pivot.
Memorizing Quick Sort Algorithm Partition Pivot without the situation where it is useful.
Connect Quick Sort Algorithm Partition Pivot to a concrete algorithm analysis task.
The common mistake is memorizing syntax without understanding when the behavior changes or fails.
Remember the problem it solves in algorithm analysis, then attach the syntax or steps to that problem.
You can predict the result of a small example, explain a failure case, and choose it over a nearby alternative for a clear reason.
They often copy the syntax but skip the state, input, dependency, selector, route, type, or configuration that controls the behavior.
Explore 500+ free tutorials across 20+ languages and frameworks.