QUICK SORT: INTRODUCTION AND PROGRAM
Introduction
Sorting means arranging items in order. For example, sorting numbers from small to big, or words from A to Z. Sorting makes searching and using data much faster and easier. Quick Sort is a famous and very fast sorting method. Many programming libraries use it or a close family member. In average cases, Quick Sort is one of the fastest ways to sort.
Big Picture: What Quick Sort Does
Quick Sort follows a simple idea:
1) Pick one item as a “pivot.”
2) Put smaller items on the left of the pivot, and bigger items on the right. This step is called “partition.”
3) Now, sort the left side by doing the same thing again. Sort the right side the same way too.
4) Stop when the part you are sorting has zero or one item.
This “break into parts and solve each part” style is called divide-and-conquer.
A Friendly Analogy
Imagine you want to arrange shoes by size. You pick one shoe as a reference size (pivot). You move smaller sizes to the left pile and bigger sizes to the right pile. The reference shoe stays in the middle. Then you do the same with the left pile and the right pile until every pile is tiny or already in order. In the end, all shoes are sorted.
Key Terms (In Simple Words)
– Pivot: The chosen “reference” value you use to split the array. Items smaller than the pivot go left; items larger go right.
– Partition: The process of rearranging items around the pivot so left side is “<= pivot” and right side is “> pivot” (or similar rule).
– Recursion: When a function calls itself to handle smaller parts of the same problem.
– Base case: The point where you stop (when a part has zero or one item, it is already sorted).
– In-place: The algorithm reuses the same array; it does not need big extra arrays.
– Stable: If equal items keep their original order. Quick Sort is usually not stable.
How Quick Sort Works (Step by Step, In Words)
First, choose a pivot in the array. There are many ways: last element, first element, middle, random, or “median-of-three.” Then, sweep through the array and put things in the correct side relative to the pivot. After partition, the pivot is in its final sorted position. Now the problem splits into two smaller problems: sort the left part and sort the right part. You keep doing this until the parts are so small they need no work.
Choosing a Pivot
The pivot choice affects speed:
– Last element or first element: Simple, but can be slow if the array is already sorted or reverse sorted.
– Random element: Usually avoids the worst case and gives good average performance.
– Median-of-three (first, middle, last; take the median): Often reduces bad cases and is still simple.
Partition Methods You Will Hear About
There are two popular ways to write the partition step.
1) Lomuto partition scheme
– Simple to code.
– Often picks the last element as pivot.
– Keeps an index “i” separating the smaller zone from the unknown zone. Another index “j” scans the array.
– After scanning, it swaps the pivot into the first position after the “smaller” zone.
2) Hoare partition scheme
– Uses two pointers that move toward each other from both ends.
– Often chooses the first element as pivot.
– Swaps out-of-place items until pointers cross.
– Can do fewer swaps, but the code is a bit trickier.
Time and Space Complexity
Quick Sort’s speed can vary, but the average is very good.
– Best time: O(n log n) when splits are balanced.
– Average time: O(n log n), which is what usually happens with good pivot selection (random or median-of-three).
– Worst time: O(n^2) when splits are very unbalanced (for example, always choosing the smallest or largest as pivot on already sorted data).
– Extra space: O(log n) on average for the recursion call stack. It is in-place in terms of data storage.
When to Use Quick Sort
– When you need very fast sorting in most real-world cases.
– When extra memory should be small.
– When you do not need the sort to be stable.
When to Avoid Quick Sort
– If you must guarantee no worst-case slowdown (for example, hard real-time systems). Merge Sort or Heap Sort may be safer here.
– If you need a stable sort and you cannot use a stable variant of Quick Sort.
Advantages
– Very fast on average (O(n log n)).
– In-place, so it uses little extra memory.
– Simple core idea and widely used.
Disadvantages
– Worst-case time is O(n^2) if pivot choices are unlucky.
– Not stable in its usual form.
– Recursive approach can cause deep recursion in bad cases.
Applications
– Sorting numbers or strings in programs and systems.
– Preprocessing data before binary search and other fast lookups.
– Used inside libraries (or variants of it) for general-purpose sorting.
– Helpful inside other algorithms that need quick ordering of parts.
A Small Example: Quick Sort By Hand
Let us sort this list: [9, 3, 7, 1, 3, 8]
We will use the last element as the pivot (Lomuto style).
– Step 1: Pivot = 8. Move numbers <= 8 to the left.
After partition around 8: [3, 7, 1, 3, 8, 9]
Now 8 is at its final position.
- Step 2: Left part [3, 7, 1, 3], right part [9]. Right part has 1 item, so it is done. Sort the left part.
- Step 3: For [3, 7, 1, 3], pivot = 3 (last element).
After partition: [3, 1, 3, 7]
The pivot 3 is placed in the correct spot between the two 3s. Now we split again: left [3, 1], right [7].
- Step 4: Sort [3, 1] with pivot = 1.
After partition: [1, 3]
Now both sides are size 0 or 1, so they are done.
- Step 5: Combine all parts: [1, 3, 3, 7, 8, 9]
The array is sorted.
Program 1: Quick Sort in Python (Lomuto Partition)
This version sorts the array in place. It also sorts the smaller side first to reduce recursion depth.
def quick_sort(arr):
# Partition using Lomuto scheme: pivot = arr[hi]
def partition(lo, hi):
pivot = arr[hi]
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
return i + 1
def sort(lo, hi):
if lo >= hi:
return
p = partition(lo, hi)
# Sort smaller side first to keep recursion shallow
left_size = p – 1 – lo
right_size = hi – (p + 1)
if left_size < right_size:
sort(lo, p - 1)
sort(p + 1, hi)
else:
sort(p + 1, hi)
sort(lo, p - 1)
sort(0, len(arr) - 1)
return arr
# Example usage:
data = [9, 3, 7, 1, 3, 8]
quick_sort(data)
# data is now [1, 3, 3, 7, 8, 9]
Explanation of the Python Program
The function quick_sort takes a list and sorts it. Inside it, partition picks the last element as the pivot. It moves all elements less than or equal to the pivot to the left. Finally, it puts the pivot in its correct place and returns the pivot’s index. The sort function uses recursion. It stops when the part is size 0 or 1. It always sorts the smaller side first to avoid very deep recursion, which helps prevent stack overflow and makes the average memory use smaller.
Making the Python Version More Robust With Random Pivot
Picking a random pivot often protects us from the worst-case time when data is already sorted.
import random
def quick_sort_random(arr):
def partition(lo, hi):
# Pick a random pivot and move it to the end
pivot_index = random.randint(lo, hi)
arr[pivot_index], arr[hi] = arr[hi], arr[pivot_index]
pivot = arr[hi]
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
return i + 1
def sort(lo, hi):
if lo >= hi:
return
p = partition(lo, hi)
if (p – 1 – lo) < (hi - (p + 1)):
sort(lo, p - 1)
sort(p + 1, hi)
else:
sort(p + 1, hi)
sort(lo, p - 1)
sort(0, len(arr) - 1)
return arr
Handling Many Equal Elements: 3-Way Quick Sort
If your array has lots of duplicates, a “3-way” partition can be faster. It splits the array into three parts: less than pivot, equal to pivot, greater than pivot. This keeps equal items grouped and reduces work.
def quick_sort_3way(arr):
def sort(lo, hi):
if lo >= hi:
return
pivot = arr[lo]
lt = lo # arr[lo..lt-1] < pivot
i = lo + 1 # arr[lt..i-1] == pivot
gt = hi # arr[gt+1..hi] > pivot
while i <= gt:
if arr[i] < pivot:
arr[lt], arr[i] = arr[i], arr[lt]
lt += 1
i += 1
elif arr[i] > pivot:
arr[i], arr[gt] = arr[gt], arr[i]
gt -= 1
else:
i += 1
sort(lo, lt – 1)
sort(gt + 1, hi)
sort(0, len(arr) – 1)
return arr
Program 2: Quick Sort in C (Lomuto Partition)
This version uses the last element as pivot and sorts in place.
#include
void swap(int *a, int *b) {
int t = *a; *a = *b; *b = t;
}
int partition(int a[], int lo, int hi) {
int pivot = a[hi];
int i = lo – 1;
for (int j = lo; j < hi; j++) {
if (a[j] <= pivot) {
i++;
swap(&a[i], &a[j]);
}
}
swap(&a[i + 1], &a[hi]);
return i + 1;
}
void quick_sort(int a[], int lo, int hi) {
if (lo >= hi) return;
int p = partition(a, lo, hi);
// Sort smaller side first to limit recursion depth
int left_size = p – 1 – lo;
int right_size = hi – (p + 1);
if (left_size < right_size) {
quick_sort(a, lo, p - 1);
quick_sort(a, p + 1, hi);
} else {
quick_sort(a, p + 1, hi);
quick_sort(a, lo, p - 1);
}
}
int main() {
int a[] = {9, 3, 7, 1, 3, 8};
int n = sizeof(a) / sizeof(a[0]);
quick_sort(a, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("\n");
return 0;
}
Hoare Partition (Concept Only)
Hoare’s method starts with two indexes, one at the left and one at the right. It chooses a pivot, then moves the left index rightward until it finds an element that should be on the right, and moves the right index leftward until it finds an element that should be on the left. It swaps them, and keeps going until the indexes cross. This method can reduce swaps and is often a bit faster in practice, but it returns a partition index with slightly different rules than Lomuto. If you try Hoare, be careful with the loop conditions and the recursion boundaries.
Stability and In-Place Notes
Quick Sort is not stable in its standard form. If you must keep equal items in their original order, either use a different algorithm (like Merge Sort) or modify Quick Sort with extra memory to handle stable partitioning. Quick Sort is in-place, because it rearranges items inside the array and uses only a small recursion stack as extra space.
Common Mistakes and How to Avoid Them
One common mistake is choosing a pivot that always causes bad splits (for example, always picking the first or last element when the input is already sorted). Using a random pivot or median-of-three helps avoid this. Another mistake is forgetting the base case or using wrong bounds, which causes infinite recursion. Always stop when the part has zero or one item. Finally, be careful with equal elements. If your data has many duplicates, consider the 3-way partition version to avoid slowdowns.
Practical Tips
On small arrays (for example, parts of size less than 10), it can be faster to switch to Insertion Sort inside Quick Sort. This hybrid method speeds up real code. Sorting the smaller side first (as shown above) keeps recursion depth low. For big arrays in real programs, random pivot or median-of-three is a good default.
Short Comparison to Merge Sort and Heap Sort
Quick Sort usually runs faster than Merge Sort and Heap Sort on average because of good cache behavior and simple inner loops. Merge Sort has guaranteed O(n log n) time and is stable, but uses more memory. Heap Sort has O(n log n) time and uses constant extra memory, but is often slower in practice than Quick Sort.
More Examples (Situations Where Quick Sort Shines)
- Sorting a large list of integers read from a file.
- Ordering names alphabetically in a dictionary app.
- Organizing product prices before performing binary searches.
- Sorting database keys in memory to build indexes.
Summary
Quick Sort is a fast, practical, and widely used sorting method. The main idea is simple: pick a pivot, partition the array into two parts, then repeat the process on each part. With a good pivot choice, the average running time is O(n log n). It uses little extra memory and is excellent for most day-to-day sorting tasks. Be aware of worst-case behavior and many-duplicate cases, and use random or median-of-three pivot selection and 3-way partitioning when needed.