DSA by Mitul in C++, Python, and Java : Quick Sort (Divide and conquer algorithm)

Here we find the pivot number and make sure smaller numbers locate at the left of pivot and bigger numbers are located at the right of the pivot. Unlike merge sort, extra space is not required.
SO, Lets assume this is our array.
Ans we have decided (right most)50 as our pivot number.

So, according to the rules. Numbers less than the pivot number (50) will be in the left side and number bigger than the pivot number (50) will be in right side.

So, This will look like this.

Now, from the left array, we choose the right most as our pivot again which is 20.

Now, we will take 10 and 30 as pivot and follow the previous process.

Note:We are using Pivot as the right most number of the sorted or unsorted array

So, you can see this part is sorted.

Now from the right array, lets take 90 as our pivot as it the right most.

Then we get this array. We then take 70 as the pivot:

Then 60 as pivot:

Then 80 as pivot:

Done!

Let's see how they use the pivot to swap values less than it and bigger than it.

Here we have 6 as the pivot. Generally pivot number is chosen at random. Also, we labeled Left most number as "L" and right most number as "R".

Now the left labelled value will iterate until it gets the bigger value then pivot (6).

Here 5 is bigger than 6 and thus the label will first move to 5 .

and then 8 is bigger than 5, thus it will move to 8.
When it gets a bigger value than pivot, it stops.

Here 8 is bigger than 6 thus L has stopped.

Now lets move the "R" label until it gets smaller value than pivot(6).

When "R" gets less value than pivot, it also stops.

Now, "L" and "R" will swap values.

This will look like this:

Again, the "L" label will move until it gets bigger value than the pivot(6)

It will stop there. the "R" label will start moving again and find lesser value than the pivot(6).

But here when the right marker moves to the left, it finds left market and now here is a special condition.

If this happens, we will swap that number with the pivot number.

So, done!
We have values in left and right depending on the pivot.

So, this is how the pivot sorts values in left and right array.

Then again from the left array, we can pick 2(right most ) as pivot and then sort like this.

Again, take 5 as pivot and we have:

Then 3 as pivot

As the left part is sorted, lets move to the right part

Then 7 as pivot and 8 as pivot. Finally we have:

Fully sorted array.

Code for Quick sort

def partition(customList, low, high):
    i = low - 1
    pivot = customList[high]
    for j in range(low,high):
        if customList[j] <= pivot:
            i += 1
            customList[i], customList[j] = customList[j], customList[i]
    customList[i+1], customList[high] = customList[high], customList[i+1]
    return (i+1)

def quickSort(customList, low, high):
    if low < high:
        pi = partition(customList, low, high)
        quickSort(customList, low, pi-1)
        quickSort(customList, pi+1, high)

Complexity of the Quick sort

When to use Quick sort?
When average expected time is O(nlogn)

When to avoid Quick sort?
When space is concern and when you need a stable sort.