What is Quick Sort?

This article will explain one of the most famous sorting techniques, Quick Sort. We will understand the approach behind the sorting technique, understand pseudocodes and see an example to understand the concept in depth. We will also see the time and space complexity of the algorithm.

Quick Sort is a sorting technique that follows the divide and conquer rule, dividing the given array into half or around an element. Operations are performed around the component to provide the desired result. In quick-sort, we refer to this element as a pivot and try to bring this particular element to its correct position before dividing the array further.

What is a pivot?

A pivot is an element that needs to be brought to its correct place in the array. In quick sort, the elements smaller than the pivot are to be brought before the pivot and the elements greater than it needs to be placed after it. 

The choice of pivot can be made based on its position and the requirement of the problem— ways to choose the pivot based on the index.

1. Element at the end of the array
2. Element at the mid of the array
3. Element at the start of the array
4. Any random position (least recommended)

Note: The position where we pick our pivot at every step must be constant throughout the procedure. That is, during the whole algorithm, the index chosen at the beginning of the partition algorithm needs to be constant for every divided array. This will be understood better with an example we will take up later.

As mentioned previously, we will use the divide and conquer approach to perform this sorting algorithm. Quick sort is a recursion-based algorithm in its general form that divides the array around an element and pivots only after the pivot has been positioned at its correct place in the array.

Overview of the Quick Sort Algorithm

1. Get the pivot index, pi, from the partition function.
2. Divide the array into two parts
   1. Array from starting index, si to pi -1
   2. Array from pi+1 to ending index, ei.
3. Repeat until starting index, si < ending index, ei

Here is the pseudo code for the quick sort algorithm

quicksort(A[], si, ei)

if(si<ei){
	pi = partition(A[], si, ei)
	quicksort(A[], si, pi-1)
	quicksort(A[], pi+1, ei)
}
Code language: Java (java)

Partition Function

There is an essential function that is the basis for quick sorting. It is often referred to as the partition function (partition). This function uses our chosen pivot and sorts the element around that element. Smaller elements come before the pivot, and bigger elements come after. 

To discuss the functioning of the partition function, we will lay out an overview of what happens in the function and understand it better with an example later.

Pseudo Code for Partition

partition(A[], si, ei)              
// select pivot element
pivot = A[ei]
i = si-1

for(j=si, j<ei, j++){

// A[j] is less than pivot then increment i and swap ith and jth element

	if(A[j]<pivot){
		i++
		Swap(A[i], A[j])
	}
// else ignore
}

//swap i+1th element and pivot
swap(A[i+1], A[ei])
return i+1
Code language: Java (java)

Variables assumptions:

1. Starting index = si 
2. Ending index = ei
3. Array element = A[i], where A[i] refers to the ith element of the array.

Approach:

1. Choose a pivot
2. Take two pointers, i and j, where i=si-1.
3. The pointer j starts from si and ends at a-1. For every iteration, j increments by 1.
4. Two conditions carry this algorithm.
   1. If the element is less than the pivot element, increment the i pointer and swap A[i] and A[j].
   2. No action will be taken if the element is greater than the pivot.
5. When the pointer j reaches the ei index, swap A[ei] and A[i+1]. This places the pivot in the correct position.

Now let’s take an example. We will implement partition on this array A[]: 45 72 37 98 50 65

The pivot in this array is 65.

This table imitates the working of the partition function.

Pointer j	Pointer i	Comparison	Changes	Resultant Array
0	-1	45 < 65	i++, swap i and j	45 72 37 98 50 65
1	1	72 > 65	No changes	45 72 37 98 50 65
2	1	37 < 65	i++, swap i and j	45 37 72 98 50 65
3	2	98 > 65	No changes	45 37 72 98 50 65
4	2	50 < 65	i++, swap i and j	45 37  50 72 98 65

Explanation: 

1. j = 0, i = -1, A[0] < pivot, 45 < 65, so we increment i to 0 and swap A[0] and A[0]. In this step, no changes occur as both pointers are in the same position.
2. j = 1, i = 0, A[1] > pivot, 72 > 65, hence nothing changes.
3. j = 2, i = 0, A[2] < pivot, 37 < 65, i is incremented to 1 and A[1] and A[2] swaps.
4. j = 3, i = 1, A[3] > pivot, 98 > 65
5. j = 4, i = 1, A[4] < pivot, 50 < 65, i incremented to 2, A[2] and A[4] swaps.
6. j = 5 and i = 3, so we swap A[i+1] and A[ei], that is, 98 and 65.

Resulting array: 45 37 50 65 98 72. Hence the pivot index is 3

Understanding Quick Sort with an Example

Now that we have discussed the partition function let’s understand the whole algorithm using an example. 

At each step, we divide the array further based on pivot position and call the quick sort function (quickSort()) on the left and right parts of the split array to carry on the procedure until the ending index is less than starting index or starting index surpasses the ending index. 

This way, we can sort our array using quick sort.

Quick Sort Program

Implementation of Quick Sort in Java

public int quickSort(int[] nums, int lo, int hi, int k){
        
        if(hi<=lo) return;

        int pi = parition(nums, lo, hi);
        quickSort(nums, lo, pi-1);
        quickSort(nums, pi+1, hi);               
        
    }

  public int partition(int[] nums, int lo, int hi){
        int pivot = nums[hi];
        int pi=lo;        
        
        for(int j=lo; j<hi;j++){
            if(nums[j]>=pivot){
                swap(nums, pi, j); 
                pi++;
            }     
            
        }
        
        swap(nums,pi,hi);
        return pi;
    }
    
    public void swap(int[] nums, int a, int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

Code language: Java (java)

Complexities

Time Complexity

1. Best Case: O(n*logn) – The best case occurs when the pivot lies in the middle of the array as the array is split in half, and the recursion call takes log n time. 
2. Average Case: O(n*logn) – This occurs when the pivot index is a random variable.
3. Worst Case: O(n^2) – This happens when the pivot is the greatest or smallest element in the array, sorted in descending or ascending order. 

Note: Even though the worst-case complexity of Quick sort is O(n^2), it is much faster than merge sort and heap sort. We can avoid the worst-case complexity by choosing the correct pivot element.

Space Complexity

O(log n)

Quick sort is not a stable sorting algorithm because the swapping of elements occurs concerning the position the pivot takes and not the relative order of the elements. Quick sort is an in-place algorithm because other than the input storage (the given array), we do not use any additional storage (leaving the extra space taken by the recursion call stack). Quick sort is preferred over Merge Sort because the Merge sort consumes an extra space of O(N) to store the merged array, whereas the Quick Sort does the sorting in place.

Problems related to Quick Sort

There are a few famous problems that use concepts based on quick sort

1. Quick Select
2. Kth Largest element
3. Kth smallest element
4. Move Zeros

Problems to practice partitioning

1. Sort 01: move all zeroes in front and all 1s at the end
2. Sort 012: move all zeroes in front, 1 in between and 2s at the end.
3. Sort by parity: Partition array based on a given condition.

Summary

1. Quick sort uses the divide and conquer approach to sort an unsorted array using the partition function recursively.
2. The partition function moves the pivot to its correct position by moving all smaller numbers before it and all more significant numbers after it.
3. The pivot is chosen based on the problem statement’s requirement and time complexity requirements of the problem statement.

Read more about learning paths at codedamn here

Happy Learning!