Example for Recursive QuickSort Function
C++
// Online C++ compiler to run C++ program online
#include <iostream>
using namespace std;
// Function to swap elements
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
// This function takes last element as pivot, places the pivot element at its correct
// position in sorted array, and places all smaller (smaller than pivot) to left of
// pivot and all greater elements to right of pivot
int partition (int arr[], int low, int high) {
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high- 1; j++) {
// If current element is smaller than the pivot
if (arr[j] < pivot) {
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
// The main function that implements QuickSort
// arr[] --> Array to be sorted,
// low --> Starting index,
// high --> Ending index
void quickSort(int arr[], int low, int high) {
if (low < high) {
/* pi is partitioning index, arr[p] is now at right place */
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, high, pi + 1);
}
}
// Function to print an array
void printArray(int arr[], int size) {
int i;
for (i=0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
// Driver code
int main() {
int arr[] = {10, 80, 30, 90, 40, 50, 70};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
You can also try this code with Online C++ Compiler
Output
Sorted array: 10 30 40 50 70 7 80 90
This C++ code outlines the QuickSort algorithm using a recursive method. It starts by selecting the last element as the pivot, then partitions the array around this pivot, and recursively sorts the sub-arrays. The swap function aids in modifying the array elements, ensuring the pivot element is placed correctly and the array is sorted efficiently.
Method 2: QuickSort Using Extra Space
An alternative approach to implementing QuickSort is by using extra space. This method simplifies the partitioning process by eliminating the need for in-place swaps. Here, we create two additional arrays to hold elements less than and greater than the pivot, respectively. After partitioning, these arrays are concatenated with the pivot to form the sorted array. This approach is particularly useful for understanding the partitioning concept without modifying the original array.
Here's how it works step-by-step:
-
Select the Pivot: Choose a pivot from the array. This example uses the last element as the pivot.
- Partitioning with Extra Arrays: Create two empty arrays:
less: To hold elements less than the pivot.
greater: To hold elements greater than the pivot.
-
Fill the Arrays: Traverse through the array, comparing each element with the pivot. Place each element in the less or greater array based on the comparison.
- Concatenate: Combine the arrays and pivot into a single array where less elements are followed by the pivot and then the greater elements.
C++
#include <iostream>
#include <vector>
using namespace std;
vector<int> quickSortUsingExtraSpace(vector<int> arr) {
if (arr.size() <= 1)
return arr;
int pivot = arr.back(); // using the last element as the pivot
vector<int> less;
vector<int> greater;
// Partitioning process
for (int i = 0; i < arr.size() - 1; i++) {
if (arr[i] < pivot)
less.push_back(arr[i]);
else
greater.push_back(arr[i]);
}
// Recursively sort and concatenate
less = quickSortUsingExtraSpace(less);
greater = quickSortUsingExtraSpace(greater);
// Combining the results
less.push_back(pivot); // add the pivot
less.insert(less.end(), greater.begin(), greater.end());
return less;
}
// Function to print an array
void printArray(const vector<int>& arr) {
for (int num : arr)
cout << num << " ";
cout << endl;
}
// Driver code
int main() {
vector<int> arr = {10, 80, 30, 90, 40, 50, 70};
vector<int> sortedArr = quickSortUsingExtraSpace(arr);
cout << "Sorted array: ";
printArray(sortedArr);
return 0;
}
You can also try this code with Online C++ Compiler
Output
Sorted array: 10 30 40 50 70 80 90
This code demonstrates QuickSort using extra space, which although it uses more memory, can be easier to understand and debug for beginners. By separating elements into distinct arrays, the partitioning becomes visually clearer and less error-prone.
Frequently Asked Questions
Why choose QuickSort over other sorting algorithms?
QuickSort is often faster than other sorting algorithms like bubble sort and insertion sort, especially for large datasets, due to its ability to partition data and sort in a divide-and-conquer manner.
Is QuickSort stable?
No, QuickSort is not a stable sorting algorithm by default. Stability in sorting algorithms means that identical elements retain their relative order after sorting, which QuickSort does not guarantee.
How does the choice of pivot affect QuickSort's performance?
The choice of pivot significantly impacts QuickSort's efficiency. A bad pivot choice, like always choosing the first element when the array is already sorted, can lead to the worst-case performance (O(n^2)). Ideally, a pivot should divide the array into two equal parts, which is why some implementations pick it randomly or use the median-of-three method to optimize performance.
Conclusion
In this article, we have learned the fundamental concepts and steps of the QuickSort algorithm. We explored its recursive implementation in C++, demonstrating how the algorithm efficiently sorts an array by partitioning it around a pivot and recursively sorting the sub-arrays. Additionally, we examined an alternative method that uses extra space to simplify the partitioning process, suitable for those new to the concept. QuickSort's versatility and efficiency make it a valuable concept for any programmer to learn, particularly useful for handling large datasets where performance is critical.
You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.
7+ registered 
