In our previous lesson in this series we

discussed and analyzed Merge sort algorithm Merge sort, as we saw is a recursive

algorithm in which we follow a divide-and-conquer strategy

the running time of Merge sort is O(nlogn) in worst case but Merge sort is not an in place sorting algorithm and in

place sorting algorithm takes constant amount of extra memory but the space complexity

of Merge sort is O(n) the extra memory requires disproportional to the number

of elements in a list that needs to be sorted now in this

lesson we will discuss and analyze quick sort which is another recursive algorithm where

we will follow a divide-and-conquer strategy time

complexity of Quick Sort algorithm is O(nlogn) in average case and it is O(n2) in worst

case but Quick Sort is an in place sorting

algorithm we take almost constant amount of extra

memory and despite having a worst case running

time of O(n2) Quick Sort is pretty

fast and efficient in practical scenarios the

worst-case running time of Quick Sort is almost always avoided by using what

we call a randomized version of Quick Sort

randomized quick sort gives us O(nlogn) running time with

very high probability Quick Sort is often the most practical choice

for an efficient sorting algorithm in fact

sort function given to us by most of the language libraries are

implementations of Quick Sort only so in this lesson we will discuss and

analyze Quick Sort algorithm once again I’ll take a very simple

sorting scenario let’s say we have a list of integers

given to us in the form of an array something like this i will name

this array A and we want to re-arrange this list in increasing order of the value of

integers now in Quick Sort what we do is we first select one of the elements

from the list and this can be any element in this

example here let’s say we select number four now we call this selected

number pivot and now first we re-arrange the list such that all the elements lesser

than the pivot are towards the left of it and all the

elements greater than the pivot are towards the right

of it something like this let’s call this whole process

partitioning of a list so lets say partition is a process in which we select a pivot

and rearrange the list such that all the elements

lesser than the pivot are towards the left and all the elements greater than the pivot are towards the

right there can be more than one possible arrangements in

which elements lesser than the pivot will be towards the left and

elements greater than pivot will be towards the right for example

two one and three are lesser than the pivot in this example we could have had them in

order 3 2 1 or 1 2 3 it doesn’t really matter we can have

anyone such arrangement the only requirement is that all the

elements lesser than the pivot should be towards

the left and all the elements greater than the pivot should be

towards right we have an efficient in place algorithm to partition a

list like this we can do so in constant amount of extra memory using only some

temporary variables we will come back to the partitioning

logic but let’s first think about this once we have partitioned the array like

this we can break this problem into two sub-problems and the two

sub-problems will be sorting the segment of the array to the

left of the pivot and sorting the segment of the array to the

right of the pivot and this time alike merge sort we do

not need to create auxiliary arrays entirely new arrays and

copy the elements into these new arrays we

can work on the same arrays it’s just that we will have to keep

track of the start and end index of the segments so if this is array A from index 0 to 7 this is

segment of array A from index 0 till 2 and this

is segment of array A from index four till seven we

will come back to why we do not need to create auxiliary arrays and why we can work on the same array just marking the start and end of a

segment lets first try to understand the

core logic so far we understand that once a list has been partitioned then we have

two sub problems to solve sorting the list left of the pivot

and then sorting the list right of pivot sorting the sub list left of the pivot

and sorting the sub list right of the pivot but now how do we sort these two sub lists

that we have created we can apply the partitioning logic

once again and break the problem even further let’s

say first we want to work on this left sub list so we choose a pivot and then we rearrange the sub list such

that all the elements lesser than the pivot are towards left

three is the largest in this sub list so this arrangement is actually satisfying

the condition this problem will actually have only

one sub-problem now we need to work on segment of the

array from zero till one because there has to be a deterministic

logic of picking up the pivot let’s say we always

pick the rightmost element in the sub list as

pivot so for this segment from 0 till 1

we will pick one as pivot and this sub list will be rearranged

like this and we will have one sub problem to solve so we’re going on in a recursion we

are breaking the problem in self similar manner and remember all the rearrangement is

