#include <iostream>
using namespace std;
int partition(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++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
// Recursively sort elements before and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
printArray(arr, n);
quickSort(arr, 0, n - 1);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}Output
Original array: 64 34 25 12 22 11 90 Sorted array: 11 12 22 25 34 64 90
This program teaches you how to implement the Quick Sort algorithm in C++. Quick Sort is a highly efficient divide-and-conquer sorting algorithm that works by selecting a pivot element and partitioning the array around it. It's one of the fastest sorting algorithms in practice and is widely used in real-world applications.
1. What This Program Does
The program sorts an array of integers using the Quick Sort algorithm. For example:
- Input array: [64, 34, 25, 12, 22, 11, 90]
- Output array: [11, 12, 22, 25, 34, 64, 90]
Quick Sort works by selecting a pivot, partitioning the array so elements smaller than pivot are on the left and larger on the right, then recursively sorting the partitions.
2. Header File Used
#include <iostream>
This header provides:
- cout for displaying output
- cin for taking input from the user
3. Understanding Quick Sort
Algorithm Concept:
-
Choose Pivot: Select an element as pivot (often last element)
-
Partition: Rearrange array so pivot is in correct position
- Elements < pivot go to left
- Elements > pivot go to right
-
Recurse: Recursively sort left and right partitions
Visual Example:
[64, 34, 25, 12, 22, 11, 90] Pivot: 90 (last element)
Partition: [64, 34, 25, 12, 22, 11] | 90 (all < 90) (pivot)
Recurse on [64, 34, 25, 12, 22, 11] Pivot: 11
Partition: 11 | [64, 34, 25, 12, 22] (pivot) (all > 11)
Continue recursively...
4. Function: partition()
int partition(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++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
How it works:
- pivot: last element (arr[high])
- i: index of smaller element (starts at low - 1)
- j: traverses array from low to high - 1
- If arr[j] < pivot, increment i and swap
- After loop, place pivot at i + 1 (correct position)
Partition Process (pivot = 90):
[64, 34, 25, 12, 22, 11, 90] i = -1, j = 0: 64 < 90 → i=0, swap → [64, ...] j = 1: 34 < 90 → i=1, swap → [64, 34, ...] j = 2: 25 < 90 → i=2, swap → [64, 34, 25, ...] ... After loop: [64, 34, 25, 12, 22, 11, 90] Place pivot: [64, 34, 25, 12, 22, 11, 90] (pivot already at end)
5. Function: quickSort()
void quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
How it works:
- Base case: if low >= high, subarray has 0 or 1 element
- Partition: place pivot in correct position, get partition index
- Recurse: sort left partition (low to pi-1) and right partition (pi+1 to high)
6. Understanding Partition
Partition Goal:
- Place pivot in its final sorted position
- All elements < pivot to the left
- All elements > pivot to the right
Partition Index (pi):
- Returns position where pivot is placed
- Left partition: [low, pi - 1]
- Right partition: [pi + 1, high]
- Pivot at pi is in correct position
7. Time and Space Complexity
Time Complexity:
- Best case: O(n log n) - balanced partitions
- Average case: O(n log n) - random data
- Worst case: O(n²) - pivot always smallest/largest
Space Complexity: O(log n)
- Recursive call stack
- Average depth: log n
- Worst case: O(n) if unbalanced
Stability: Not Stable
- Swapping during partition can change relative order
- Example: [3₁, 3₂, 1] → partition can swap 3₁ and 3₂
8. When to Use Quick Sort
Best For:
- Large datasets
- Average-case performance critical
- In-place sorting needed
- General-purpose sorting
Not Recommended For:
- When worst-case O(n²) is unacceptable
- When stability is required
- Nearly sorted data (can degrade to O(n²))
- Small datasets (overhead of recursion)
9. Important Considerations
Pivot Selection:
- This implementation uses last element
- Other strategies: first, middle, random, median
- Pivot choice affects performance
Partition Balance:
- Balanced partitions → O(n log n)
- Unbalanced partitions → O(n²)
- Random pivot helps avoid worst case
Recursive Calls:
- Tail recursion can be optimized
- Iterative version possible
- Stack depth depends on partition balance
10. return 0;
This ends the program successfully.
Summary
- Quick Sort uses divide-and-conquer with pivot-based partitioning.
- Time complexity: O(n log n) average, O(n²) worst case.
- Space complexity: O(log n) for recursive calls.
- Not stable - partitioning can change relative order.
- In-place sorting - modifies original array.
- Pivot selection affects performance significantly.
- Generally faster than Merge Sort in practice due to better cache performance.
- Understanding Quick Sort is essential for efficient sorting algorithms.
This program is fundamental for beginners learning divide-and-conquer algorithms, understanding partitioning, and preparing for advanced algorithm design in C++ programs.