Understand Quick Select (In 10 mins)
Вставка
- Опубліковано 28 чер 2024
- It is easy to understand how quick select works, but the partition algorithm is tough to reformulate especially in conditions such as technical interviews. This video will hopefully help you understand how quick select and partition really works so you will never need to memorise this algorithm again.
- Наука та технологія
Believe it or not, this is the best quick select explanation on youtube.For the first timein my life, i can write this algorithm without memorization
You easily had the best video on it, thank you!
I can say this video is the best explanation of the quick select algorithm on UA-cam. I read an article on GeeksforGeeks and only found myself more confused because of poor variable naming such as x and y, and weird way of partitioning like right - left, and so on. The method in this video and the explanation make more sense! Thanks CS Robot!
lowkey the best quickselect explanation ever what
One of the better explanations out there. The thing with partition is that there are various ways to do it and so many nuances with the boundary conditions if you are not careful. There is another method using while loops which I have always found tad bit more difficult. This one is more straightforward.
What a great, down to earth explanation.
straight to the point and no nonse explaination!, thanks for explaining the partition function now I can easily remember the solution
Keep posting these king of videos
Great usage of example and step by step impl explanation.
Keeping it simple
thank you for your explanation it is super clear and concise thank you
thank you so much this helped me understand very quickly
Super good explanation video. This deserves more views
Great Explanation, thank you
This is best as far as I have seen on YT
I was really stuck at I and J pointer.
nailed it 🔥
Awesome explanation. Thanks!!!
Very good explanation, thank you!
thank you so much. that was a great explanation
You have good explanation, Thanks it's help me a lot
really appreciate your way of explaining😇😇
good explanation, thanks
great video , it deserves more views
really well explained
great explanation
great video!
really really good video
Is this works if the last element in an array is the largest?, bcoz the arr[i] and arr[r] swaps at the end of the each iteration right
How do you make these graphics ? Is it a presentation ? Slides , or something like manim ?
thanks
Love from india
this is the first time i can understand algorithms from the first time.
Isn't the third largest element 10 here?
Selecting the last as pivot is risky, selecting a random is much better.
lol no, if the order it's random which almost always is it's the same
@@Fran-kc2gu Depend on the input as you say, but you hit the worst case O(N^2) if the list if already sorted, which is a denial of service attack vector. If your having a critical timeout you must meet you should even go with a median-of-medians.
how can we adopt the partition function to select a random pivot? Just pivot = arr[randint(l, r)] doesn't work
@@surters , if your list is unsorted, arguably list.length - 1 slot will follow a random distribution. Your worst case depends not only on the list but the kth position you're trying to find. It is true, a random selection can reduce worst case chance still, but it really is something you should judge on your use case. Your real world distribution of your list may not hit the worst case scenario as often as other distributions. If your list is small, your usage of random may actually incur more overhead than just selecting a fixed pivot. Don't let big O complexity blind you to the underlying complexity and overhead of the functions you call in your algorithms, or that the complexity depends on external factors to the algorithm, like the expected distribution of your list.
For a DOS attack, your user would have to control the list and search position and the specific implementation would need to affect the shared resources appreciably. Your advice thus is highly specific to a very specific use case and implementation that isn't broadly of concern.
@@JimBob1937 If it is OK that sometimes O(N^2) is acceptable and the data is not depending on potential hostile 3rd party input, it could be OK. If your dealing with potentially hostile 3rd party inputs, depending on a predictable pivot is not advisable, picking a random pivot might be good enough. If on the other hand you can never afford to hit O(N^2) ever, then median of medians is an option. There is tons of literature on the matter.
The time complexity is wrong, its o(n^2) worst case if you select the largest or smallest element in the array
Great explanation, thank you