Introduction
Quick Sort is an internal sorting technique which can be used to arrange a given set of unordered dataset into required order. It is the most efficient internal sorting technique, which doesn’t use any auxiliary memory (or additional space to hold the dataset while processing) and uses a “divide and conquer” approach for its sorting.
How to write quick sort algorithm
As mentioned before, the Quick Sort algorithm uses a “Divide and Conquer” approach to sort the elements. In this approach, the algorithm breaks the input dataset into working subsets based on a criteria and then recursively applies the same approach on the resultant subsets, while performing sorting on these subsets. All this operations happen “in-place” within the array and hence no additional memory is required for this algorithm.
The algorithm happens in four simple steps:
- Pick a Pivot element from the input dataset, which can generally be the median of the dataset
- Start from both the ends of the dataset and swap the elements such that all the elements in the left side of the chosen “pivot” are lesser than it and all the elements on the right side of the pivot are greater than it.
- Once the left and right pointers which are running from the opposite side run across each other, divide the dataset into smaller subsets based on the index where these indices collide.
- Repeat the steps from 1 to 3 recursively on the thus created subsets, until we have these left and right pointers point to the same index, which means that the dataset is now completely sorted.
The algorithm for this sorting looks like this:
function quicksort(array A, integer left, integer right)
begin
if left >= right then
begin
return;
end
let pivotIndex = (left+right)/2;
let pivot = A[pivotIndex];
let partitionIndex = partition(A, left, right, pivot);
quicksort(A, left, partitionIndex - 1);
quicksort(A, partitionIndex, right);
end
function partition(A, left, right, pivot)
begin
while left <= right do
begin
while A[left] < pivot do
left = left + 1
while A[right] > pivot do
right = right - 1
if left <= right then
begin
swap(A, left, right);
left = left + 1;
right = right - 1;
end
end
return left;
end
Quick sort Example in .NET
Its implementation can look like below:
public void DoQuickSort(ref int[] arr, int left, int right)
{
/*
1. Find a Pivot
2. Set Left and Right to Ends of Arrays
3. Swap all the elements such that
Elements to left of Pivot are smaller than Pivot
Elements to right of Pivot are greater than Pivot
4. If the Left and Right come across, partition the array into two parts
from the start to left, from left+1 to right
recursively work on the successive chunks
*/
// array is now divided till the individual elements
// no more the swapping function is needed
if (left >= right) return;
// set the median as the pivot
int pivot = arr[(left + right) / 2];
var partitionIndex = SwappingFunction(ref arr, left, right, pivot);
// work on the left chunk of the array
DoQuickSort(ref arr, left, partitionIndex - 1);
// work on the right chunk of the array
DoQuickSort(ref arr, partitionIndex, right);
}
public int SwappingFunction(ref int[] arr, int left, int right, int pivot)
{
// all the elements to left of pivot are smaller
// all the elements to the right of pivot are larger
while (left <= right)
{
// move till the element which a[left] > pivot
while (arr[left] < pivot)
{
left++;
}
//left now contains the element which is larger than pivot
// move till the element which a[right] < pivot
while (arr[right] > pivot)
{
right--;
}
// right now contains the element which is smaller than pivot
// now swap left and right
if (left <= right)
{
var temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
// now left is almost at the center of the array
// which can now be used to break the array into sub arrays
return left;
}
For an input dataset {5,9,2,4,7,8} the processing looks like below:
Input: 5,9,2,4,7,8
#Iteration 1:
PivotElement:2 Left: 0 Right: 5
Processed Set: 2,9,5,4,7,8
#Result PartitionIndex: 1
PivotElement:4 Left: 1 Right: 5
Processed Set: 2,4,5,9,7,8
#Result PartitionIndex: 2
PivotElement:9 Left: 2 Right: 5
Processed Set: 2,4,5,8,7,9
#Result PartitionIndex: 5
PivotElement:8 Left: 2 Right: 4
Processed Set: 2,4,5,7,8,9
#Result PartitionIndex: 4
PivotElement:5 Left: 2 Right: 3
Processed Set: 2,4,5,7,8,9
#Result PartitionIndex: 3
Output: 2,4,5,7,8,9
Quicksort time complexity analysis
If we observe how the algorithm works, for every iteration of the dataset the subject dataset on which the algorithm works on is almost divided to half. For example, in the above dataset we have the first iteration run on the entire dataset with the Pivot Element as 2 (index 2) with left and right pointers at the ends of the dataset. But in the second iteration, the subjective dataset is now between 1 and 5, later shrunk to 2 and 5, 2 and 4 and so on. At the final iteration, the subjective dataset was between 2 and 3 which is the set [5,7].
This way, for a typical dataset the algorithm works on about half of the input per iteration. Hence the time taken for this algorithm is logarithmic, and its an average of O(NLogN) for any given dataset.
# dataset working split #
n
n/2 n/2 -> at every level, the total work done is always n
n/4 n/4 n/4 n/4
.
.
.
.
1 1 1 1 ... n (leaves of the call tree)
Here we have the LogN part because the dataset is being divided as we proceed further down the iterations, forming a tree of recursive calls. The depth of this tree is LogN. And at every level of this dataset, we have a constant O(n) work done, since no two recursive calls work on the same dataset. Hence the total is O(NLogN).
As for the space, apart from a few variables for storing the left, right and pivot pointers, we aren’t using any variable memory parts. Hence the algorithm always takes a constant O(1) space.
Conclusion
Quicksort is the fastest internal sorting technique, which does the operations “in-place” without requiring any additional space. It works based on the Divide and Conquer approach and uses a recursive approach for the operation, with a limited subset of elements at any time.
The algorithm takes an efficient O(NLogN) time for the normal case, while at a worst case scenario the time is O(N2). Whereas on the memory front it still goes with an optimal O(1) space.
Found this article helpful? Please consider supporting!
