Quick sort in 4 minutes

Рет қаралды 1,780,137

Күн бұрын

Step by step instructions showing how to run quick sort.
Code: github.com/msambol/dsa/blob/m... (different than video, I added this retroactively)
Sources:
1. Data Structures and Abstractions with Java by Frank M. Carrano [www.amazon.com/Structures-Abs...]
2. www.algorithmist.com/index.php...
LinkedIn: / michael-sambol

Пікірлер: 515

@WhisperingWalnuts 2 жыл бұрын

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

@MichaelSambol 2 жыл бұрын

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!

@westsideslasha Жыл бұрын

@@MichaelSambol I got really confused when the pseudocode didn't match the explanation. You should correct that (in the video) ASAP.

@MichaelSambol Жыл бұрын

@@westsideslasha I'm sorry about that! KZfaq won't let me change the video now unfortunately, but I pinned this comment.

@manavshah448 Жыл бұрын

I am encountering an infinite loop if I change the while condition to be i < j instead of

@amono770 Жыл бұрын

i am glad that i looked at the comment section after having a hard time connecting the pesudo code to the video content.

@EchoVids2u 3 жыл бұрын

With every new quick sort video, I watch, I get more recursively confused.

@Iceron55 3 жыл бұрын

same lol all the quicksort videos use the same words to explain it

@user-wp9pz9hl3z 3 жыл бұрын

hey man, after pulling my hair out for 2 days I finally got it, sadly I had to pay for it.

@HACKINGMADEFUN 3 жыл бұрын

@@user-wp9pz9hl3z what did u pay for?

@user-wp9pz9hl3z 3 жыл бұрын

@@HACKINGMADEFUN a Udemy course

@HACKINGMADEFUN 3 жыл бұрын

@@user-wp9pz9hl3z cool

@jonahrivera7 3 жыл бұрын

Guy: "I think you understand the concept" Me: No I don't

@Evokans 3 жыл бұрын

it gets halved and is recursively applied to both halves in each step

@sleevman2307 3 жыл бұрын

@@Evokans um what?

@faith2756 3 жыл бұрын

@@sleevman2307 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.

@sleevman2307 3 жыл бұрын

@@faith2756 sorry wat?

@faith2756 3 жыл бұрын

@@sleevman2307 Which part exactly do you not understand?

@alanfender123 5 жыл бұрын

i should be working at mcdonalds

@SkillUpMobileGaming 4 жыл бұрын

You really should. *SAD!*

@IStMl 4 жыл бұрын

@@SkillUpMobileGaming You too

@torment6425 4 жыл бұрын

wait what. why

@asailingstone 4 жыл бұрын

lol 😂😂😂

@loklyu5691 4 жыл бұрын

that's what I was thinking. you're a genius pal

@SAMURAIch 4 жыл бұрын

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

@liuqing1995 3 жыл бұрын

understanding the meaning of pivot is the KEY.

@reguret2976 Жыл бұрын

yeah, theitemfromleft, or right wasn't even properly discussed, left of what or right of what exactly?

@skyness9 2 ай бұрын

lol

@banderson924 5 жыл бұрын

So we let magic handle the rest.

@Bridgelessalex 5 жыл бұрын

HAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHAHA

@airex12 5 жыл бұрын

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 5 жыл бұрын

@@airex12 so 8 is the new pivot? How can I go through if there is no number in the array greater than 8?

@airex12 5 жыл бұрын

@@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.

@kennethquilantang8080 5 жыл бұрын

@@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?

@Charoula1608 5 жыл бұрын

*screams in Ross voice* PIVOT! PIVOT! PIVOT!

@peizhiyan2916 5 жыл бұрын

haha, I can't help imaging Ross's face, hahaha

@Daver2212 5 жыл бұрын

Me in future, oh Ross's couch sort?

@Jiwoo15 4 жыл бұрын

screams in Chandler voice SHUT UP! SHUT UP! SHUT UP!

@mahnazha 4 жыл бұрын

Oh my GOOOOD :-))))))))))))) So truuuuueeeeeee

@AbdelhameedG 4 жыл бұрын

