Stack Bash - Master data structures and algorithms

Quick sort

Quick sort is a divide and conquer algorithm that sorts an array.
The sorting algorithm partitions the input array around an arbitrary pivot.
This is achieved by maintaining pointers to elements on each side of the input array.
The 2 parts of the input array are recursively quick sorted.
Let's take the following input array A as an example
A = [3, 1, 8, 2, 9, 5]
Step through the images below to see how quick sort works
Quick Sort

Try it

Before you look at the solution, try to code it yourself.

Solution

Time and Space Complexity

It takes logarithmic time to divide the problem into subprobems, 2 halves each time.
In every subproblem, we compare the pivot element with each element in the subarray, which takes linear time.
Therefore, the average time complexity of quick sort is O(n*log n).
Comparing and swapping the pivot element in each iteration is done in place.
But since the implementation is recursive, the algorithm builds up the call stack for each sub problem. So the space complexity is O(log n).

5 Essential Sorting & Searching Coding Interview Problems

Master Sorting & Searching by trying the coding challenges below.
  1. 1.Merge intervalsMedium
  2. 2.Kth largest in arrayMedium
  3. 3.Intersection of ArraysMedium
  4. 4.Search sorted matrixHard
  5. 5.Search row & col sorted matrixHard

Want to confidently pass your next coding interview?

Stack Bash helps new and veteran software engineers master data structures and algorithms for technical interviews.