This is great video! but, I feel the algo provided in the end is not the same as the way he was explaining.. I went ahead and wrote my code for it same way he explained: ``` class Solution: def sortArray(self, nums: List[int]) -> List[int]: def quicksort(nums, lo, hi): if lo < hi: partition_resting_point = partition(nums, lo, hi) quicksort(nums, lo, partition_resting_point - 1) quicksort(nums, partition_resting_point + 1, hi) def partition(nums, lo, hi): pivotIdx = random.randint(lo, hi) nums[pivotIdx], nums[hi] = nums[hi], nums[pivotIdx] pivot = nums[hi] l_idx = lo r_idx = hi-1 while l_idx
Yeah, in the early days I didn't spend enough time on pseudocode. Trying to fix that now by building out this repo: github.com/msambol/youtube/blob/master/sort/quick_sort.py. Thanks for the feedback!
After you swap itemFromLeft and the pivot at the end, itemFromLeft is now at the end of the array. So, use that as the *new* pivot. Repeat that until its sorted.
@@kennethquilantang8080 after 7 is put in its correct position, remember that all numbers to the right of 7 are greater than 7. In this case, there is only one number - 8. A partition with just one number is already sorted, so you can ignore it and move on to sort [6,5] to the left of 7. For sorting [6,5] choose 5 as the pivot. itemFromLeft is therefore 6, and itemFromRight has no value because no number in the array smaller than 5. Therefore, we can stop and swap itemFromLeft and the pivot to leave [5,6]. Yes, the video is unclear because it does not explain these cases. The point is that each time you put the pivot into it's correct position, you have "split" the array into two parts - one part has all numbers bigger than the pivot and the other part has all numbers smaller than the pivot. Parts with *just one* element are already sorted. If a part is already sorted, no itemFromLeft can be found. If a part is unsorted, you are guaranteed to find an itemFromLeft, and if the index of itemFromRight < the index of itemFromLeft *OR* itemFromRight does not exist then you can swap itemFromLeft and the pivot to put the pivot into its correct position in the whole array.
I've been looking at it for a few minutes now, and I can believe that this pseudocode is accurate, but I'd have to check the details of what the partition function is doing to be sure, but it seems legit. Assuming your language of choice will permit a self-referential function like that.
@@diabl2master The recursion is fine... he's talking about how `partition` is putting the pivot on the left wall instead of the right. In the video the pivot is on the right side.
@@jscholex That would be a failure of technically reflecting, not intuitively reflecting, the walkthrough. I'm not sure OP was referring to that, but who knows.
N Betancourt cuz the way he explains it IS confusing I’ve watched this a couple of times, thought I understood went to the exam and screwed up Now that I’ve watched other videos I understand that the way he explains it is confusing
He didn't explain what quick sort does in general, what it can be applied to, and left some holes in the explanation that someone with no experience would struggle to grasp. Which is a shame.
To ones without enough background knowledge, this video omits details of execution of each step. But to ones with, this is concise and covers sufficient key points of quick sort. Thanks a lot for your video sharing.
The pseudocode is wrong. Not only does it not match your explanation at all, it doesn't even work when implemented. Please cut that part of the video out or put an end card there stating that it's wrong, it's misleading and a waste of time.
Sorry about that. I didn't focus enough on pseudocode in the early days. Please look here for better code: github.com/msambol/youtube/blob/master/sort/quick_sort.py.
you lost me at, "we'll let recursion handle the rest".. should have shown animation of how each element moves while being sorted instead of showing the final sorted array :/
I study computer science, and once, I had an exam with a few sort algorithms in it. I didn't really study but about twenty minutes before the exam I watched your 2-4 minute videos on these sort algorithms and I passed the exam. Thank you for helping me.
What's so confusing? the pivot gets out of the way, the two halves get on two sides and pivot is swapped back. So you have two halves as you desire. The only thing missing was when there are only two items, you just set them in order without partitioning. Other than that, it's pretty easy to follow.
The thing is, at the beginning he says you swap item from left with item to right which obviously makes item from left higher index than item from right, but he does it again and only then he swaps with pivot?! It's impossible to see a pattern when there's no pattern in this explanation. EDIT: "StOp wHeN InDeX oF itemFromLeft > index of itemFromRight" but the first time he swapped it was higher index too so that's what I meant
The pseudocode is not accurate. If the parameter `high` from Quicksort(A, low, high) is inclusive, then line 4 should be Quicksort(A, low, pivot_location - 1). Running this program as it is will cause an endless recursion where `low = 0` and `high = 1`, thus never reaching the base case (low < high).
I read up on this and it’s a pivot is the the max then you are going to get to the end of the array without finding a value to assign for item larger, and that means you have to choose a new pivot. I think an implementation that avoids this error will have to have multiple ways of choosing pivot including choosing first item or choosing last item or choosing a random or just iterating through the list until you find a pivot that works. Whether you have multiple options of choosing the pivot depends on whether duplicate numbers are allowed. If duplicates are not allowed then it is easier. I think random number generation is the most and efficient way of choosing a pivot so I would not include that in my implementation
This is great. The simple explanation and the especially simple pseudocode towards the end makes it easy to understand the core concept of the algorithm.
I have to admit that the visualisation is great. It helps me understand and implement quicksort by myself clearly, but the pseudo-code is not relative to the walkthrough. Anyway, still a great video.
If you don't understand quicksort in 4 min that doesn't make you dumb or the explanation bad. Watch it again and maybe again, work it out in your head, grab a white board. These things don't come easy for everyone. If you're just starting CS get used to it and keep at it!
Why the pseudocode doesn't intuitively reflect the walk through? (Quote from Wikipedia) "The pivot selection and partitioning steps can be done in several different ways; the choice of specific implementation schemes greatly affects the algorithm's performance." There are two partition schemes: 1. Lomuto partition scheme, which is the pseudocode provided in the video. 2. Hoare partition scheme, which is the walkthrough in the video. Comparison (Quote from Wikipedia) 1. "As the Lomuto partition scheme is more compact and easy to understand, it is frequently used in introductory material, although it is less efficient than Hoare's original scheme." 2. "Hoare's scheme is more efficient than Lomuto's partition scheme because it does three times fewer swaps on average, and it creates efficient partitions even when all values are equal." To understand the Lomuto partition scheme more, I recommend a UA-cam video called "Quicksort: Partitioning an array" by KC Ang.
Your pseudo code does not represent the algorithm you explained in the video. Your psuedocode uses only 1 index to check the pivot against, as opposed to the 2 index method you described.
If anyone is confused at the 1:10, basically he doesn't go through the loop. Instead he jumps to when item from left is higher or item from right is smaller etc. There is a left and right pointer that checks for the condition and then left++ or right-- if its not correct. itemsfromRight goes from 1 cuz its smaller, and then the right-- checks 7, not smaller, right--, checks 8 not smaller, right-- and then it checks the 0 and see that its smaller.
Your pseudo code at 04:05 is wrong for both functions Quicksort and partition, inside Quicksort first recursive call should be from low to (pivot_location -1) and inside Partition when A[i] is less than pivot then swap will be done on A[i] and A[leftwall + 1]. Also writing swap(pivot, A[leftwall] is wrong you should write swap(A[low],A[leftwall])
I remember i wrote a quicksort program understood fully the concept and 6 months later i dont even remember the concept. Quicksort is such a weird algorithm
"I think you understand the concept so we'll let recursion handle the rest" NO I DONT ! Why you only used the right part of the list and not the left(2 1 0) ?
The explanation was with Hoare partition scheme but the pseudo code is with Lomuto partition scheme. Those are different. Please check what you copy-paste!
Really wonder why the hell they call this "Quick Sort" more like "The slowest, easiest to mess up, complex sort." I get that the average case is what we're after, but if worst case is n² anyway, might as well choose a different sort imo.
I was able to write quick sort in a day when I first learned it, and now I completely forgot and feel stupid. This is my major, how tf did I forget this algorithm.
Pivot is reference. You just got to put all the values that is larger than the pivot to the right and values smaller than the pivot to the left. Thats all it is. Why are the comments overreacting??
You can't say you understand how the recursion works if you don't explain the base case that terminates the recursion. There is a big hole in the explanation for when you hit 1 or 2 elements in the subarray that defines how to end the recursion itself.
Dude wtf this is so confusing you say pick an item from right to pivot but 3 is already right-most... At least mark the center position if you meant to
def quicksort(arr): if len(arr) < 2: return arr else: pivot = arr[0] less = [i for i in arr[1:] if i pivot] return quicksort(less) + [pivot] + quicksort(greater)
This is great video! but, I feel the algo provided in the end is not the same as the way he was explaining.. I went ahead and wrote my code for it same way he explained:
```
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
def quicksort(nums, lo, hi):
if lo < hi:
partition_resting_point = partition(nums, lo, hi)
quicksort(nums, lo, partition_resting_point - 1)
quicksort(nums, partition_resting_point + 1, hi)
def partition(nums, lo, hi):
pivotIdx = random.randint(lo, hi)
nums[pivotIdx], nums[hi] = nums[hi], nums[pivotIdx]
pivot = nums[hi]
l_idx = lo
r_idx = hi-1
while l_idx
Yeah, in the early days I didn't spend enough time on pseudocode. Trying to fix that now by building out this repo: github.com/msambol/youtube/blob/master/sort/quick_sort.py. Thanks for the feedback!
@@MichaelSambol I got really confused when the pseudocode didn't match the explanation. You should correct that (in the video) ASAP.
@@westsideslasha I'm sorry about that! UA-cam won't let me change the video now unfortunately, but I pinned this comment.
I am encountering an infinite loop if I change the while condition to be i < j instead of
i am glad that i looked at the comment section after having a hard time connecting the pesudo code to the video content.
With every new quick sort video, I watch, I get more recursively confused.
same lol all the quicksort videos use the same words to explain it
hey man, after pulling my hair out for 2 days I finally got it, sadly I had to pay for it.
@@अनिष्टदेव-श7य what did u pay for?
@@HACKINGMADEFUN a Udemy course
@@अनिष्टदेव-श7य cool
Guy: "I think you understand the concept"
Me: No I don't
it gets halved and is recursively applied to both halves in each step
@@Evokans um what?
@@sleevman It gets repeatedly done on each new half, as after each half the pivot is in the right place, so a new pivot is used.
@@faith2756 sorry wat?
@@sleevman Which part exactly do you not understand?
i should be working at mcdonalds
You really should. *SAD!*
@@SkillUpMobileGaming You too
wait what. why
lol 😂😂😂
that's what I was thinking. you're a genius pal
I feel so dumb when i don't understand this, but then i just scroll the comment section and realise that im not alone lol
understanding the meaning of pivot is the KEY.
yeah, theitemfromleft, or right wasn't even properly discussed, left of what or right of what exactly?
lol
he is missing lot of steps , this video is a crime
So we let magic handle the rest.
HAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHA
After you swap itemFromLeft and the pivot at the end, itemFromLeft is now at the end of the array. So, use that as the *new* pivot.
Repeat that until its sorted.
@@airex12 so 8 is the new pivot? How can I go through if there is no number in the array greater than 8?
@@kennethquilantang8080 after 7 is put in its correct position, remember that all numbers to the right of 7 are greater than 7. In this case, there is only one number - 8. A partition with just one number is already sorted, so you can ignore it and move on to sort [6,5] to the left of 7.
For sorting [6,5] choose 5 as the pivot. itemFromLeft is therefore 6, and itemFromRight has no value because no number in the array smaller than 5. Therefore, we can stop and swap itemFromLeft and the pivot to leave [5,6].
Yes, the video is unclear because it does not explain these cases. The point is that each time you put the pivot into it's correct position, you have "split" the array into two parts - one part has all numbers bigger than the pivot and the other part has all numbers smaller than the pivot. Parts with *just one* element are already sorted. If a part is already sorted, no itemFromLeft can be found. If a part is unsorted, you are guaranteed to find an itemFromLeft, and if the index of itemFromRight < the index of itemFromLeft *OR* itemFromRight does not exist then you can swap itemFromLeft and the pivot to put the pivot into its correct position in the whole array.
@@airex12 I get your point bro thanks but what would be the next step. Will I need to pick another pivot? How can I sort the rest?
*screams in Ross voice* PIVOT! PIVOT! PIVOT!
haha, I can't help imaging Ross's face, hahaha
Me in future, oh Ross's couch sort?
screams in Chandler voice SHUT UP! SHUT UP! SHUT UP!
Oh my GOOOOD :-))))))))))))) So truuuuueeeeeee
This is exactly what came into my mind learning about this :))
The psudocode is not intuitively reflecting the walkthrough
I've been looking at it for a few minutes now, and I can believe that this pseudocode is accurate, but I'd have to check the details of what the partition function is doing to be sure, but it seems legit. Assuming your language of choice will permit a self-referential function like that.
@@diabl2master The recursion is fine... he's talking about how `partition` is putting the pivot on the left wall instead of the right. In the video the pivot is on the right side.
@@jscholex That would be a failure of technically reflecting, not intuitively reflecting, the walkthrough. I'm not sure OP was referring to that, but who knows.
@@diabl2master Yeah who knows... but I think we can all agree the pseudocode isn't great hah
the pseudocode shows the Lomuto version but the visualisation is for the Hoare version, which is better. See Wikipedia for both.
This is the most confusing and incoherent visualization of quicksort I've ever seen
Well said 👍
Makes perfect sense to me
Christian May That’s so great! 🙌👏
I thought the visualisation was fine. I feel that I understand it now.
This is the fist visualisation of quick-sort I've ever seen, so I know it doesn't mean much, but I agree.
am still confused
N Betancourt cuz the way he explains it IS confusing
I’ve watched this a couple of times, thought I understood went to the exam and screwed up
Now that I’ve watched other videos I understand that the way he explains it is confusing
N Betancourt He made it more confusing, for sure.
He didn't explain what quick sort does in general, what it can be applied to, and left some holes in the explanation that someone with no experience would struggle to grasp. Which is a shame.
Hope this helps :ua-cam.com/video/Zh37XyQLHkw/v-deo.html
i hope you got it cute bird from nichijou
How to get Confused in 4 minutes
then again, this was the best video about it so far
I want more videos like this where they explain stuff in less than 10 minutes
Bet ? ua-cam.com/video/Zh37XyQLHkw/v-deo.html
there's a video by abdul. i think it is best
To ones without enough background knowledge, this video omits details of execution of each step. But to ones with, this is concise and covers sufficient key points of quick sort. Thanks a lot for your video sharing.
Thats the fanciest wording I've heard, i would use: "You get it or you dont"
Try to sort a few short sequences yourself according to the steps in the video. You may get the "background knowledge".
I think I'm here for the fourth time now.
i put this at 1.5x and now i learnt quick sort 2.6667 minutes
you should put the code next to all of the visual aids and highlight each line as its being done in the visual. thanks for the help with sorting!
Imagine newcomers watching this explanation for the first time.
Thank you. I feel the same about my actual online course I'm studying. And I'm a newcomer. I feel better.
horrible
Hahahaha I still didn't get this.....😎😎
The pseudocode is wrong. Not only does it not match your explanation at all, it doesn't even work when implemented.
Please cut that part of the video out or put an end card there stating that it's wrong, it's misleading and a waste of time.
Sorry about that. I didn't focus enough on pseudocode in the early days. Please look here for better code: github.com/msambol/youtube/blob/master/sort/quick_sort.py.
thank you for pointing this out
Psuedo code does not match demonstrated algorithm.
here for the comments
VERY UNIQUE TASTE 8|
Wtf
The comments on this video do not reflect the like/dislike ratio.
Doesn't this guy know Left and Right or what
Lol
lol
@@zolongOne lol again
you lost me at, "we'll let recursion handle the rest".. should have shown animation of how each element moves while being sorted instead of showing the final sorted array :/
Code is not right.
"leftwall = leftwall + 1;" needs to happen right before "swap(array[i], array[leftwall]);" not after it.
Agree!
Grate video! Just one thing. @ 1:53 itemFromLeft is 0 and itemFromRight is 5. This part confused me.
you lost me at 2:54 :(((
Nice! Glad to see magic still exists!
I'm seeing myself working customer service for the rest of my life
don't you think at 4:04 , in Partition code. leftwall++ should be before swap(A[i], A[leftwall])
better and much easier algo than any standard quicksort algo available in the books
saying "move pivot" but instead swapping it with last number 🗿👍🏻
Needs a bit more of an indepth explaination :/
Honestly the phrasing is confusing. This easier if you ignore half of it and just watch the numbers.
Edit: ok, maybe bad advice..
@@thehammurabichode7994 indeed bad advice
I can now finally sort my life out
why u didn't pick the last element as pivot ? Instead of picking the middle one and then swaping with the last one ...
I study computer science, and once, I had an exam with a few sort algorithms in it. I didn't really study but about twenty minutes before the exam I watched your 2-4 minute videos on these sort algorithms and I passed the exam. Thank you for helping me.
thats gonna b me td lmao
@@fireboywatergirl1625 i am sure you are at the right place.
explained it much fckin better in 4 minutes with 1.5x watchspeed than my teacher in a 90 minutes class, thank you sm
all your videos are short and very useful.
What did you teach? NOTHING!!! You assumed too much and did not make any base reference in order to ground the subject matter and build from it.
Thanks for the feedback, Gary.
I can implement quicksort and this still confused me.
Right? This is the shittiest explanation I've seen
What's so confusing? the pivot gets out of the way, the two halves get on two sides and pivot is swapped back. So you have two halves as you desire. The only thing missing was when there are only two items, you just set them in order without partitioning. Other than that, it's pretty easy to follow.
Michael Sambol, You're amazing! Let's be friends and have fun together!
fuk i cannot understand what the video talk about
what if i encountered an element equal to the pivot
Can anybody explain the relationship between the example and the presucode?
The presucode does not work for [3 5 5 0 3]
The thing is, at the beginning he says you swap item from left with item to right which obviously makes item from left higher index than item from right, but he does it again and only then he swaps with pivot?! It's impossible to see a pattern when there's no pattern in this explanation.
EDIT: "StOp wHeN InDeX oF itemFromLeft > index of itemFromRight" but the first time he swapped it was higher index too so that's what I meant
You don't swap the indices. You just change the numbers in the indices
What if there is no smaller number than tha pivot?
Now this one better!
The pseudocode is not accurate. If the parameter `high` from Quicksort(A, low, high) is inclusive, then line 4 should be Quicksort(A, low, pivot_location - 1). Running this program as it is will cause an endless recursion where `low = 0` and `high = 1`, thus never reaching the base case (low < high).
Oh, great, I didn't understand a shit
There is an error in the pseudo code in the end: leftwall should be incremented before swaping
um didnt understand a single thing
what if the pivot chosen is the largest number in the array? in this case, 8
I read up on this and it’s a pivot is the the max then you are going to get to the end of the array without finding a value to assign for item larger, and that means you have to choose a new pivot. I think an implementation that avoids this error will have to have multiple ways of choosing pivot including choosing first item or choosing last item or choosing a random or just iterating through the list until you find a pivot that works. Whether you have multiple options of choosing the pivot depends on whether duplicate numbers are allowed. If duplicates are not allowed then it is easier. I think random number generation is the most and efficient way of choosing a pivot so I would not include that in my implementation
Yess I finally understood it, having a clear mind the morning before the exam helped
Why the fuck did I choose CS
This is great. The simple explanation and the especially simple pseudocode towards the end makes it easy to understand the core concept of the algorithm.
seems like it takes forever!
LOL this is one of the best and easiest video out there on quick sort. All of you disliking it shouldn't do programming.
I have to admit that the visualisation is great. It helps me understand and implement quicksort by myself clearly, but the pseudo-code is not relative to the walkthrough. Anyway, still a great video.
Writting my A-Levels in computer science was probably the worst decision of my life....
If you don't understand quicksort in 4 min that doesn't make you dumb or the explanation bad. Watch it again and maybe again, work it out in your head, grab a white board. These things don't come easy for everyone. If you're just starting CS get used to it and keep at it!
why would someone use this haha so confusing
Because it is currently the fastest sorting algorithm out there
Why the pseudocode doesn't intuitively reflect the walk through?
(Quote from Wikipedia) "The pivot selection and partitioning steps can be done in several different ways; the choice of specific implementation schemes greatly affects the algorithm's performance."
There are two partition schemes:
1. Lomuto partition scheme, which is the pseudocode provided in the video.
2. Hoare partition scheme, which is the walkthrough in the video.
Comparison (Quote from Wikipedia)
1. "As the Lomuto partition scheme is more compact and easy to understand, it is frequently used in introductory material, although it is less efficient than Hoare's original scheme."
2. "Hoare's scheme is more efficient than Lomuto's partition scheme because it does three times fewer swaps on average, and it creates efficient partitions even when all values are equal."
To understand the Lomuto partition scheme more, I recommend a UA-cam video called "Quicksort: Partitioning an array" by KC Ang.
thank you a lot!
Your pseudo code does not represent the algorithm you explained in the video. Your psuedocode uses only 1 index to check the pivot against, as opposed to the 2 index method you described.
These are some clean tutorials. Thank you for making this!
Very very good video, thank you! I really love how you never stutter over your words, and never say uhm or uhhhh. That makes this very easy to watch.
What
Very good video, I learned quick sort easily thanks to this. Although, I did have to rewatch the "median-of-three" explanation.
If anyone is confused at the 1:10, basically he doesn't go through the loop.
Instead he jumps to when item from left is higher or item from right is smaller etc. There is a left and right pointer that checks for the condition and then left++ or right-- if its not correct.
itemsfromRight goes from 1 cuz its smaller, and then the right-- checks 7, not smaller, right--, checks 8 not smaller, right-- and then it checks the 0 and see that its smaller.
Thanks for the explanation!
what the hell are you talking about this is a church sir
@@jamboy1843 I don't even remember making this comment.
Not recommended
Out of all the sorting algrotiems this one the hard to understand but you understand it you'll understand it.
Your videos are busteling always, keep cooking!
people are complaining but this is gonna come in clutch for my wirtten exam tmr.
Your pseudo code at 04:05 is wrong for both functions Quicksort and partition, inside Quicksort first recursive call should be from low to (pivot_location -1) and inside Partition when A[i] is less than pivot then swap will be done on A[i] and A[leftwall + 1]. Also writing swap(pivot, A[leftwall] is wrong you should write swap(A[low],A[leftwall])
Why is this and Computerphile's explanation so vastly different but the outcome is the same? Which is the correct "quicksort"?
I am a Computer Science student, have watched 100s of videos of quick sort, always skipped this for exams….. But from now on,,, Never
when i search for something on youtube and see one of your videos in the results i genuenly get excited
Ironic how quick sort is the longest of your sort videos...
I remember i wrote a quicksort program understood fully the concept and 6 months later i dont even remember the concept. Quicksort is such a weird algorithm
shouldn't it be swap(A[low], A[leftwall]) instead of swap(pivot, A[leftwall])
Quick sort is really good when sorting numbers by hand pleasedontaskmehowiknow
And if you get [4,3,7,5,8] and 8 is chosen as pivot then itemFromLeft is what? NULL? What then.
"I think you understand the concept so we'll let recursion handle the rest"
NO I DONT ! Why you only used the right part of the list and not the left(2 1 0) ?
The explanation was with Hoare partition scheme but the pseudo code is with Lomuto partition scheme. Those are different. Please check what you copy-paste!
Pseudo code doesn't match to what you were explaining with itemFromLeft/itemFromRight. Where these notions are in the pseudo code?
Really wonder why the hell they call this "Quick Sort" more like "The slowest, easiest to mess up, complex sort."
I get that the average case is what we're after, but if worst case is n² anyway, might as well choose a different sort imo.
Him: “quick sort = pivot”
Me: “WHILE HE HID IN RADIO WE PIVOTED TO VIDEO 🗣️💥”
thank you so insightful :)
me too
yo me too
I was able to write quick sort in a day when I first learned it, and now I completely forgot and feel stupid. This is my major, how tf did I forget this algorithm.
4:11 I think the more precise way to put would be not “chosen properly” but instead “we don’t get very unlucky”.
this ain't how they explained it to us... Like, how many different quicksort are there that the way it's shown are that different from each other...
I don't get how people aren't understanding this explanation, the only thing I'm confused about is what "O" is
Pivot is reference. You just got to put all the values that is larger than the pivot to the right and values smaller than the pivot to the left. Thats all it is. Why are the comments overreacting??
I'm confused about the left and right...the right sometimes go to the left vice versa
You can't say you understand how the recursion works if you don't explain the base case that terminates the recursion. There is a big hole in the explanation for when you hit 1 or 2 elements in the subarray that defines how to end the recursion itself.
Dude wtf this is so confusing you say pick an item from right to pivot but 3 is already right-most... At least mark the center position if you meant to
I don't get it. What if the pivot has no greater than or less than itself? What numbers can it compare to?
Love the videos!
Haha you copied me! Very funny feel like a real bogo sort right now
def quicksort(arr):
if len(arr) < 2:
return arr
else:
pivot = arr[0]
less = [i for i in arr[1:] if i pivot]
return quicksort(less) + [pivot] + quicksort(greater)
This algorithm fails the case for an already sorted list, like [4,5,6]
What if there is a number that is not smaller than pivot or larger than pivod? What if only one of the statements is true? (Only left or only right)
Why 8 is an item from left of 7 >>> both 5 and 8 are itemFromRight ....