This is exactly what came into my mind learning about this :))

@theducksneezes4987 4 жыл бұрын

How to get Confused in 4 minutes then again, this was the best video about it so far

@4TH4RV 4 жыл бұрын

I want more videos like this where they explain stuff in less than 10 minutes

@omegagmysta2092 4 жыл бұрын

Bet ? kzfaq.info/get/bejne/kM5jaruqtrKsm6s.html

@JoelThomas-sr6ti Ай бұрын

there's a video by abdul. i think it is best

@yufangjuan4994 3 жыл бұрын

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.

@noahdirksen3623 2 жыл бұрын

Thats the fanciest wording I've heard, i would use: "You get it or you dont"

@seanzhou2188 Жыл бұрын

Try to sort a few short sequences yourself according to the steps in the video. You may get the "background knowledge".

@LL-rn8rn 5 жыл бұрын

The psudocode is not intuitively reflecting the walkthrough

@diabl2master 4 жыл бұрын

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.

@jscholex 4 жыл бұрын

@@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.

@diabl2master 4 жыл бұрын

@@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.

@jscholex 4 жыл бұрын

@@diabl2master Yeah who knows... but I think we can all agree the pseudocode isn't great hah

@skarfie123 3 жыл бұрын

the pseudocode shows the Lomuto version but the visualisation is for the Hoare version, which is better. See Wikipedia for both.

@nabe4320 6 жыл бұрын

am still confused

@ibu433 5 жыл бұрын

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

@thewiseowl8804 4 жыл бұрын

N Betancourt He made it more confusing, for sure.

@diabl2master 4 жыл бұрын

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.

@omegagmysta2092 4 жыл бұрын

Hope this helps :kzfaq.info/get/bejne/kM5jaruqtrKsm6s.html

@alvin_row 3 жыл бұрын

i hope you got it cute bird from nichijou

@fr5229 6 жыл бұрын

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.

@wendyd.1918 3 жыл бұрын

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.

@fireboywatergirl1625 6 ай бұрын

thats gonna b me td lmao

@wendyd.1918 6 ай бұрын

@@fireboywatergirl1625 i am sure you are at the right place.

@LGNNorotic 4 жыл бұрын

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!

@brianmartinez6193 2 жыл бұрын

I watched several videos, including my school books, and I had no idea what they were saying with left to right and could not get the answers in the correct order because of that. I was able to understand after watching your video and it allowed me to get past my assignment. Thank you.

@MewPurPur 3 жыл бұрын

Yess I finally understood it, having a clear mind the morning before the exam helped

@mehdibadaoui1658 4 жыл бұрын

when i search for something on youtube and see one of your videos in the results i genuenly get excited

@TheAPlayd 4 жыл бұрын

That is the exact! same Quick Sort Algorithm we have been thought. Really good! Thanks

@dh7222 7 жыл бұрын

These are some clean tutorials. Thank you for making this!

@devanshityagi8231 5 жыл бұрын

Wow... You just found a place in my mind where you stored quick sort so deeply.🙋💖😂

@HelloWorld-tn1tl 3 жыл бұрын

This is the first video that made me really understand how to impl quicksort, and it's very short.

@seltonmc 2 жыл бұрын

Your short videos helped me a looot. Thank you so much!

@parthpatel-bt7qw 6 жыл бұрын

This was exactly the kind of video I was looking for!! Short and concise, but no loss of information. Thank you.

@emilgebl8644 3 жыл бұрын

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.

@christianeichmueller8637 Жыл бұрын

Thanks for the explanation!

@jamboy1843 Жыл бұрын

what the hell are you talking about this is a church sir

@emilgebl8644 Жыл бұрын

@@jamboy1843 I don't even remember making this comment.

@chinmayhattewar4456 3 жыл бұрын

Imagine newcomers watching this explanation for the first time.

@bethanylowe8773 3 жыл бұрын

Thank you. I feel the same about my actual online course I'm studying. And I'm a newcomer. I feel better.

@krishnarajj9358 2 жыл бұрын

horrible

@nemesis9410 5 жыл бұрын

