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.

Mam, how to replace Input with Replace Module

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?

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

Please do program on tower of Hanoi mam

Thank you very much mam

Thank You>>>>>>>>>>>>>>>>>>>>>>

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.

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

Please do linked List in python

Thanks Mam, I really like your teaching style! : )

please make a video on "LINKED LIST "

Can you help me mam, why this swapping method is not working ?

thanks SIR

mam how to accept the list from user

iam noticed that you said 14:21 right<left ie list[5]<list[2] ie 44<93 is false how?