happening in the original array only in the

original list only the segments that we are showing here are just snapshots of the original array so at

this stage we have two one and 3 at 0 1 & 2 respectively in A and when we go to this stage after

partition two goes to index one and one comes to

index zero so when we are here when our segment is

only one element the element at index one then the

original array from index 0 till 2 is 1 2 & 3 at indices zero one and two respectively and when we have only one element

in a sub list or a segment that segment is already sorted we do

not need to break the problem any further so we need to stop our recursion at this

stage this will be the exit condition from

recursion and at this stage the segment from zero till index two is sorted and now we can go ahead and

work on the segment from index four till seven now let’s first try to understand how

we will do all of this programmatically I will write a function

named QuickSort that will take as argument

an Array A and start and end index of the segment that needs to be sorted now why do we need start and end as

argument because we do not want to create any

auxiliary array any new array what we want to do is we want to use

the same array we want to keep on passing the same

array and we just want to mark the boundaries of the segment that we want

to work upon initially we will call the QuickSort

function passing it start index zero and end index length minus one so we will pass the whole

array things will be clear when i will write the

body of this function now in this function first we’ll make a

call to partition the array and to partition also we will pass

the array the start index and the end index to tell that you need to

work only on this segment now this function partition let’s say will rearrange the array such that we will rearrange the segment of

the array from start till end such that there will be a

pivot and all the elements left of the pivot

will be lesser and all the elements right of the pivot or towards the

higher indices of the pivot will be greater and let’s say in this function

will return the index of the pivot after

rearrangement I will call it pIndex for partition

index now once we have rearranged a segment

in this process partition and got the partition index the index of the pivot then we can make two recursive calls one to sort the

segment left of the partition index and another to sort the segment right or towards the higher index higher indices

of partition index so first call is for segment start till partition index

-1 and another call is for segment starting partition index plus one till end there

is only one thing remaining here now we do not want to go into the recursion

infinitely so we must write a base condition or exit condition in our function here

as we had seen we can exit if a segment is having only one element so we can write something like this if start of the segment is greater than or equal to end then we can return which will mean exiting the

function why start greater than or equal to

end and not just start equal equal end well start

greater than or equal to end will take care of two things if the

segment is invalid then also we will exit and if segment will have only one element then

also we will exit sometimes we will not have a valid segment

in the left or in the right like here for this segment from

index zero till one there is no segment left to the pivot but still we will make a recursive call to QuickSort we need

to gracefully exit in that case we can also write

something like this do this whole partitioning only if start is strictly less than end and this will also mean the same thing we will come back to partitioning

logic which is the core of this algorithm but first i will quickly simulate a run of

QuickSort on this example array here first we’ll

make a call to QuickSort passing it array start index zero and end index 7 now start is less than end 0 is less than

seven so partition function will be called and

after partition partition index will be three so this

QuickSort call will make another QuickSort call with start index zero and end index 2 whenever a function makes another call

the execution of that particular function call is

paused the machine says that hey I’ll come back to you once am done once I have finished this another

call I’ll simply write Q here as shortcut for

QuickSort now once again zero is less than two so

we will partition and this guy Q(A,0,2) will

first make a call to Q(A,0,1) the state of execution

of this call will be paused we will go to Q(A,0,1) zero once again is less than one so

partition will run we’re already showing the partitioned

segment here and first a call will be made to Q A zero and partition index

here is zero so we will make a call like this Q(A,0,-1) now start equal zero and end equal -1

is an invalid segment but our code is taking care

of it we will not go inside the if condition here for this particular

call and this particular call will simply finish and exit so this guy will simply return without

doing anything the control will return back to

Q(A,0,1) and now this guy will make another recursive call to Q(A,1,1) now once again for this guy start less than end condition will be false so

this guy will not partition it will simply return and now Q (A,0,1) will return and now Q (A,0,2) will make another call to Q(A,2,3) sorry Q(A,3,2) it has to be pIndex plus

one till end once again this is an invalid

