Quick sort is a highly efficient sorting algorithm that follows the divide-and-conquer
paradigm. It works by selecting a "pivot" element from the array and partitioning the other
elements into two sub-arrays according to whether they are less than or greater than the pivot.
The steps of the quick sort algorithm are as follows:
QuickSort is a sorting algorithm based on the Divide and Conquer that picks an element as a
pivot and partitions the given array around the picked pivot by placing the pivot in its correct
position in the sorted array.
It works on the principle of divide and conquer, breaking down the problem into smaller
sub-problems.
There are mainly three steps in the algorithm:
1. Choose a Pivot: Select an element from the array as the pivot. The choice of pivot can vary
(e.g., first element, last element, random element, or median).
2. Partition the Array: Rearrange the array around the pivot. After partitioning, all elements
smaller than the pivot will be on its left, and all elements greater than the pivot will be on its
right. The pivot is then in its correct position, and we obtain the index of the pivot.
3. Recursively Call: Recursively apply the same process to the two partitioned sub-arrays (left
and right of the pivot).
4. Base Case: The recursion stops when there is only one element left in the sub-array, as a
single element is already sorted.
Here’s a basic overview of how the QuickSort algorithm works.
Choice of Pivot
There are many different choices for picking pivots.
Always pick the first (or last) element as a pivot. The below implementation picks the last
element as pivot. The problem with this approach is it ends up in the worst case when array is
already sorted.
Pick a random element as a pivot. This is a preferred approach because it does not have a
pattern for which the worst case happens.
Pick the median element is pivot. This is an ideal approach in terms of time complexity as we
can find median in linear time and the partition function will always divide the input array into
two halves. But it takes more time on average as median finding has high constants.
1. Choose a Pivot: Select an element from the array to serve as the pivot. The choice of pivot can
vary (e.g., first element, last element, random element, or median).
2. Partitioning: Rearrange the array so that all elements less than the pivot come before it, and all
elements greater than the pivot come after it. The pivot is then in its final position.
3. Recursively Apply: Recursively apply the above steps to the sub-arrays of elements less than
and greater than the pivot.
4. Base Case: If a sub-array has one or zero elements, it is already sorted.
Example
Consider an array: [10, 7, 8, 9, 1, 5].
1. Choose a Pivot: Let's choose the last element as the pivot (5).
2. Partitioning:
• Rearranging gives us: [1, 5, 8, 9, 10, 7], where 5 is now in its final position.
3. Recursion:
• We now have two sub-arrays: [1] (left of pivot) and [8, 9, 10, 7] (right of pivot).
• The left sub-array is already sorted.
• Now we sort the right sub-array [8, 9, 10, 7] by choosing 7 as the pivot.
• After partitioning, we get: [7, 8, 9, 10].
The final sorted array will be: [1, 5, 7, 8, 9, 10].
Example : implementation
// C++ Program to sort a string of characters
// using Counting Sort
#include <bits/stdc++.h>
using namespace std;
// Maximum range of ASCII lowercase alphabets
#define RANGE 26
void countSort(string &str) {
int n = [Link]();
// Output array to store sorted string
char out[n + 1];
// Count array to store frequency
int count[RANGE] = {0};
// Store the count of each character
for (int i = 0; i < n; i++) {
count[str[i] - 'a']++;
}
// Modify count array to store cumulative
// position of characters
for (int i = 1; i < RANGE; i++) {
count[i] += count[i - 1];
}
// Building output array based on the
// cumulative positions
for (int i = n - 1; i >= 0; i--) {
out[count[str[i] - 'a'] - 1] = str[i];
count[str[i] - 'a']--;
}
out[n] = '\0';
// Copy the sorted characters back to the original string
for (int i = 0; i < n; i++) {
str[i] = out[i];
}
}
int main() {
string str = "geeksforgeeks";
// Sort the string using Counting Sort
countSort(str);
cout << str << endl;
return 0;
}
Run the program
#include <iostream>
using namespace std;
// Function to swap two elements
void swap(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}
// Partition function
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Choosing the last element as pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j < high; j++) {
// If current element is smaller than or equal to pivot
if (arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]); // Swap
}
}
swap(arr[i + 1], arr[high]); // Swap the pivot element
return (i + 1);
}
// Quick Sort function
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // Partitioning index
// Recursively sort elements before and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Function to print the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
// Main function
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: ";
printArray(arr, n);
return 0;
}
Explanation
. Swap Function: Swaps two elements in the array.
· Partition Function: Rearranges the array and returns the partitioning index.
· Quick Sort Function: Recursively sorts the array.
· Main Function: Initializes an array, calls quickSort, and prints the sorted array.
1. Partition Function:
• This function takes the last element as a pivot and places it in its correct position while
ensuring that all smaller elements are on its left and all larger elements are on its right.
2. Quick Sort Function:
• This function recursively sorts the array by calling itself on the left and right sub-arrays formed
by the partitioning.
3. Utility Functions:
• printArray is used to display the contents of the array before and after sorting.
4. Main Function:
• Initializes an array, calls quickSort, and prints the sorted array.
Complexity Analysis:
• Time Complexity:
• Average Case: O(n log n)
• Worst Case: O(n²) (when the smallest or largest element is always chosen as pivot)
• Space Complexity:
• O(log n) for recursive stack space.
Time Complexity
• Average Case: O(n log n)
• Worst Case: O(n²) (occurs when the smallest or largest element is always chosen as the pivot)
• Best Case: O(n log n)
Space Complexity
• In-place sorting (requires little additional memory), so O(log n) for the recursive stack space.
Advantages
It is a divide-and-conquer algorithm that makes it easier to solve problems.
It is efficient on large data sets.
It has a low overhead, as it only requires a small amount of memory to function.
It is Cache Friendly as we work on the same array to sort and do not copy data to any
auxiliary array.
Fastest general purpose algorithm for large data when stability is not required.
It is tail recursive and hence all the tail call optimization can be done.
• Quick sort is generally faster in practice than other O(n log n) algorithms like merge sort and
heap-sort due to better cache performance and locality of reference.
Disadvantages
It has a worst-case time complexity of O(n 2), which occurs when the pivot is chosen poorly.
It is not a good choice for small data sets.
It is not a stable sort, meaning that if two elements have the same key, their relative order
will not be preserved in the sorted output in case of quick sort, because here we are
swapping elements according to the pivot's position (without considering their original
positions).
• The worst-case performance can be poor if not implemented with a good pivot selection strategy
(like randomization or using the median of three).
In summary, quick sort is a popular and efficient sorting algorithm widely used in various
applications due to its performance characteristics and simplicity.