This is the most confusing and incoherent visualization of quicksort I've ever seen

@thewiseowl8804 4 жыл бұрын

Well said 👍

@ChristianMay21 4 жыл бұрын

Makes perfect sense to me

@thewiseowl8804 4 жыл бұрын

Christian May That’s so great! 🙌👏

@diabl2master 4 жыл бұрын

I thought the visualisation was fine. I feel that I understand it now.

@cristian-bull 3 жыл бұрын

This is the fist visualisation of quick-sort I've ever seen, so I know it doesn't mean much, but I agree.

@snake3276120 3 жыл бұрын

LOL this is one of the best and easiest video out there on quick sort. All of you disliking it shouldn't do programming.

@Kleyguy7 3 жыл бұрын

I think I'm here for the fourth time now.

@davidrichmond9759 6 жыл бұрын

These 4 minute videos are great for cramming!

@ganimatormusic Жыл бұрын

Thank you so much, i have a pc science test today, and i didn'T understand since i can't speak german that well and i am still learning it, this guy explained it all

@alanperaza5696 4 жыл бұрын

It was quick and I understood everything. Thanks a lot

@Shivam25Verma 2 жыл бұрын

Thank u very much Sir, I got it completely. Actually I'd missed my college online lecture b/c of sleeping... U saved me just night before exam, as urs is the shortest video on YT.

@lemonw3906 3 жыл бұрын

The pseudocode is hard to read, but the variable name "leftwall" is really good, this gives me a vivid concept of how the leftmost larger item was swapped and the "wall" moved.

@hiteshsahu_ 2 жыл бұрын

pseudocode is actually wrong as well !

@blurryhorizon 2 жыл бұрын

@@hiteshsahu_ Exactly, not only 1 pointer moves & stopping when this 1 pointer reaches end of the array, but also only picking leftmost value as pivot

@Kokil92341 Жыл бұрын

@@hiteshsahu_ Exactly , i have wasted so much time over it

@scarlettwang2146 Жыл бұрын

@@blurryhorizon I suppose that in the Partition function, the "pivot = A[low]" should actually be "pivot = A[high]"? Very confusing so I wrote it down and found out that the pseudocode doesn't work properly. // Oh just realised that although pivot = A[low] might works as well but the pseudocode is totally wrong for Partition function jeez..

@kemot25 11 ай бұрын

@@scarlettwang2146 I think it should be as it is. Something else is wrong.

@sushan_karki 5 жыл бұрын

watching this video from NEPAL. Great sir. THANK YOU.

@noddycode7324 5 жыл бұрын

QuickSort has always been a bit of a mystery to me, but somehow this video instantly made it click. Thank you so much!

@Crzynoob 4 жыл бұрын

Psuedo code does not match demonstrated algorithm.

@ToriliaShine 2 жыл бұрын

thank u so much, i have an exam tommorow and was stressing bc i couldnt figure out how quick sort work with my teacher's explanation and this just simplified it easily. tysm ;-;

@jarencascino7862 3 жыл бұрын

This is exactly what I was looking for in a video

@reytampubolon6390 2 жыл бұрын

currently studying for my Algorithms and Data Structure exam, your video is very helpful :) thanks

@Agman3a 2 жыл бұрын

Thank you so much! I was having so much trouble understanding this algorithm but you saved me in 4 minutes.

@VictorBanerjeeF 4 жыл бұрын

Thanks Brother, You save my 10 min exam fast revision time

@joshuabrown604 2 жыл бұрын

Thank you so much! Just understood how to do a quick sort in a few minutes. Fantastic Video! Keep up the great work 😀

@sachinpathy6940 2 жыл бұрын

i put this at 1.5x and now i learnt quick sort 2.6667 minutes

@paulmerg 4 жыл бұрын

very well explained and visualised!! thank you!

@yessirski7868 2 ай бұрын

people are complaining but this is gonna come in clutch for my wirtten exam tmr.

@ragavendhart 5 жыл бұрын

