Quick Sort - Data Structures & Algorithms Tutorial Python #15
Vložit
- čas přidán 24. 07. 2024
- Quick sort is a popular sorting algorithm invented by British scientist Tony Hoare. Often interviewers ask questions around quick sort in software engineering interviews. This technique uses divide and conquer approach to divide given list into partitions and then recursively sort these partitions. It starts with a pivot element and tries to put pivot element in its correct position. This video goes over theory and two popular partition schemes called hoare partition and lomuto partition. We will write code to implement quick sort algorithm in python. In the end I have an exercise for you to solve.
Code: github.com/codebasics/data-st...
Exercise: github.com/codebasics/data-st...
Data structures and algo in python playlist: • Data Structures And Al...
Topics
00:00 Quick sort technique
03:59 Hoare partition scheme
08:11 Lomuto partition scheme
13:17 Python code for quick sort
29:06 Exercise
Do you want to learn technology from me? Check codebasics.io/ for my affordable video courses.
#quicksort #datastructures #algorithms #python
Next Video: • Insertion Sort - Data ...
Previous video: • Bubble Sort - Data Str...
Complete playlist: • Data Structures And Al...
Website: codebasics.io/
Facebook: / codebasicshub
Twitter: / codebasicshub
DISCLAIMER: All opinions expressed in this video are of my own and not that of my employers'.
Do you want to learn python from me with a lot of interactive quizzes, and exercises? Here is my project-based python learning course: codebasics.io/courses/python-for-beginner-and-intermediate-learners
who named it quick sort.. maybe they named it sarcastically ☻
I can see the humongous effort you have taken in making this video. Love the energy and I am extremely grateful for this series
You are so welcome
19:13, meanwhile in Rocket Science classes 'Come on guys this is not Data Structures and Algorithms'.
Lol ....😂🤣
Yup! 😂
I don't think this partitioning scheme can be learnt by anyone in the very first attempt. But, the code looks so beautiful when it runs. By the way, 'Divide and Conquer' is now truly British. Thank You, Mr. Hoare.
Hi Sir the thing I love about u is that u do it all by yourself not just looking at the standard codes here and there and then doing
by the same format.
By seeing your videos we are also able to learn how to approach the problem
Thanks a lot, sir
You are the coolest instructor I know. Thank you for explaining a concept which no one else on CZcams was able to explain.
Watch abdul bari
This is the most detailed explaination on Yt. Thank you for putting so much effort.🤗
Awesome learning experience, even though I have to spend 10X time to wrap my brain around, and keep on rewinding!! Thank you sir😀!
You have explained whole Data Structure series very very well. It helps me alot, please upload videos on Algorithms please.
I loved the lack of energy lol. But great presentation! Thank you!
Great explanation! 👏👏👏
This is great you explained this relatively well. Though I am still very confused I'll try to watch it again until I get it.
I'm extremely grateful for this series, ❤ thank you sir
He has coded from starting how a coder should do coding, what problems might come and how to solve those problems. I like it. Thank you so much
We need more teachers like you sir......
Thank you so much Daval sir for the simplistic explination.
you are always a better explainer than others on the you tube ❤✌
line 20 in partition function , you wrote it as
while start < len(elements) and elements[start]
thank you so much dhaval sir, it really helped a lot.
Tqsm for the simple nd neat explanation sir!
Great explanation sir we need more videos on DS algorithm
Will upload soon
Thanks for such a great video and explanation.
If I do quick sorting in below fashion, will it be fine?
I am using last element as pivot >>> traversing through list to see which is less/equal/greater than pivot >>> Adding items to another list >>> Adding all lists together >>> Then making recursive call to repeat the process.
def quick_sorting(sample_list):
print(f"Got list: {sample_list}")
smaller, equal, larger = [], [], []
if len(sample_list) < 2:
return sample_list
pivot = sample_list[-1]
print(f"Pivot element >>> {pivot}")
for item in sample_list:
if item < pivot:
smaller.append(item)
elif item == pivot:
equal.append(item)
else:
larger.append(item)
print(f"Processing: {smaller}, {equal}, {larger}")
return quick_sorting(smaller) + quick_sorting(equal) + quick_sorting(larger)
if __name__ == "__main__":
given_list = [11, 9, 29, 7, 2, 15, 28]
qs = quick_sorting(given_list)
print(f"After quick-sorting: {qs}") # [2, 7, 9, 11, 15, 28, 29]
PS: I haven't written code all by myself but I go through other videos as well. DSA understanding takes time for me. 😀
To be honest I only understood the algorithm after implementing it myself. I have attached my python solution below. Thanks a lot for the videos!!
def quicksort(element, start, end):
if start < end:
p = partition(element, start, end)
quicksort(element, start, p-1)
quicksort(element, p+1, end)
def partition(element, start, end):
pivot = element[end]
i = start
j = start
while(j
great explanation
You are using nested while loop which makes the time complexity as n*n and quick sorts time complexity should be nlogn?
keep continuing
best resource
Yup. Next one is on insertion sort
I have a question,
when did you initialised value of start from 0, in theory you told we dont need to initialize start from 0 but from 1?
How swap function is effecting directly to the actual list, as it is not returning anything
I didn't understand what happened after the first pivot element(11) was positioned in its correct position.
why is pivot initialized to start when the code is being made generic?
isnt it start-1? correct me please
I'm so glad you started this series
But I had a question in mind
How important is dsa for data science and machine learning how should we go about it if our main goal is ml and data science not software engineering?
What are the important topics one should be aware of ?
And pls do complete this series it's imperative for a lot of us
Need to know this answer
Another youtuber who makes data science videos ( Krish Naik ) has a video which explains why every programmer should learn data structures and algorithms.
Here is the link to that video
czcams.com/video/ND3HXC46zO4/video.html
Thanks so much dude, great tutorials. Could you point out what the mistake is with this script that I wrote ?
def lomuto_partition(elements, start, end):
pivot_index = end
pivot = elements[pivot_index]
p_index = start
i_index = p_index+1
while i_index < end:
while p_index < len(elements) and elements[p_index] pivot:
i_index +=1
if p_index < i_index:
swap(p_index, i_index, elements)
if elements[p_index] > pivot:
swap(p_index, pivot_index, elements)
return p_index
Great Sir
There’s a mistake at 9:27 u said eleven instead of pivot
yes, i was searching this comment.😅
have a error if arr dont have any numbers that less than pivot so fix this issue, we have to add a condition right > 0 in second while
What about if input 50 40 30 20 10 start goes beyond bound in while loop right
Sir in your code pivot & start indexes are same
pivot_index = start
pivot = elements[pivot_index]
why ???
The while condition is written as
12:50 Talking about the O(nlogn) time complexity, I think you got it confused with the space complexity!
hello, can you explain better why did you return end? thank you for the great video btw
interesting that the array doesnt get returned internally yet it gets updated and shared recursively
Great explanation sir!!!. Sir how many more videos will be uploaded??
10 more atleast
Thanks. It really helped
I am happy this was helpful to you.
Mistake: at 9:08 you say "you only compare against pivot" (correct), but at 9:25 you say "you move i until you find a value less than 11". You should've said "less than pivot".
Thank you sir....
Is Binary Search a divide & conquer method?
It is working friends, it is working!
Quick note on a tiny mistake that you made: at around 10:21, when P-index hits and stops at 29, you said that "29 is less than 28", instead of "29 is greater than 28". Nothing major, I know what you meant, but it gave me pause for a second.
Great videos, thank you so much! These have been the most helpful.
Does Python supports recursion? I have the algorithm in C++ and I want to have the Python version.
Of course, you can.
Thank you sir
although, we are saying do the swap if start < end , when we swap 7 iwith 11 , start index was 4 and end index was 3. so how come the code is working?
He didn't write an if condition; it's a while loop. The condition checks if the outer loop's start is less than the end. If the condition is false, the outer loop breaks. Since 4 is greater than 3, the loop breaks, and the end is swapped with the pivot at that moment.
Just in gpt,
def quick_sort(arr):
if len(arr) pivot]
return quick_sort(left) + middle + quick_sort(right)
Hey could you help me in the exercise where we have to sort the string part because i have sorted the number part but how do i implement sorted string
Thank You Sir
zabardast😍😍😍
awesome!
Good explanation. Noticed for test case [1, 2, 3, 4, 5] its giving [1, 2, 3, 5, 4].
Ahh... Are you saying my code on GitHub has this issue. Do you have a fix? If yes please give me a pull request
hi i just ran my code on [1, 2, 3, 4, 5] and dont see any issues. it gave me back [1, 2, 3, 4, 5].
@@codebasics in my case, i prove the code in colab, there i notice some issues with the right partition, showing 28,15,29 as the result for that segment of the list of values
9:15 beginners we don't start i here. we start i and p.index together. if i
On 9:34, why do you said 7 is less than 11? Because you said we only compare with pivot, but now you compared with 11, which is not the pivot.
U r awesome man!!!!!!
how about this:
def quicksort(arr):
if len(arr) pivot]
return quicksort(left) + middle + quicksort(right)
In Lomuto, the resultant was not sorted.....
Could you please check the error in my code
def swap(a,b,arr):
if a !=b:
temp = arr[a]
arr[a] = arr[b]
arr[b]=temp
def partition(start,end,array):
pivot_index = start
pivot = array[pivot_index]
start =pivot_index+1
while start
Hey could you help me in the exercise where we have to sort the string part because i have sorted the number part but how do i implement sorted string .
5 minutes to watch the video. 2 hours to implement the lomuto partition!
def quick_sort(collection):
if len(collection)
Correct but you are using extra space for left and right arrays
Elements array is [50, 40, 30, 20, 10] , pivot element = 50 , start = 50 , end = 10
Elements array is [10, 40, 30, 20, 50] , pivot element = 10 , start = 10 , end = 20
Elements array is [10, 40, 30, 20, 50] , pivot element = 40 , start = 40 , end = 20
Elements array is [10, 20, 30, 40, 50] , pivot element = 20 , start = 20 , end = 30
The sorted array is [10, 20, 30, 40, 50]
After executing the code step by step , I noticed that for the initial step you are taking start_index = pivot_index
But in the theory part , you teach start_element is the next element of pivot element i.e start_index = pivot_index + 1...........
so that is making a confussion ..... how to fix it?
the code is wrong it wont work for array having duplicate elements.
I went to programming language course hindi and online class programming in hindi. You know any online class .
Tell me . please sir
Lol
@@padmanabhan5907 why🤔
🔥👍
👍😊
Sir iam B.A graduate can i became data scientist? How?
Hey could you help me in the exercise where we have to sort the string part because i have sorted the number part but how do i implement sorted string
a,b = b,a is a better way to swap
The pivot election is an influencer too naive(low), high, random. Random is the best according to my research.
lumtttottt .... haha .......... great video
I am happy this was helpful to you.
❤
Woww
Hello Sir, can you please create a video developing of project using only DSA ?
So quick sort is nothing but a binary search but not searching only sorts .... I think so...
U actually did a little bit mistake but only in speaking n showing was different just a bit but that's ok i gotch u 💓
YASSSSS
24 18 38 43 14 40 1 54 what about this input
yes.. implementation needs to be tuned further. try giving [15,16,17], output would not be right for this case too.
lumoto lamuto laaa, whatever... who thought learning DSA can be this fun
Why man you confused me, don't upload such video, do partition of this video in 2....
oooooooooo..
hindi mai padha do sir aap
over complicated the python code
Hindi aati hai
You know Hindi
could have explained in better way.. felt a bit difficult understanding while other youtube video were more clear.. for ex : czcams.com/video/UjdyhNkaO9k/video.html
Honest review, no hate !
is he drunk?
worst explanation, honestly you should stop trying to act funny to hide stupid mistakes
I dont know what is happening to u my friend but I feel like if you had some alcohol .. hopefully you are good now