Hello Guys and welcome to Python programming tutorials by Amuls Academy.
Today in this tutorial we are discussing about the Quicksort algorithm, in this video series
we already discussed about the Bubble sort and selection Sort algorithm for that i will
give you the link in the description box.
So now Quicksort algorithm is also called as "partition exchange sort" algorithm it
is developed by Tony hoare in 1959 and published in 1961 so it is one of the commonly used
sorting algorithm.
Quicksort algorithm when implemented well it can be about 2 or 3 times faster than the
merge sort and heapsort.
I guess that's why the name Quicksort.
So quick sort is the comparison sort algorithm so here also we will compare the values, to
rearrange the list we will compare the values.
Next in_place algorithm so that is nothing but it may require small additional amount
of memory to perform the sorting but it is the inplace sorting.
And next is unstable algorithm that is nothing but the relative order of equal sort item
is not preserved like, if you are sorting a list and it contains the duplicate values
the order they will appear in the input may not be the same in the output ok.so next it
is the recursive algorithm.
And next this Quicksort is the divide and conquer type of algorithm, So divide and conquer
is nothing but in this we will divide a problem into sub problem then we will solve that ok.
So in the divide and conquer rule there will be three steps, first one is divide, second
one is conquer, third one is combine.
So in the devide step we will divide the problem into subproblems ok so in the case of list
we will divide the list into sublist.
In the second Step, that is the conquer step we will find out the solution for the sub
list or sub problem recursively.
In the third step in the combine step we will combine the solution for these sublist or
sub problem to problem ok.
so as I said Quicksort also divide and conquer type of algorithm so in the first step in
the divide step first we will rearrange the list and we will divide the list based on
the "pivot element".
so "pivot" element is nothing but an element which will divide the list and we will divide
the list in such a way that the elements which are smaller than the pivot element will be
present left to the "pivot" element and the element which are greater than "pivot" element
will be present at the right of the pivot element ok.
so we will rearrange the list and we'll devide our list using "pivot" element, so how to
select pivot element we will discuss later.
Ans In the second step in the conquer step we will find out the solution for sub list
recursively.
And here third step is not required in the quick sort algorithm, no need to combine the
solution for sub problem to problem ok so we won't do any combining here.
so I talked about the "pivot" element right, we will divide the list using "pivot" element
then what is this and how to select this right,?
"pivot" element is just an element in the list ok if you ask how to select that then
you can choose the first element as the "pivot" element or you can choose the last element
of the list as the "pivot" element or you can select a random element or median of three
values that is first middle and last ok. so if you search for the quick sort algorithm,
ok in Google or YouTube in the most of the example you can see either first element or
the last element is the "pivot" element, so this is the easiest way to implement but when
sorted list is given or reverse sorted list is given this is the bad choice because we'll
select minimum or maximum value as the "pivot", after partitioning the list either left side
or right side will be completely empty ok. so when the sorted list or reverse sorted
list is given this is the bad choice so in that case we can go for the random element
we can choose random element as "pivot" element or we can go for the median of 3 values OK
so the selection of pivot element is very important it is entirely depend on the type
of input ok.
ok next we will take one example, so i took a list called "a" and these are all the elements.
I want to sort them in the ascending order.
So for that the first step in the Quicksort algorithm is selecting the pivot element ok,
so as i said we can select the last element or first element or random element or median
of 3 values.
so here first I'll take the last element as my pivot element ok.
so this is my "pivot" element, so next step is i need to find out the original place of
this "pivot" element that is 17.
so when i arrange number in the ascending order what is the original place of 17 ,i
need to find out it now.
so for that what i need to do is, i need to place all the smaller values in the left side
of the "pivot" value and i want to place all the bigger value to the right side of the
"pivot" value.
So to do this we need to compare all the values with "pivot" value, so for that i need two
more variables so here i'll take one variable called "left" and it will point here, so the
first element of the list and here i'll take next value as "right" it will point last but
one value because here last value is "pivot" value, here we are comparing the values with
the pivot value, so i don't want to compare this 17 with 17 so that's why i took "right"
from here.
So I'll take the index 0 2 3 4 and 5 ok, so "right" is in 4th index.
so now we will begin from the "left" ok so we will start to compare the values with the
"pivot" value.
so while comparing the values we need to follow few rules ok so that is this rules.
first one is always the "left" index value should be less than or equal to "right" ok
if "left" value become greater than "right" value then i need to stop ok here this first
condition and next is if this condition is true then i need to check the "left" value
that is the first value, whatever the value present in the left index is less than or
equal to "pivot" value, if this condition become false then I need to stop.
and I will go to the next condition that is this condition ok here also I'll check the
value present in the right index should be greater than or equal to "pivot", if not then
I need to stop.
we need to follow these three rules.
so here first I'll take the "left" value, so now initially left value is 0 and "right
value" is 4 right, so I'll write down that so now first I will check the first condition
whether the "left is less than or equal to right", yes because left value 0 right value
is 4 and "0 is less than 4" OK so I can go for the next condition.
so here the next condition is i need to check the first value which is present in the left
index whether it is less than or equal to "pivot" value that is nothing but i need to
check whether "14 is less than or equal to 17" ok
if this condition is true then no need to do anything, I need to move to the next value,
I need to compare next value with "pivot" , because i want smaller value in the left
side ok if it is become false then i need to stop ok and here in this case we can see
"14 is less than 17" ok so this condition become true So what I need to do go to the
next value and compare that with the pivot value ok.
so now this will be my left value, here left index become one, so now i will check "whether
25 is less than or equal to 17", ok so if it is true move to the next value, not stop.
we can see, "25 is greater than 17" ok so this condition become false, so i need to
stop here.
so here i will stop that ok so now i will move to the this right condition.
so here in the right, first I'll check whether "left is less than or equal to right" yes
it is because "one is less than 4" OK so next i will go to the right condition, that is
this.
This condition ok so here the value present in the right index should be greater than
or equal to "pivot" value ok so I'll check "a" of right, the value present in the right
index is greater than or equal to 17, so here first we can see the value is 1, so "1 is
greater than or equal to 17", if true then move to the next value False stop.
so it is false right because "one is less than 17", it is not greater than 17 so I need
to stop here.
ok so in the left side we stopped for a value because we got a value which is greater than
the "pivot" value, in the right side we got a value which is less than the "pivot" value.
Now what we need to do, we need to swap the value present in the left index and right
index because here we want all the smaller number in the left side, all the bigger number
in the right side ok so that's why we need to swap them now.
so I will swap 1 and 25, so, 1 will come here and 25 will go here ok now again we need to
check from the beginning, so here we will start from the left side so first here we
can see the value 1, so I'll check whether "1 is smaller than or equal to 17" Yes, if
yes then i need to move towards the next value right so left will point here now here left
value become 2 ok so now again I'll check whether the value present in the left index
is smaller than or equal to "pivot" value, no it is not, because "100 is greater than
17" right, so I need to stop here and I'll move to the right side so I'll check whether
"25 is greater than or equal to 17" YES it is, so i will go to the next value ok so right
will point here now.
so right value become 3 now ok so now i will check whether this value is greater than or
equal to "pivot" value "14 is greater than or equal to pivot value", no it is not.
Here this value 14 is smaller than 17, so I need to stop so now we got the two values
in the left side we got a value which is greater than the pivot value and in the right side
we got a value which is smaller than the pivot value so I need to swap 100 and 14 now.
so the value present in the left index and right index so 14 will come here and 100 will
go here ok.
so now again we will start from the beginning, we will check whether left is less than or
equal to right, so before checking each value with the pivot value you need to check this
condition ok left should be less than or equal to right, here it is true because left value
is 2, right value is 3, so left is less then right now.
so I'll check whether "14 is less than or equal to 17" YES it is, so I'll move to the
next value So now left will point here, so now i need to check whether "hundred is less
than or equal to 17" no it is not right, 100 is bigger value so i need to stop here.
Here I am stopping this left index now I'll move to the right, here left Intex is 3 now,
so before checking the right value i need to check whether left is less than or equal
to right, here left and right are equal both are three now ok, that's ok the condition
is true now.
so it will check whether "100 is greater than or equal to 17", yes it is right 100 is a
greater value.
so I need to move to the next value so right will move to the this value so now, right
become 2 ok, so next to check the next condition whether "14 is greater than 17", i need to
first check this condition that is whether "left is less than or equal to right" No it
is not, left become greater than Right, Left value is 3, right value is 2 ok so if this
happens i need to stop everything ok now i need to stop, when a left value crosses the
right value that means we got the actual position of pivot value now so, so to place that in
the correct position we need to do is we need to swap now ok pivot value and the value present
in the left index ok, so why because when we take last element as pivot element ok so
then we need to swap pivot and left index if you take first element as the pivot ok
if you take first element as pivot then in that case you need to swap pivot and the value
present in the right index ok you need to remember this, here we took the last value
of list as pivot value here we can see that's why i need to swap pivot and left index value.
Here left index value is 100 and pivot is 17, so i need to swap these two.
ok so here we got the original position of the pivot value that is 17, so that is nothing
but 17 is sorted here now, 17 is present in it correct position that is nothing but, if
i sort this number in the ascending order like 1 14 14 17 25 100 right, this is the
correct order so if i take 0 1 2 3 17 should be present in the third index so here we can
see it is present, that means 17 is sorted, this is not sorted and this is not sorted,
the element present left side and right side of the pivot element is not sorted but 17
is sorted here now, ok based on that now we will sort all the other elements also.
here if you observe then we can see the element which are present in the left side of 17 are
smaller values and the elements which are present in the right side of the pivot value
are the greater than the pivot value right,? so now what we need to do is, we need to divide
the list.
so as i said it is based on the divide and conquer method, so here we will divide the
list based on this pivot element ok, so here we need to divide like this, first is 14 and
1 and 14 ok this is one sublist, Next is 25 and 100 OK.
Here 17 is sorted right.
So we need to solve this sublist separately so we will apply same method OK.
We will take the last element as the pivot and we'll search the correct position of that
pivot element, so we will repeat the same step so we will do this recursively ok.
So here we will take 14 as pivot value now so this will be left value this will be right
value.
right?
so first I'll check whether "14 is less than or equal to 14", that is this value is less
than or equal to 14 yes it is, so I'll move one position next.
so now left will point here, so again i will check whether "1 is less than or equal to
14" yes it is true.
So again I'll move to the next value so it will point Here.
so now here we can see left value is cross the right value, here right value is 1 left
value is 2.
So left is greater than right so I need to stop.
Now i need to swap the value present in the left index and pivot value right,
so both are same here because left index value is also 14 and the pivot value is also same
so we need to swap 14 with the 14 so we'll get 14 only so here we will get the same list
ok.
so if i divide this list now based on this pivot value then we will get 14 and 1.
We will get only one sub list because here there are no elements present at the right
of the pivot element right, so we'll get this sublist.
So now again we need to find out the same method that is i need to take the last element
as pivot and i need to find out the original position of that pivot element, then i need
to divide the list ok.
So here 1 is the pivot value, so this will be left and this will be right because only
two values are present right?, so this is the pivot value.
So first I'll check whether "14 is less than or equal to 1" no it is not, right 14 is greater
than 1, so i'll stop that and I'll go to the right side i will check whether "14 is greater
than or equal to 1" yes it is right, 14 is greater than 1.
so I need to move to the right towards the next value so here right will point towards
here so -1 index okay so now we can see the left value is greater than right.
right value is -1 left value is 0, so left is greater than right so I need to stop and
I need to swap the value present in the left index and Pivot ok.
that is nothing but i need to swap 14 and 1, ok here if i swap that it will become 1
and 14 right.
so here 1 was the pivot value so if we divide this we will get a single list called 14 which
contains only one element Ok so if a single element is present that means it is sorted
right, so it will return 14 here so we'll get 1 and 14 this will return to here.
As i said we will do this operation recursively so it will return the result to the previous
function so this result will be returned to here, so this is nothing but this part is
sorted and we will get 1 14 and 14 and 17 because 17 is also sorted.
We will get this now ok.
so next we will move to the next so we'll move here, so here first I'll take 100 as
the pivot value and this is left and this is right and I'll check whether "left 25 is
less than or equal to 100" yes it is true So left will move here .
so now left comes here, so now you can see right value is less than left Value, so we
need to swap and I need to swap 100 with the 100, because 100 is pivot value as well as
the value present in the left index.
so I need to swap 100 and 100, so this is the pivot value, so it will return the result
as 25 ok. so this is pivot value that means it will
return the sub list that contains only one element that is 25 , so this function will
return 25 and 100.
So We will get 25 100 only it is sorted, so now all the elements are sorted and here we
can see the final result it is 1 14 14 17 25 and 100, all the elements are in ascending
order ok.
so this is about the Quicksort algorithm how to arrange the numbers in the ascending order
by taking the last value as pivot value so now i will stop this video and in the next
tutorial we will see how to sort the numbers in the descending order as well as how to
take first element, random element and median of three values as the pivot value and how
to arrange the numbers ok so thank you for watching don't forget to subscribe to my channel
I will meet you in next class till then take care.

