Python Tutorials – Quick Sort Algorithm | Program | Part-1

Python Tutorials – Quick Sort Algorithm | Program | Part-1


Hello guys and welcome to Python programming
tutorials by Amuls Academy. In the previous two tutorials we discussed
about how we can sort the numbers using Quicksort algorithm, today in this tutorial we are discussing
about the Quicksort algorithm as well as we will write the program. So first algorithm and to understand this
tutorial you need to watch the previous two tutorials OK so the first step is, select
the pivot element so it can be first element or last element or you can choose randomly
but select the pivot element. Second step is, find out the correct position
of the pivot element in the list by rearranging it, so we will compare other values with the
pivot element and we will find out its original place right this is about the that step. Next step is divide the list based on the
pivot element, once we found out the original place of the pivot element then we will divide
the list right?, left sublist and right sublist ok, so we need to divide the list. And next step is, sort the sub list recursively,
we will use the same step to sort the sub list that is, in that we will take the pivot
element and we will find out its correct position OK we will do it recursively ok. So these are the steps . so next we will write the program Ok actually
we will use three functions ok in this program, see the first function and second function
these are the user defined function next we will use the main function ok to take the
input as well as to print the input output ok.
so here in the first function, this function is to find out the correct position of the
pivot element ok so in this function we will find out the pivot element correct position
and in the second function we will divide the list based on the this pivot element ok
and we will sort the sub list recursively ok here we can see the recursive call in this
second function ok, so we need to define two functions in this program. so first we will define the first function
that is the function to get the correct position of the pivot element ok so we need to define
a function, so for that i will use “def” keyword next followed by the function name
so here you can give any function name but using the proper function name will help to
understand the program ok if any other user will refer your function then he will get
to know what that function actually will do. ok so here this function is to find out the
original position of the pivot element ok, so i’ll take “pivot_ place” as the
function name, you can take any name ok if you want here i’ll include the comment also
like, ok so this function is to get the correct position of the pivot element see the original
place of the pivot element ok. so next here inside this function i need 3
parameters here ok so first one is the list the entire list, whatever the input because
to get the pivot element first i need list right?. next i need two more parameters that is first
and last, i’ll take name as “first” and “last” these are the index ok so from
where to where. So this first and last parameter will tell
the length of the list, whether we are applying this function on the full list ok or on the
sublist that will be get to know from these two parameters it will tell the length of
list OK. so the “first” will be the starting index
and “last” will be the last index of the list ok.
next so what is the first step. we need to take the pivot element right?,
select the pivot element. so first in this program i’ll take the first
element as the pivot element ok. so what i will do is, i will take a variable
called pivot and here i’ll take “list1” that is the list name and here i’ll take first,
“list1 of first”. Why because it is the index of the first value
ok, and here list name is “list1” so i took “list1 of first”, that means the
first element is pivot now alright. So next i need to take left and right value,
two more index to compare the values right?, here in the example here we can see i took
the first element as pivot. Now i want left and right, here in this example
“0 is first” and “five is last” value ok.
so i took, this list name is “list1” so “list1 of first” means we will get 56
ok. so now i want left Value, left value i want
one, right value 5 ok so what i’ll do is, i will take left as “first plus one” ok
and here i’ll take right at last correct right. Here we can see this is last and this is “first
plus one” ok zero is first here, so we want left as one that is nothing but “first plus
one”. so next i have left now, right now, and pivot,
so now what i need to do?, i need to check this condition right?, i need to check each
and every value with the pivot value, i need to compare that ok.
so first condition is this right?, “left should be less than or equal to right” if
it is true then i will go for the next condition that is, “a of left” is less than or equal
to pivot, here list name is list1, so “list1 of left is less than or equal to pivot”.
so here first i will check “26 is less than or equal to 56”, if it is true then i need
to move to the next value. I need to check next value is less than or
equal to pivot ok so here we are checking the same condition for different value, so
we will check whatever the value present in the left index is less than or equal to pivot
again and again until the condition become false right?, so for that in the program we
will use loops, we want to use the same condition again and again for different values ok so
here i have condition, these are the conditions so I’ll take while loop ok here. so I’ll take while first one is “left should
be always less than or equal to right”, ok i need to check this condition every time,
next condition is, “and” and means logical and ok so i will check “list 1 of left”
ok should be less than or equal to pivot value ok so this is the condition right?, first
condition ok so i need both of this condition need to be true ok that’s why i took “and”
here. if anyone of this condition is true then i
don’t want to execute it’s body. so if it is true then i need to increment
left by 1 . So here we can see first i will check 26=56 this
condition, so i need to take the while loop for that now. So while here also “left should be less
than or equal to right”, ok first i will check this condition, and if it is true then
“list1 of right” the whatever the value present in the right index should be greater
than or equal to pivot, so we are writing the program for ascending order ok so for
this this condition. Now i will do is right is equal to right minus
1. Here this condition become true ok when, if
the value present in the right side is greater than pivot then i will move to the next value
ok so that means i will move this way right?, that’s why
I took right=right – 1. Here 1 index become less that’s why. So if this condition become false then i will
stop there only ok. So next here this while loop become False
in two condition OK when this condition become false here in this loop, in this loop this
condition ok. at that time this loop can be become false
or when this become false ok in any cases this two loop can become false and control
come out of this loop right?. so now i need to write the condition for that,
so i will take if condition and check when “right value become less than left” what
will happen. so i told you in every condition here, “left
should be less than or equal to right” here also left should be less than or equal to
right. what if right become smaller than left, left
become greater than right, what will happen ok so if you remember in the previous tutorial
i told you, if this happen then we need to stop everything and now we got the correct
position of the pivot element. we need to swap now so what we need to do,
we need to swap pivot and the value present in the right index, why right index because
if we take the pivot as the first element then we need to swap right index value, if
you take last element as the pivot then we need to swap left index value i explained
you about this in the previous tutorial right?. so now we need to do this, so we need to swap
pivot and the value present in the right index ok so to swap we can use many methods ok so
here I’ll write in a single line. So here i will write “list1 of first”,
“list1 of right” is equal to “list1 of right”, list1[first]. So here list1[first] is nothing but pivot,
here we can see right?, and “list1 of right” is the value present
in the right index, so now if you ask why I am writing “list1 of first”, instead
of writing pivot, here we want to swap the numbers in the list ok if i write pivot here
it won’t do the changes, i want to change the value present in this first index and
right index ok, i want to change the values in the list itself that’s why here i am writing
“list1 of first”. if you write pivot here instead of “list1
of first” you won’t get the proper output ok.
so for now, so if i took if then i will take else also, so here ok first i’ll check this
condition, “left is less than or equal to right”, and “list1 of left ” is less
than or equal to pivot, if both this condition is true, i need to increment left and i need
to check the next value with the pivot and if this condition become false if any one
of this condition become false i will go here and i will check this condition ok if both
this condition become false, if the control come out of this while loop, then we will
execute this if condition. So i will check, so why control came out of
this while loop, whether because of this condition fails, or this condition fails ok so here
i check that. Ok then what happens if this condition become
false in this and this condition become false in this while loop that is, this case ok .
so this is the left first initially ok i’ll check “26 is less than or equal to 56”
yes it is true. So now i will point towords this value, so
I’ll check whether “93 is less than or equal to 56”, no right?, so i’ll stop here. I will go to the right side and I’ll check
whether the value present in the right index is greater than or equal to 56, no it is not,
so I’ll stop here ok. so in this condition we stop the both the
while loop, ok in the program the first while loop stops because here and next while loop
fails because here this condition become false . In the program this condition became false
first and here this condition become false ok so i’ll come out of this 2 while loop and
i will check this condition whether “right is less than left”, so here check “right
value is 5” and “left value is 2”, No this condition is also false right here right
is 5, it is greater than left ok so this condition satisfies. so control won’t go here, it will go to
the else part,then what we need to do?, we want to swap the value present in the left
index and right index right?, so here i need to do that, ok here in the else part i need
to swap the value present in the left index and right index, if you are not comfortable
with this way you can go for that three variable method you can take a temp variable and you
can swap OK. Here ok, we swap this 93 and 44 ok in the
program, so now what i need to do, again i need to start from the beginning right?, i
need to check the value present in the left index, i need to do this same thing again
ok again i will do ok so i want to execute this part of code again and again so i need
to place this in a loop ok. so that is because here we can see once, if
i, so here 44 will come here right?, so 93 will go here ok now what i will do again i
check the value right?, so i will check first this condition whether the “left is less
than or equal to right” next I’ll check value present in the left is less than or
equal to right, again i will do the same thing ok so if i want to do that again and again
until this condition become false right?, so i need to do this again and again, so what
I’ll do is, i will place this piece of code in a while loop ok so first i will do is,
i will cut this and here I’ll take a while loop. so I’ll take while True this as the
condition, so place that in the, indent it correctly ok, ok so now i took a
while loop and i place this code in the while loop ok. now i need a condition within this while loop
body to come out of this loop right?, so now it is infinite loop it will continuously execute
because while True means it is always true. So now i need some condition to come out of
this loop ok so i want to make it finite so what i will do is, here if this condition
become true when “right becomes smaller than left”, then i need to stop everything
right?, so here i need to check this condition again and again till this condition become
false so what i will do is, if this condition become true i will cut this and here i’ll
write break, so that means come out of the loop ok next here outside the loop i will
execute that code. so what i did now, so if this condition become
true then i will come out of this loop and I’ll swap the value present in the first index
and right, that is nothing but pivot and the value present in the right index. So In this example, so so i will check whether
“44 is less than or equal to 56” true, so I’ll go to this 17, so “17 is less than
or equal to 56”, true so i will again go to 31, “ 31 is less than or equal 56”
true again i’ll go to 93, i will check whether “93 is less than or equal to 56” no right?,
so this condition becomes false so i will stop here only. So i will goto the right side now so right
is here, so it will check whether “93 is greater than 56” true, so it will go to
the next value, left is greater than right, right is “right value is 4”, “left value
is 5” so this condition become false, ok if this condition is become false, so i need
to stop everything now i need to swap the value present in the first index or pivot
value and the value whatever the present in the right index right?, so that’s what we
did here ok . so when this condition become true I’ll stop
everything that’s why here i wrote break it will come out of the loop and here i will
swap the value present in the first index that is pivot and the value present in the
right index ok. And next i want to return some value from
this function ok we came to the end of this function so here I’ll return right index,
the index where pivot element is present now, ok here i need to swap 56 and 31, so this
is the right index right?, after swapping 56 will come here, 56 will present in the
right index so we got the correct index of the pivot element, so we get to know where
actually pivot element should be present ok so that’s why i return right here ok so done
with this one function. so now i need to write the 2nd function, so
next function is to divide the list and for the recursive call. Here I’ll take define here I’ll take the function
name as quicksort itself ok if you want you can change, here also i want first last ok
parameters are same here. first thing what i will do is, I’ll call this
pivot_palce function, this function, so to divide the list i want the index of the pivot
element ok, it will return that, that’s why I’ll call that function now here. so I’ll take one variable called “p” it
will hold the return result and here I’ll call pivot list1 first last ok, this is the
function call to this function, so this will return the index ok where the pivot element
is present that will be stored in this variable. Next what i will do is, i’ll divide the list
ok, how?, i’ll call , i will recursively solve that list so here I’ll take list1, here you
can take the index as zero or you can go for first and here i will take p -1 ok next, p
plus one to last. Ok if you ask how i divided this like this,
so I’ll explain you so here i need to swap 31 and 56 right?, so 31 will come here, 56
here. this is the right that’s why i return the
index of 56 now what i need to do is, so now i got the actual index of the pivot element,
ok that is this 4 . 4th index pivot element is present and it
is the correct position of this pivot element now i need to divide this right?, so how i
will divide it, So 31 26 44 and 17 and here the 2nd sublist
is, only 1 element 93 . Ok so here 0 1 2 3
56 and here from 5 , ok so here this is the one sublist, here we can see the starting
index that is zero and the ending index that is 3, that is nothing but 4-1, what is 4?,
4 is the index of pivot element that is called “p” in our program .
So here i took p-1, 0 to p-1, or first to p-1. Here what is 5, 5 is p+1 so p+1. That’s why in this program first i took
list1 first and p-1 this is one sublist that is left sublist. next here list1 p+1 last, the next sublist,
right sublist ok. So it will do the work recursively and next
here this function is the recursive function right?, here we can see the function call
inside this function body also, so whenever we write the recursive function we will write
two case right?, that is base case and recursive case, base case will be the stopping condition
and recursive case contains the recursive call, so here we can see the recursive case
that is we can see the recursive call. but where is the base case?, here what is
the stopping condition for this Quicksort, when we get a list with single element right?,in
the previous example also i explained about this, when we will get the single element
in a list we will stop that, so here that is the condition, that is the base case, here
we can take like this OK so the condition is when “first index is equal to last index”
that is if it contains single element then the first is also this, last is also this
right?, first index is the starting index and last index is the last index of the list,
so if both are same then we need to stop ok. no need to do anything we need to stop, if
first is smaller than last, then we need to do this recursive case ok, here because in
the base case we don’t need to do anything, that is when “first is equal to last”
here we don’t want to do anything, that’s why here i take the condition like this, here
i will take if condition and here i will check, ok if “first is less than last”, then
only execute this code , that is partition the list and and solve that sub list recursively
OK when a list contains single element then no need to execute anything stop everything
ok so here base case is when “first is equal to equal to last” or when “first becomes
equal to last” ok that time no need to do anything that’s why i didn’t write the condition
here. ok so this is the recursive case and also
this function is not returning any value to the main function where we will call this
function because in this program we are not getting any new list ok we are sorting the
original list itself ok that’s why we are not returning any list or value to the main
function. Next i need to take main, here you need to
take the input, you can take the user input or you can directly take the input like this
ok so i will enter few elements. Next what I’ll do is, I’ll call the quick
sort function ok so this function and here i will pass the list1 and i need to mention
the first and last index ok. so first index will be zero always and the
last index will be length of list1 – 1. Here in this case, here we can see 0 1 2 3
4 5 ok i want to write 5 here, so what is 5?, it is length of list1 – 1 right?, So if
i take length of list1 i will get 6, because the index will start from zero so here i want
5, so i will write n-1 ok so next print list1. so here this function is not returning anything
because here so we are modifying the original list itself. So now if i save this and run this, 17 26
31 44 56 93 these are all numbers are in the ascending order
So if you want descending order then just change the symbol here, ok here go for greater
than or equal to, here less than or equal to. 93 56 44 31 26 17 all the numbers are in descending
order now. And remaining everything i will explain in
the next tutorial, so that’s it for now guys thank you for watching don’t forget
to subscribe to my channel i will meet you in next class till then take care.

