Modernization Hub

Modernization and Improvement
Quicksort algorithm

Quicksort algorithm


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

100 comments on “Quicksort algorithm

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

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

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

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

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

  6. 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!

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

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

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

  10. 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 ?

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

  12. #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

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

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

  15. 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?

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

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

  18. 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??

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

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

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

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

Leave a Reply

Your email address will not be published. Required fields are marked *