Quick Sort (Divide and Conquer) Algorithm
Suppose you are given a task to sort an array using the Divide and Conquer Approach. You can use either the merge sort or the quick sort. But the merge sort hardly does any kind of division and all the real work happens in the combine step. Whereas in quick sort, the major work is done in the dividing step.
Lets just first understand what exactly does Divide and Conquer mean.
When the divide and conquer approach is used, the problem is broken down into smaller subproblems and then each problem is solved independently. The subproblems also can be further divided if need be and are solved recursively. Then all the sub-solutions of those subproblems are combined together to get the final solution for the original problem.
Quick Sort is one of the most efficient algorithms out there which divides the array into subarrays. It requires an element to be pointed as the pivot and 2 other elements as references to compare with the pivot element to get the list of the elements smaller and larger than the pivot elements on two different sides of it.
Since using quick sort, the problems can be solved by combining optimal solutions to non-overlapping subproblems, quick sort cannot be determined as a dynamic programming approach.
Algorithm
We will divide the problem (which is sorting in this case) into smaller problems (we can divide the problem into same type of smaller problems)
Divide : At first, we divide the problem P into smaller problems P1 , P2,………Pk until P is small enough. Conquer : we get the results of sub-problems by solving them recursively. Combine : the solutions of sub problems to create a solution to the original problem.
Algorithm for Quick Sort
There are 3 main steps:
First is Divide: Divide the Array A[p…r] into 2 sub-arrays A[p..q-1] & A[q+1...r] in a way that each element of A[p..q-1] is less than or equal to A[q] & each element of A[q+1..r] is greater than or equal to A[q]. Compute q as part of this partitioning.
Second is Conquer: sort the sub arrays A[p..q-1] and A[q+1..r] by recursive calls to QUICKSORT.
Third is Combine: the partitioning and recursive sorting lead us to the sorted array A[p..r].
I found a great representation of quick sort from the internet which I would like to represent here as a reference:
QUICKSORT(A[p,…r])
Given — A[p,….r]
To get — Subarray A[1.…r] stored in non-decreasing order when p<r
- q= PARTITION(A,p,r)
- QUICKSORT(A[p,q-1])
- QUICKSORT(A[q+1, r])
PARTITION(A[p….r])
Initialization…
- P=A[p]
- i=p
- j=r+1
Repeat
- Repeat i=i+1 until A[i]≥P
- Repeat j=j-1 until A[j]≤P
- Swap(A[i],A[j])
Until i ≥ j
Swap(A[p],a[j]);
Return j
Example of Sorting an Array using Quick Sort
Lets say we have an array A to sort.
A = [12, 10, 26, 16, 91]
First of all we select 12 as our pivot P element. We give the element 67 i reference and the element 91 j reference.
Now we compare P with i and find that i is greater than P so we will stop here and move on to compare j with P and find that q is greater than P and hence we will decrease j and now compare 16 with P then j decreases again, now we compare 26 with 12 and since it is again greater than 12, j decreases and in the end j reaches to 10. Now since it is less than P, it stops here and since i and j have crossed each other, we will swap j and P.
Now the array becomes A = [10, 12, 26, 16, 91]
We have to keep in mind that whenever we swap P with j, the new position of P will always be the exact position for that element. Here, 12 is on its exact place and the elements on its left will always be lesser than it and the elements on its right will always be greater than it.
Now we can divide the array into 2 smaller parts on the left and right sides of the old pivot. We only have one element in the left subarray so we don’t need to perform any action on it and after performing the same actions on the right subarray, we will get our sorted array A = [10, 12, 16, 26, 91].
Another example that I took from the internet with an amazing animated gif
A = [35, 33, 42, 10, 14, 19, 27, 44, 26, 31]
Normal and Worst Time Complexities:
Normal: 2T(n/2) + n
Comp = O(nlog2n)Worst: T(n) = T(n-1) + O(n)
Comp = O(n²)
Differences between Quick Sort and Merge Sort:
Quick Sort is basically preferred over when arrays are needed to be sorted whereas Merge Sort is better when it comes to sort Linked Lists.
No additional space is required for quick sort but merge sort requires a temporary array to store the elements.