segments so this guy will simply return and now Q(A,0,2) will return Q(A,0,7) will resume and now Q(A,0,7) will make a

call for the segment right of the pivot a call like Q(A,4,7) will be made Four is less than seven so first

partition will happen after partition pivot will be five now Q(A,4,7) will make call to it

will first make a call like Q A start four end four which will simply return because we have only one element in the segment then

it’ll make another call for segment from six to seven this guy will

again make two calls one for an invalid segment the right one will

be for invalid segment and one for the left one

first it will make a call for the left one the left one will have one element in

the segment so that’ll also simply return so finally

with all these calls our list in all will be sorted once the right

sub list is also sorted the list itself the over all list will

also be sorted so this is how thinks will happen this

is how things will execute for this recursive function QuickSort now let’s

talk about the partitioning logic basically we want

to solve this problem we want to select a pivot and we want

to rearrange a list such that all the elements

lesser than the pivot are to the left of it and all the elements

greater than the pivot are to the right of it I want to write a

function named Partition that should take an array the start index of the segment in the array that needs to be

partitioned and the end index of the segment this signature

will make sure that we have a function to partition a

segment of array A you can pass the whole array to

this function or you can pass the segment you just

need to pass the right values for start and end now in this function we first

need to select the pivot let’s say the right most element in the segment is selected

as pivot so pivot is always A[end] if we

pass this whole array we will pass A start will be zero

end will be 7 so pivot will be four now partition

logic will be something like this we will first take a variable named pIndex or partition index i am just

writing shortcut pIndex for partition index and initially we will set it to start and now we

will scan the whole list from start till end-1 and we will make sure that all the

elements lesser than the pivot are pushed to the

left of partition index partition index will be adjusted

accordingly so we will do something like this we will run a loop from start till n -1 and if the element at that particular

index is less than or equal to pivot we will

first swap that particular element with the element at partition index and

then we will increment the partition index with this much of code let’s quickly

see what will happen if we will try to to partition this array that we are showing in the left here

we will pass this array start index will be zero end index

will be seven so four will be the pivot pIndex will initially be zero now the idea

is to push all the elements lesser than the pivot

to the left of pIndex we will start the for loop with i equal 0 we will come to this conditional

statement 7 is not less than or equal to 4 it is

greater than 4 so no swapping will happen i will simply

get incremented now A[i] will be two two is lesser than four so we will

swap the elements at index i and at index

pIndex and now pIndex will be incremented at any stage all the elements to the

left of partition index will be lesser than the pivot let’s say we will show them in this

blue color now i will be incremented i will be two one once again is lesser than four

so we will swap these two elements seven and one partition index will now be equal to two

and i will be three 6 is greater than 4 so we will simply move 8 once again

is greater than 4 i will now be five and 5 the element at index

five is also greater than 4 so we will go to index

six three is lesser than four so we need a

swap here and now pIndex at this stage will be three and now we will exit the for loop and if you can see at this stage all the

elements lesser than the pivot are towards the left of the partition

index and the pivot itself and the elements

greater than the pivot are on or after the partition index now

there is only one more thing that we need to do and we will have a proper partitioning

we will swap the element at the partition index with

the element at end index which is the

pivot so six will go to index seven and Four

will come to index three and now we have a proper partitioning

this function Partition will return the partition index and we are good with this implementation

of Partition function the QuickSort function that we had written earlier

will work let’s quickly write a real program for this and see whether this works or not I’m writing

this program in C++ this is the implementation of Partition

function and then I have written the QuickSort

function inside the QuickSort function we make a call to Partition and then we

make two recursive calls in the main function I have

initialized an array of 8 elements then am making a call to

QuickSort passing starting index Zero end index

seven and then I’m simply printing the elements in the array after call to QuickSort let’s

see what happens when we run this code and the output seems to be sorted

now let’s change this array let’s pick

up the example that we had used earlier this is the array that we had used in our

example once again the output seems to be

correct so we are looking good so this is our implementation of QuickSort in C++ we have left one

