Introduction
Quick Sort is similar to Merge Sort, both of which are divide and conquer techniques, but Quick Sort could be faster. This post explains the concept and implementation of Quick Sort. For concept explanation, I compare between Quick Sort and Merge Sort.
Concepts
The following tables differentiates Quick Sort and Merge Sort
| Quick Sort | Merge Sort | |
|---|---|---|
| Strategy | partition the input array into 2 subarray around a pivot | partition the input array into 2 subarray around the mid point. |
| Divided method | * choose a pivot value. * loop through the input array, rearrange the items such that: 1) a pivot correct location is found 2) items on the left are less than the pivot, items on the right are more than the pivot. | * identify the midpoint. * loop through the arrays, makes copy of items to the left subarray, and right subarray. |
| Conquer method | recursively partition the original array until the subarray size is 1. | recursively partition the original array until the subarray size is 1 |
| How sorting is achieved | each time partition is recursively called, the pivot position is found => item is sorted and placed to correct position in the original array | when merging the subarray backs, comparison is made to swap positions betwen subarrays. |
| Time Complexity | O(nlog n) best case O(n^2) worst case | O(log n) |
| Space Complexity | O(1). There is no need to make copies of items from the input array, to allocate subarrays. The subarrays are identified by left, right boundary | O(n) due to subarrays must be allocated. |
Implementation
The following is my code implementation for algorithms:
quickSortfunction calls partition to divide the array.- There is no need to allocate space for subarray. The subarray will be identified by left, right boundary.
- after partition finishes, quickSort further calls itself recursively to partition the left and right array, separated by the pivot's index which is returned by partition.
partitionfunction does 2 things:- it chooses a pivot value, usually an item at the end of the subarray or right boundary, and performs algorithm such that at the end, the correct position of the pivot in the original array is found.
- it partitions the original array in to left and right subarray, where all items on the left of the pivot are less than the pivot, and all items on the right are greater than the pivot.
- the algorithm that finds the pivot correct position and partition the subarray makes use of a pair value. [i,j] where initially
i = left, j=left-1.- it loops from left to right until
i = pivot's indexin the input array. - it performs necessary swap between items of the input array at
i and j index. - it returns the correct and sorted position of pivot in the input array as
j+1.
- it loops from left to right until
The following youtube explains the algorithm with animation
// C++ program for the implementation of merge sort
#include <iostream>
#include <vector>
using namespace std;
// partition the subarray limited by left, right boundary.
// finding the pivot correct position.
int partition(vector<int>&vec, int left, int right){
// chosing pivot as the last element in the subarray
int pivot = vec[right];
int i=left, j=left-1;
// partition the vect into left, right subarray
// left items < pivot, right items > pivots.
while (i< right){
if (vec[i] <= pivot){
j++;
swap(vec[i], vec[j]); // swaping allowing the partition
}
i++;
}
// This swap allows placing the pivot at the correct position.
swap(vec[j+1], vec[right]);
return j+1;
}
// quickSort the original vector to smaller subarray, identified by left, right boundary
void quickSort(vector<int>& vec, int left, int right){
if (right <= left)
return;
// Step 1: divide the vector to 2 parts around the pivot
// also returns the pivot's correct position.
int pivotIndex = partition(vec, left, right);
// Step 2: conquer, continue to divide the left subarray
// find a pivot correct position
quickSort(vec, left, pivotIndex -1);
// Step 3: conquer, continue to divide the left subarray
// find a pivot correct position
quickSort(vec, pivotIndex+1, right);
}
int main() {
vector<int> vec = {12, 11, 13, 5, 6, 7};
int n = vec.size();
quickSort (vec, 0, vec.size()-1);
for (auto i: vec)
cout << i << " ";
return 0;
}