DSA by Mitul in C++, Python, and Java : Quick Sort (Divide and conquer algorithm)
Published: 2022-11-11 00:26:20

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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vk7y04qlfq4jbuvuhdmd.png)

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.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5uspgc2jso2ipy2yesib.png)


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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0ti70sr265b5et5ntrc0.png)


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/xnlndep51deuxqn4cdvs.png)

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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/kv5by8h0yvqenx9lxq8w.png)


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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4avep7w0ri3dc4quevn4.png)

So, you can see this part is sorted.

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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/l6w38sj59ui5x2f41pbu.png)

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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7jr8rq91wf2f0t1p1vya.png)

Then 60 as pivot:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rhvphh1i230qw0lwwl9c.png)

Then 80 as pivot:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ttwuuots8gibxwvt75h9.png)

Done!


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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/at9hdkodr5m4iib7j7at.png)

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).


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ul2wgsy622eg6n41tyca.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5i257aj4gtslike56sd6.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bzssmxsc5y5gpt5806nl.png)

Here 8 is bigger than 6 thus L has stopped.

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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7toxajruwi9zi552jtux.png)
When "R" gets less value than pivot, it also stops.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5o51zfdc3niragkv7k7a.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6aa75mr317zhm9xksjub.png)
This will look like this:
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zjtis0w4rwidn6zdtde4.png)


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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/myf9lazy69kpjmsuzmz7.png)
It will stop there. the "R" label will start moving again and find lesser value than the pivot(6).

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/cc18hcn3bc37lkv4ekft.png)

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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3xdl8ste9fq3uz3owljz.png)

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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/gcjnsdm5l4zehwx4mgzp.png)


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/du3g82knhhrljz6s73j1.png)

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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/22v7rd3ahmgcuzt2pb3m.png)


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/m3a6cnz05oj6nbkhjqh3.png)

Again, take 5 as pivot and we have:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uul6f8drn65mo52ag98j.png)
Then 3 as pivot

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/am81w0qca3qg0s0pzood.png)

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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zi7u2rgnbwlmd01vgw86.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/i5v7fpeb6eie2m1npnfj.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/g8k89lpxb96e8w9ecdeg.png)

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**

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5xcm4mgg149d30wpjhqa.png)




**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.