question unanswered the question was why are we

not having to create an auxiliary array here like Merge Sort well in Merge Sort once we were done

sorting the left part and the right part then we were merging the two parts back

into the original list and there is no way you can perform the

merge process without using auxiliary arrays think about it and you should be able to

get it we will analyze the properties and running time of QuickSort in next lesson this is it for this lesson

thanks for watching

There are a few issues (including a possible bug in the code, need to change the <= to < , in your if statement in the partition). Overall, overall pretty decent. Still, I would also look at the "Introduction to Algorithms" book MIT press, and also check out other material first. Then this video will aid you if you still dont get it. The example helped me as its been over 30 years since I read the first edition of the MIT press book! 🙂 Well, I would also ensure that the algorithm presented should match the code and vice versa. – so there I said it.

it would be gr8 , if u could link a github gist for the codes

Nice attempt..

nicely explained, each step is clear and deep, thank you for this sir 👍👍🙂👍

Amazing explanation.

Thanks a lot sir.

Hi You are doing a great job.The video is excellent.But i felt one point is missing .Can you please explain how the control jumps from one Quicksort(A,start,end) to QuickSort(A,start,pindex-1) and from here to QuickSort(A,pindex+1,end)…That would make the explanation complete.

Can you please explain how multiple recursion works.I mean how the output of the below code is ABACABA. Here is the code:

public class Main {

public static void main(String[] args) {

recMethod("ABCD",2);

}

public static void recMethod(String s,int n){

if(n>=0){

recMethod(s,n-1);

System.out.print(s.charAt(n));

recMethod(s,n-1);

}

}

}

source of code:StackOverflow

thanks bro

amazing explanation

if pivot = A[end], for should be for i -> start to end: so, that if we pass 12345678 it works. if not it runs from 1 to 7 and pIndex will be at 7 and it gets swaped with 8 and we get 12345687 and returns 7 as pIndex

Thanks, your tutorial is best among all the quicksort videos

PIVOT, PIVOT, PIVOT, PIVOT!!!!!!!!!!!

❤❤

Tnqqqqqqqq….sooooo sir

At 3:13 sir can we select 7 as a pivot

I think in the partition function pIndex should be start -1. Please correct me if I am wrong.

Beautiful explanation! Best I found so far in my research. Thanks alot.

good expalanation………………..cool……

Excellent walk through! I have one clarification at 18.48, for the last swapping, what happens if the pivot value is greater than all elements, then that will collapse the logic. Logical comparison must be done for the last swapping as well.

Partition should be explained early, It remains a mystery till the end, else it was very good

watch?v=ApfZomWlfik

Damn…Subscribed!