I guess, In the quicksort explanation he moves the pivot to the RIGHT END of the array. In the pseudocode, he moves the pivot to the LEFT end of the array. And after the swapping is done, he then brings the pivot to the original position from the LEFTEND. I've seen too many quicksort algorithm videos and this works the best for all my cases.

@haloum Жыл бұрын

this made it a lot more logical for me, thank you.

@M15onehundred 4 жыл бұрын

Nice! Glad to see magic still exists!

@senaszel 4 жыл бұрын

Helped me. Great vid. Fan of your since now. Cheers.

@lil-mi-777 2 жыл бұрын

The video hold the key of quicksort, most clear to me!

@akira_asahi Жыл бұрын

Thank you for the video. I am grateful for your time and contribution. Kind regards, Akira.

@ZuleyenineIbneNoman 2 жыл бұрын

You did a great job man! It helps me a lot . Thank you so much.

@seanzhou2188 Жыл бұрын

Thanks for the concise and succinct tutorial.

@user-fc5ou7pn2k 2 жыл бұрын

amazing, ive got an exam tmrw... this lesson is much appriciated as my professor is not very good at explaining these basics

@mirana7660 2 жыл бұрын

it's 8:48 AM, i have an exam at 15:30 PM and ur saving me here

@godaimer999 2 жыл бұрын

explained it much fckin better in 4 minutes with 1.5x watchspeed than my teacher in a 90 minutes class, thank you sm

@denisf5664 4 жыл бұрын

I have a question: if I skip using a "while" the smaller elements from the beginning than pivot is not more efficient? And I think that because the computer is exempt from doing the first swaps

@mitchross4002 Жыл бұрын

God bless you man this is by far the most straightforward and comprehensible explanation of quicksort, really got me out of a pickle with this one.

@MichaelSambol Жыл бұрын

God bless, Mitch

@DT-ll8og 2 жыл бұрын

Thanks for clear explanation. Correct Position for Pivot, let recursive do remains. Good job man.

@walteramenya5759 6 жыл бұрын

here for the comments

@thehammurabichode7994 4 жыл бұрын

VERY UNIQUE TASTE 8|

@hassanakhtar7874 4 жыл бұрын

Wtf

@nolanrudolph5463 5 жыл бұрын

I feel like the pseudo code would reflect the presentation a lot more if we let pivot be A[high] with rightwall=high-1. Then the conditional statement to initiate swap would be if(A[i]>pivot), and of course having rightwall=rightwall+1

@chetanphoenix 3 жыл бұрын

I really like this explanation. This moves the pivot out of the way and swaps it back with the itemFromLeft pointer. That's so much easier than some other videos I've seen where the pivot is in the middle of the action and we're confused with >= or

@ggg-tq9be 2 жыл бұрын

yes! It is cool!

@LR-ke5pw 3 жыл бұрын

I actually understand a little bit now, thanks!

@SuperJosba 2 жыл бұрын

Perfect explanation of quick sort!!

@yahiashams2334 2 жыл бұрын

That without voice over made the video from great to perfect

@swetashinde1184 6 жыл бұрын

Great videos I like your work :) It is very easy and quick .. All the best for future videos and work

@J4T375 3 жыл бұрын

all your videos are short and very useful.

@pebble2258 3 жыл бұрын

The comments on this video do not reflect the like/dislike ratio.

@miso-ge1gz 7 ай бұрын

i cannot even describe how much i hate learning these, thanks for the video it helps a lot

@arminkrahbar 2 жыл бұрын

The visualization is perfect!

@cb350_ 4 жыл бұрын

Thank you finally understood quicksort 😌😌

@MoguMogu818 3 ай бұрын

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.

@SarveRadhaNaam Жыл бұрын

don't you think at 4:04 , in Partition code. leftwall++ should be before swap(A[i], A[leftwall])

@JA-vt1mh 3 жыл бұрын

this is a very clear explanation, thanks

@bryanbocao4906 6 жыл бұрын

Great tutorial! Actually I understood this concept from this video in less than 4 mins.

@kellypeng6371 5 жыл бұрын

Thank you dude you save me from the finals.....

@birhaneshzaza9892 4 жыл бұрын

thank you