15 thoughts to “Python Tutorials – Quick Sort Algorithm | Program | Part-1”

  1. Mam, i am a cse student. i had python mini project in this semester! I don't have any idea abt that can u suggest me a best topic that seems to be the best one in our class ,mam?

  2. mam, give me your mailing address please . I want to learn functions deeply because some error occurred when I used function to print * pattern in another video

  3. Traceback (most recent call last):

    File "M:/Python/QuickSortTest.py", line 25, in <module>

    Quicksort(list1,0,n-1)

    File "M:/Python/QuickSortTest.py", line 20, in Quicksort

    Quicksort(list1,first,p-1)

    TypeError: unsupported operand type(s) for -: 'NoneType' and 'int'

    > error is coming.

  4. def pivot_place(list1,first,last):
    pivot=list1[first]

    left=first+1

    right=last

    while True:

    while left<=right and left<=pivot:

    left=left+1

    while left<=right and right>=pivot:

    right=right-1

    if right<left:

    break

    else:

    list1[left],list1[right]=list1[right],list1[left]

    list1[first],list1[right]=list1[right],list1[first]

    return right

    def quicksort(list1,first,last):

    if first<last:

    p=pivot_place(list1,first,last)

    quicksort(list1,first,p-1)

    quicksort(list1,p+1,last)

    list1=[7,90,76,12,34,2]

    n=len(list1)

    quicksort(list1,0,n-1)

    print(list1)

    done everything but got no output why

Leave a Reply

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