swap(a[i]….. You dint gave the swap function definition in last codes… Still how the program works?

someone help me please. Im trying to code this in python but it will not work, heres my code:

def partition(array, start, end):

pivot = array[end]

partition_index = start

for i in range(start, end):

if array[i] <= pivot:

temp = array[i]

array[i] = array[partition_index]

array[partition_index] = temp

partition_index+=1

temp = array[partition_index] # swap pivot with element at partition index

array[partition_index] = array[end]

array[end] = temp

return partition_index

def quicksort(array, start, end):

if start < end:

partition_index = partition(array, start, end)

quicksort(array, start, partition_index – 1)

quicksort(array, partition_index + 1, end)

def main():

array = [56, 7, 23, 45, 17, 5]

n = len(array)

quicksort(array,0,n-1)

print ("Sorted array is:",array)

How can i download this code…? Can you send me link or direct code on my mail ID, I.e [email protected]

Thanks in advance.

Thq sm bro by your second video.i thought i came to right place to improve my coding skills.

MyCodeSchool should publish tutorial videos of all subjects in Computer Science in the similar fashion…. They are so so so easy to understand and helpful!

I don't know why but this code is not working 🙁

Amazing man! You helped me a lot! Really amazing explanation.

Thank you, sir. This is exactly what I needed.

partition logic is incorrect. need to add another condition if(i != pIndex) after if(A[i] <= A[pIndex])

Best explanation I've encountered, thanks!

Great tutorial!!! Thank you

ZIROWWW <3

I think none on youtube really understands how this quick sort thing works, every video is different ! what a waste of time.

Sir…….u r a god ..cleared my concept ..thanks a ton sir…

i think its wrong coz it wont work for whose start is less than pivot

if iam wrong comment !!

swap function is missing

thanku so much sir…you made it so easy to understand

muito bom, me ajudou muito no meu lab

very nicely explained sir

BEST EVER!!!!!!!THANK YOU SO MUCH!!

I like the variable name you picked for pIndex – I have seen some cases where they just use i and j and this leads to confusion. The name pIndex and your comment makes it much clearer. One more thing, some folks start pIndex at start-1 which is also confusing even though we arrive at the same results as long as you increment BEFORE you swap. Thanks.

Thankyou!

There should be a check to verify, while partitioning, if the current element and the element at partIdx are same, This will reduce the number of bogus swaps i.e swapping arr[0] with arr[0] because arr[0] = 1 and pivot is 2. The same goes with the pivot swapping.

Source arr = {6,2,10,8,7}

Output of your program if i write to console each time a swapping is done:

Source Array: 6 2 10 8 7

Swapped: Index 0 with Index 0

//Bogus swap

Swapped: Index 1 with Index 1

//Bogus swap

Swapped: Index 2 with Index 4

Swapped: Index 0 with Index 1

Swapped: Index 3 with Index 3

//Bogus swap

Swapped: Index 4 with Index 4

//Bogus swap

Source Array: 2 6 7 8 10

Update to your program:

using System;

public class Program

{

public static void Main()

{

int[] numbers = {6,2,10,8,7};

Console.Write("Source Array: ");

foreach(int num in numbers)

Console.Write(num + " ");

quickSort(numbers, 0, 4);

Console.Write("Source Array: ");

foreach(int num in numbers)

Console.Write(num + " ");

}

//Rearranges the numbers lesser than the pivot to left of pivot and larger than to the right of the pivot and returns the current partition index

public static int partition(int[] arr, int start, int end)

{

int pivot = arr[end];

int partIdx = start;

for(int curr = start; curr < end; curr++)

{

if((arr[curr] <= pivot))

{

if(curr != partIdx) //Additional check to verify that swap should only be done if the numbers are not at there best position

{

Console.WriteLine(" ");

swap(arr, curr, partIdx);

}

partIdx++;

}

}

Console.WriteLine(" ");

if(partIdx != end) //Additional check to escape an extra swap

swap(arr, partIdx, end);

return partIdx;

}

public static void swap(int[] arr, int a, int b)

{

Console.WriteLine(String.Format("Swapped: Index {0} with Index {1}", a,b));

int temp = arr[a];

arr[a] = arr[b];

arr[b] = temp;

}

public static void quickSort(int[] arr, int start, int end)

{

if(start < end)

{

//find the pivot element

int pi = partition(arr, start, end);

//recursively sort left to pivot segment

quickSort(arr, start, pi-1);

//recursively sort right to pivot segment

quickSort(arr, pi+1, end);

}

}

}

Output after implementing the checks:

Source Array: 6 2 10 8 7

Swapped: Index 2 with Index 4

Swapped: Index 0 with Index 1

Source Array: 2 6 7 8 10

All the dislikes are from bubble sort

This is the best explanation I found. Thx for sharing.

Best tutorial, can you make a video on heap, bucket and radix and external sorts. I really like your videos

Self similar manner is your pet clause

All your tutorials are awesome. Can you pls upload data structure algorithms?

Also a doubt, why sort only left n right of partitions? Why don’t you pass pIndex in either of QuickSort() but pIndex-1 and pIndex+1? What happen to element at A[pIndex] in each recursive call ?

god bless shiva for this helpful tutorial

ağzının yayını sikeyim senin ben

Very good explanation. Keep it up, I want u to suggest one thing that during watching videos the titles being displayed are overriding the actual subject in bottom of the window.. plz take care of this..

where is swap function in written program

#include<stdio.h>

//using namespace std;

void swap(int *x,int *y)

{

int temp;

temp = *x;

*x = *y;

*y = temp;

}

int partition(int *A,int start,int end){

int pivot =A[end];

int partitionIndex =start;

for(int i =start;i<end;i++){

if(A[i]<=pivot){

swap(&A[i],&A[partitionIndex]);

partitionIndex++;

}

}

swap(&A[partitionIndex],&A[end]);

return partitionIndex;

}

void quicksort(int *A,int start,int end){

if(start<end){

int partitionIndex =partition(A,start,end);

quicksort(A,start,partitionIndex-1);

quicksort(A,partitionIndex-1,end);

}

}

int main(){

//int i ,n;

int A[]={7,6,5,4,2,3,1,0};

quicksort(A,0,7);

for(int i=0;i<8;i++)

printf("%dt",A[i]);

//cout<<A[i]<<" ";

}

i coppied your code ..there is no error but output is empty any one help plz i am lost

Best explanation of quicksort on youtube.

Indian tutorials are the life saver for computer science students

Best Explained

This is the best and easiest partition function i ve seen in quick sort implementation. simply too good

Tank you siir…

this guy is the master of explaining CS fundamentals

Actually amazing woah

Quick sort is the highly effective sorting algorithm which is based on the partitioning of arrays. In quick sort, a pivot element is selected. This point can be an element of the array, the first, the last or any. Based on this the array is divided into three parts: Elements less than the pivot, the pivot itself and the elements greater than the pivot.

To read the full algorithm visit: http://www.eduriz.com/quick-sort/ (http://www.eduriz.com/quick-sort/)

What happens when we select randomly 8 is selected?

Thank you Sir 😄

thankyou sir love from Pakistan doing a great job

Where is Source Code??

Thanks

your code has stack overflow you dumb indian shit

quick sort…… who gave this name, it should be the lazy sort…

I guess we can do merge sort without auxiliary arrays, can we sir??

It's too hard for me 🙁

it should be like this (start < end)

awesomely done

mycodeschool is best!!!

although accent may be bothering some but certainly better than not knowing all this great information!

Nice video as always.

But may I know which softwares do you use for writing and recording? Also do you use a stylus for writing?

Best sort in the history of all sorts

i think we can implement mergesort without using two new auxillary arrays

Algworithm

Yesterday I saw all your videos on sorting. Today in interview they asked me to explain quick and bubble sort. I got selected.

You are a good man.

Thank you.

it always confuses me ,in the last swap how can you be sure that the element at pIndex is greater then the pivot? what if you made the last swap but you weren't suppose to do it.

Thank you so much for this helpful tutorial ! but i have confused about something how could i make the swap if at the first check that (A[i]<= pivot) is true while index i starts at 0 also the P-index starts at 0 too??

Worst

Pls remove that fucking subtitles. It was hiding the screen

thanx for good explaination about quick sort..but my request for you is about how shell sort algorithm works

Sir,we used the swap function to swap the pivot element in the array , in place we can even iterate the loop from start to end but not (end-1).So,the pivot element might have its correct position.

what if the pivot element is 1 sir?help

this code is wrong it doesn't work for an array with values like "3,4,1,7,6" . Please do correct it.

Thanks a lot!

yet another perfect explanation. thank you!!

BEST VIDEO ON QUICKSORT!

"Think about it and you will get it" – well said my friend, well said.

what if the pivot is the greatest number in the array?

Best quicksort tutorial!

Been going over all your videos over the past several weeks – the content and presentation is amazing. I've learned so much and now I have much better intuition of all these algorithms.

Im going to win a medal at IOI 2020 in your memory Lord Harsh.R.I.P

on or after the partition index…hmm

you are awesome…

i must say precise, concise and excellent teaching

It's so sad that this channel is dead the last video posted was from 2 years ago but why you were doing great and content is best in whole youtube