For more infomation >> SYNC 3 | Yeni Özellikleri Nasıl Kullanırsınız? | Ford TR - Duration: 1:57.
For more infomation >> Топ Моменты с Twitch | Спалила ЖЕППУ 😿 | Папич - ТОП 10 Мира PUBG | Фейлы в COD: BO4 | Голосовые - Duration: 10:36. 
For more infomation >> Trường Giang Nói Thu Trang Diễn Sâu - Trong Bổn Cung Giá Lâm - Duration: 2:16.
For more infomation >> Two charged in College Hill double homicide - Duration: 1:35.
For more infomation >> #YesAllMen: How can we reframe masculinity? - Duration: 26:02. 
For more infomation >> 保護された直後に、食事が喉を通らなくなった猫。その予想外の原因に思わず胸が熱くなる!【感動する話】 - Duration: 2:16.
For more infomation >> #27 Overwatch Historic Live Stream - Duration: 52:07. 
For more infomation >> اغنية اجنبية روعه لاتفوتك 2018 - Duration: 3:26. 


For more infomation >> Valle del Guadiato. Mellaria, el corazón de la Córdoba romana. Córdoba - Duration: 0:43.
For more infomation >> Cuộc sống bà Mười đẩy nước ở chợ Thanh Đa giờ ra sao? - Duration: 37:31. 
Không có nhận xét nào:
Đăng nhận xét