Quick Sort (Divide and Conquer) Algorithm

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.

Image picked from Google Images
  • q= PARTITION(A,p,r)
  • QUICKSORT(A[p,q-1])
  • QUICKSORT(A[q+1, r])
  • P=A[p]
  • i=p 
  • j=r+1
  • Repeat i=i+1 until A[i]≥P 
  • Repeat j=j-1 until A[j]≤P 
  • Swap(A[i],A[j])

Example of Sorting an Array using Quick Sort

Lets say we have an array A to sort.

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: 2T(n/2) + n
Comp = O(nlog2n)
Worst: T(n) = T(n-1) + O(n)
Comp = O(n²)
Courtesy: GFG

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store