Sorting is one of the most common tasks in programming. Whether you are organizing numbers, arranging names alphabetically, or ranking results, sorting helps make data more meaningful and easy to analyze. One of the fastest and most efficient sorting algorithms in computer science is the Quick Sort algorithm. It is widely used because of its impressive speed and elegant logic based on the “divide and conquer” approach.
with hands-on learning.
get the skills and confidence to land your next move.
Quick Sort works by selecting an element called a pivot and then rearranging the array so that all elements smaller than the pivot come before it, and all elements greater than the pivot come after it. Once this partitioning step is done, Quick Sort is applied recursively to the subarrays on both sides of the pivot. This continues until the entire array is sorted.
The beauty of Quick Sort lies in its efficiency and simplicity. It performs extremely well for large datasets and is one of the preferred sorting methods in many systems and programming libraries. The average time complexity of Quick Sort is O(n log n), which makes it faster than other simple sorting algorithms like Bubble Sort and Insertion Sort. Let’s explore how we can implement this algorithm in different ways using C++.
Program 1: Basic Quick Sort using Recursion
This first program demonstrates the classic recursive approach to Quick Sort. It uses a pivot element to partition the array and then applies the sorting algorithm to both halves.
#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);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
int arr[] {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "Sorted array (ascending): ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}In this program, the partition() function plays the key role by placing the pivot element at its correct position and ensuring all smaller elements appear before it. The recursive quickSort() function then continues the process for both left and right halves until the entire array is sorted. This approach clearly shows the divide-and-conquer nature of Quick Sort and is perfect for beginners to understand how recursive logic works in sorting.
Program 2: Quick Sort using Iteration (Without Recursion)
Although Quick Sort is usually implemented with recursion, it can also be written using loops. This version avoids recursive calls by using a stack to keep track of subarray boundaries, making it easier to understand how the sorting process unfolds step by step.
#include <iostream>
#include <stack>
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 quickSortIterative(int arr[], int l, int h) {
stack<int> s;
s.push(l);
s.push(h);
while (!s.empty()) {
h = s.top();
s.pop();
l = s.top();
s.pop();
int p = partition(arr, l, h);
if (p - 1 > l) {
s.push(l);
s.push(p - 1);
}
if (p + 1 < h) {
s.push(p + 1);
s.push(h);
}
}
}
int main() {
int arr[] {34, 7, 23, 32, 5, 62};
int n = sizeof(arr) / sizeof(arr[0]);
quickSortIterative(arr, 0, n - 1);
cout << "Sorted array using iteration: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}Here, instead of recursive calls, we use a stack to store the low and high indices of subarrays that need to be sorted. The algorithm continues looping until the stack is empty, meaning all elements have been placed in the right position. This approach helps beginners understand the internal working of recursion in an iterative form, which is quite valuable in understanding algorithm optimization.
Program 3: Quick Sort for Strings
Quick Sort isn’t limited to numbers; it can also be used to sort strings alphabetically. This version shows how the same logic can be applied to text data, making it a great example for sorting names or words.
#include <iostream>
#include <string>
using namespace std;
int partition(string arr[], int low, int high) {
string 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(string arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
string arr[] {"Zebra", "Apple", "Mango", "Banana", "Cherry"};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "Sorted words alphabetically: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}In this program, the same partitioning logic is used, but the comparison between elements now works for strings. C++ allows comparing strings using < and >, which makes sorting text data straightforward. This version helps beginners see how Quick Sort can be adapted beyond just numbers.
Program 4: Quick Sort in Descending Order
There are times when you need to arrange data in descending order — for instance, when displaying high scores or sorting prices from highest to lowest. This version of Quick Sort modifies the partition condition to reverse the sorting order.
#include <iostream>
using namespace std;
int partitionDesc(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 quickSortDescending(int arr[], int low, int high) {
if (low < high) {
int pi = partitionDesc(arr, low, high);
quickSortDescending(arr, low, pi - 1);
quickSortDescending(arr, pi + 1, high);
}
}
int main() {
int arr[] {15, 3, 27, 12, 8, 20};
int n = sizeof(arr) / sizeof(arr[0]);
quickSortDescending(arr, 0, n - 1);
cout << "Sorted array in descending order: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}The logic is nearly identical to the standard Quick Sort, except the comparison inside the partition function now checks for >= instead of <=. This small change ensures that larger elements are moved before smaller ones, producing a descending order. This is a simple yet powerful demonstration of how flexible Quick Sort can be.
Frequently Asked Questions (FAQ)
This section answers some common questions that beginners often have about the Quick Sort algorithm.
Q1: What is Quick Sort in C++?
Quick Sort is a fast and efficient sorting algorithm that uses a divide-and-conquer approach to sort elements by partitioning them around a pivot element.
Q2: Why is Quick Sort faster than other sorting methods?
Because it efficiently divides the data and sorts it in place without requiring additional memory, leading to an average time complexity of O(n log n).
Q3: Is Quick Sort a stable sorting algorithm?
No, Quick Sort is not stable by default, which means equal elements may not maintain their original order after sorting.
Q4: Can Quick Sort handle large datasets?
Yes, it’s one of the best algorithms for large datasets, but recursive implementations can cause stack overflow if not handled carefully.
Q5: Can Quick Sort sort strings or descending data?
Absolutely. By adjusting the comparison logic, Quick Sort can handle strings, characters, and descending order sorting easily.
Conclusion
Quick Sort is a powerful and elegant algorithm that every programmer should learn. It beautifully demonstrates how the divide-and-conquer approach can make complex problems easier to solve. With its impressive speed and adaptability, it stands as one of the most efficient sorting techniques in computer science.
In this article, we explored multiple ways to write a C++ program to implement Quick Sort, from the traditional recursive version to iterative, string-based, and descending order implementations. Each version helps build a deeper understanding of how sorting works in different scenarios.
For beginners, the best way to master Quick Sort is through practice. Experiment with different arrays, change the pivot selection, and observe how it affects performance. The more you explore, the more confident you’ll become in handling sorting algorithms in C++.