@user-ev6er5vg6s 2 жыл бұрын

There is an error in the pseudo code in the end: leftwall should be incremented before swaping

@DeusNudus 4 жыл бұрын

Code is not right. "leftwall = leftwall + 1;" needs to happen right before "swap(array[i], array[leftwall]);" not after it.

@charleschoi5907 4 жыл бұрын

Agree!

@minefacex 3 жыл бұрын

This will be useful for tomorrow's exam.

@karaqore 2 жыл бұрын

Hvala ti brate pomogao si mi puno u životu

@georgygursky4303 4 жыл бұрын

This is a good explanation, thanks !

@Athanas007 4 жыл бұрын

0:10 who else thought of Ross screaming Pivot from that Friends Episode

@biggiechungus784 Жыл бұрын

Oh damn. When it's explained like this, it really makes sense. I could totally code this lmao

@smbowner 3 ай бұрын

Hey, Thanks for the explanasion, It was a clear and concise video, however the pseudocode is somewhat wrong I believe in 3 things: In Partition, the order of operations is not correct: increment leftwall first, then swap. The final swap in Partition is not correctly swapping the pivot's original position with A[leftwall]. The recursive calls in Quicksort should be updated to exclude the pivot_location from the ranges, properly dividing the array into segments that exclude the sorted pivot. here is the corrected version: Quicksort(A as array, low as int, high as int) if (low < high) pivot_location = Partition(A, low, high) Quicksort(A, low, pivot_location - 1) Quicksort(A, pivot_location + 1, high) Partition(A as array, low as int, high as int) pivot = A[low] leftwall = low for i = low + 1 to high if (A[i] < pivot) then leftwall = leftwall + 1 swap(A[i], A[leftwall]) swap(A[low], A[leftwall]) return(leftwall) Thanks again!

@vibhuarora2911 5 жыл бұрын

Best explanation yet compared to all other one available on YT. Thanks!

@dularamalindu427 4 жыл бұрын

Thank you. Vell explained. and easy to understand

@bohdankholmaniuk8023 5 жыл бұрын

Thanks, it really helped.

@vinjetho1609 6 ай бұрын

dont know if people will still answer questions on this video, but i tried implenting this, but i have a problem with when there's two or more copies of the smallest value it gets stuck because it tries ti continue until the index of item from right is at the end of the list, but since there are multiple of the same values at the end of the list, index of item from right doesnt continue to decrease. Basically: how do i check that it has completed one pass and the smallest/largest item is at the end?

@Rglezy 3 жыл бұрын

FINALY SOMEONE WITH CLEAR INSTRUCTIONS

@grevierx 2 жыл бұрын

How do you find the median of three "middle" value on an even number of elements in a list?

@jeffchai6561 3 жыл бұрын

This algo is akin to a toddler randomly sorting numbers around until they're in order

@kylemarcusenriquez4770 5 жыл бұрын

2:49 I'm assuming you skipped the part where if they were equal you'd continue?

@docteurraton7280 4 жыл бұрын

You mean itemFromLeft and ItemFromRight? They can't be equal beause they were chosen to be greater and lower than the pivot

@milenkopizdic9217 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

@chetanphoenix 3 жыл бұрын

You don't swap the indices. You just change the numbers in the indices

@arshadsameemdeen391 5 жыл бұрын

Doesn't this guy know Left and Right or what

@charlesjsescoto 3 жыл бұрын

Lol

@zolongOne 3 жыл бұрын

lol

@charlesjsescoto 3 жыл бұрын

@@zolongOne lol again

@Jack-dx7qb 4 жыл бұрын

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 KZfaq video called "Quicksort: Partitioning an array" by KC Ang.

@ggg-tq9be 2 жыл бұрын

thank you a lot!

@IOSALive 2 ай бұрын

Michael Sambol, You're amazing! Let's be friends and have fun together!

@myhoop 6 жыл бұрын

I think what you explain at 1m14s "itemFromLeft that is smaller than pivot", "itemFromRight that is smaller than pivot" is not represented in the pseudo code. The pseudo codes iterates only from one side.