Learn the basics of quicksort. This video is a part of HackerRank's Cracking The Coding Interview Tutorial with Gayle Laakmann McDowell. www.hackerrank.com/domains/tut...
Every single quick sort video uses a different method, and they all do at least one weird thing without explaining. I'm not even sure if quick sort is a real thing at this point :)
the smiley face doesn't make much sense in this context. I think that it all does the same thing just some methods keep the same array while others split it into different ones using recursion/multidimensionalarrays. Regardless, it appears that these two methods depend on what kind of approach you're taking -- loops or recursion.
@@IStMl I'm learning computer science by myself. Do I need to be good at and understand every algorithms? I do understand them but I can't write them by myself without researching on the internet.
You should not compute the middle point as (left + right)/2. If the array is very large (>2G) then the result of "left + right" may overflow and become negative. The proper way of choosing the midpoint pivot is: "left + (right-left)/2" which is mathematically equivalent but immune to overflow as "right > left" is an invariant that always holds and if "right" is representable then, "left" is also representable the result will never overflow. as it will be less than "right".
Bros, the video is actually correct. Ill attempt to clarify, but i have a mild form of downs syndrome so please be gentle. The pivot, (i like to call it the pivotValue for clarification), is just a number she selected randomly. In her code she just extracts the value at the arrays middle index, and its just a number you will compare all the other numbers to :) Now for part two, she makes two pointers, these move towards each other, which kind of separates all the values into two piles "bigger than or equal to pivotValue: 7" and "smaller than pivotValue: 7".. And thats what you are seeing when the two arrows meet. The meeting point of the two arrows are kind of like a wall, separating the two piles, which will then be treated separately, and each of them will have quicksort() performed on them later. So in the right pile, you have "7 and greater", and in the left pile, you have "smaller than 7". And now the fun starts all over, the calls quicksort() on the left pile, and then right pile.
IMPORTANT: the solution from the code in the video does sort the array, while the algorithm is wrong actually. It's very "quicksort", but it's not standard quicksort. To verify my point, you can run a demo in your IDE with debug mode, and watch how the pointers moving, and how the pivot moving. As many comments mentioned, the explanation and the code CONFUSING people. I won't suggest beginners waste time watching this video.
Although this implementation and explanation was quite clear to me (though I'm seeing this as revision not learning it first time), I do understand why it may be confusing for new learners watching this, so just 2 things that I didn't think was explained well to hopefully clarify some people: 1. Pivot is NOT THE SAME as the partition point where you choose where to split the array in your current iteration: In the initial video explanation, don't be mistaken thinking that because the pivot is 7, then it is also where the partition is split, therefore everything before 7 should be less, and everything after 7 should be bigger. Also, the video is not wrong when it did not swap 8 and 7 (I see a lot of complaining comments on this), because it's really just up to the implementation itself. It could well be if right index >= pivot then keep moving, so since 7 == 7 then right index keep moving (and it does look like it since you see it sets partition point between 5 and 8, where everything before 5 is less than pivot and everything after 8 is equal to or greater than pivot, as there can always be duplicate numbers in the array and that could be the pivot number itself). 2. What you return as the partition index in the partition method DEPENDS ON YOUR IMPLEMENTATION: Since the point where you partition the arrays is in between two elements, it's completely up to you on how you want to represent this point in the array. In this case, the partition method is returning left because the while loop only exits when left and right cross-over each other, meaning left will be the index of the BEGINNING of the right-hand-side partition, and right will be the index of the END of the left-hand-side partition, and in the quickSort recursive method it calls to quickSort the left-hand-side partition with boundaries between left to "index-1", and right-hand-side partition between "index" to right. By all means, in partition method, you could choose to return right instead of left, then simply have quickSort call left to "index", and "index+1" to right. Or do some other kind of calculation to get your partition index, It is completely up to you. Hope this helps!
Thanks, the pivot versus partition point was what got me in this one. I saw the 8 go to the left of 7 and then I got lost from there on out. But having the partition point where the 2 pointers meet makes total sense.
The animation and her implementation are different. In her implementation she has while arr[right]>pivot, keep moving but in the animation the condition is arr[right]>=pivot.
No, 7 is not in its final position, thereforce the algorithm they used is wrong. After each iteration of the sort, one entry must be in its final position.
@@tomleeyrc40 That's not necessary under this quicksort implementation. After each iteration the array is partitioned in two halves with respect to the pivot. the pivot can fall anywhere in the two halves, what matter is that everything less(or equal) is on the left half and everything greater(or equal) on the right half. Repeat recursively for each halves until the size==1 and the array is sorted.
I just want to point out that the book example is completely different. Additionally I think it will be useful for people watching this to know that the "random" part of this isn't the index being chosen because that is not random, it's always the middle of the array. The value found in the middle of the array is what is unknown and random hence the O(n^2) possibility. I just wanted to make that very clear.
At 1.48min you said everything smaller than one side and bigger than other side of the pivot, where there is 8 exactly left to 7 which is pivot. Please explain.....
she's saying that you can cut the array in two parts with each part containing only numbers smaller/greater than the pivot. in this case you could cut between 5 and 8 :)
The index of our pivot element is NOT our separating index. Which only makes sense, because we are assuming a randomly sorted array, so the randomly chosen value could also be the biggest in our whole dataset. Instead we'll keep moving the left and right index until left > right, which means that left has run over right. The right and left partitions are now still unsorted, which is the point of the quicksort algorithm. I hope this helps.
Looks like this video mixes pivot definition/purpose from one partition scheme with implementation of another one. Thus the confusion. en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme
The algorithm states that after each partinioining, the pivot will go into his final position, and that's not the case there. source: algs4.cs.princeton.edu/23quicksort/, en.wikipedia.org/wiki/Quicksort
I think the error is not with the sorting of the values -- that is perfectly correct. The error is with where the left and right indices have ended. Left and right should criss-cross (at least from the code from my University notes) so in the first partition left ends at index 5 and right at index 4. This is further validated if you reuse this idea for the quick select algorithm.
I understood at the first time watching the video. It ve never happened before with the other algorithm video explanations so I think this channel deserves a good thank you. Best wishes, thumbs up
1:56 You said everything bigger than pivot (pivot = 7) is now at right side and everything smaller than pivot is now at left side of pivot. But 8 is still leftside of 7. Why?
No, it means everything smaller than the pivot is in a left section and everything larger than the pivot is after that left section. The dividing index between the two sections does NOT need to be the pivot itself.
Nice video, does this actually work from observation it seems like it would break for an input [2,3,1] in the line of code that says "while(array[left] < pivot)" or when pivot is the largest element this would raise an index out of bounds error would it not?
for those watching, (left + right) / 2 can cause overflow. the author surely knows this, but might've assumed others do too. It is safer to do (left + (right - left) / 2) to avoid overflow.
code will work well if made following changes while (left < right) { while (arr[left] < pivot) left++; while (arr[right] > pivot) right--; if (left < right) { swap(&arr[left], &arr[right]); } }
A working implementation similar to her theory in case anyone is wondering. . . function quicksort(arr, low, high){ if(low < high){ let p = partition(arr, low, high); quicksort(arr, low, p); quicksort(arr, p+1, high); } } function partition(arr, low, high){ let pivot = arr[low + Math.floor((high - low)/2)]; let l = low, h = high; while(true){ while(arr[l] < pivot){ l++; } while(arr[h] > pivot){ h--; } if(l >= h) return h; // Swap low and high element [arr[l],arr[h]] = [arr[h],arr[l]]; // In case it swapped repeated elements, // decrement higher indexes // so it will not go infinite loop. if(arr[l] === arr[h]) h--; } }
1:54 if 7 is the pivot, then after all the swappings, 'right' and 'pivot' should be swapped. Only then the 'pivot' will be in it's correct position, as per the algorithm.
no, because you still want to swap when "left" index is smaller than "right" index. Technically speaking, you should take out equal sign and just have it "
@@CJKims that's actually incorrect. I ran this myself and took out the equal sign and the outer while loop ran infinitely long. It's understandable, because imagine at the end of a partition, we have left = right. And the all the left sides have been sorted, and all the right sides have also been sorted (in the sense that they are smaller/greater than the pivot). Now, the outer while loop will keep continuing, since left
Actually i got confused by (left and right) i mean which one is value and which one is index. There should have been some distinction for them but the explanation was really good. Though code was a bit confusing.
This feels like merge's sort little annoying cousin. Haha. Thanks a lot for the explanation. Very clear and on point. I understood just watching it once.
In the real world its actually very practical to implement your own algorithms. Take Doom 3 for example. The developers implemented all their own libraries to ensure the code ran as fast as possible with minimal file sizes. This was very important as if they used existing libraries the code would of took up much more space and may of even prevented it from running on most consoles back in the day. This is also the case for embedded os with low computation power. Also 8 is greater than 7...
Thank you, this helped me out so much! Also I can't be the only one to find it funny how the numbers and colorful letters fly around the screen during your example haha
Try example {1,2,3,2}, and you will find the pi for the first partition is wrong, although the last result is correct. Let's go through it: 1st partition: pivot=2 * Initially: left = 0; right = 3; * After 1st loop: left = 2, right = 2 * After 2nd loop: left = 2, right = 1 * Exit from 3rd loop condition check * Return 2 But actually it should return 1. This implementation seems have bugs in it.
In second iteration, when we sort {6,3,1,2,5} i understand we swap 6 with 2. According to the code provided later, after the swap the left pointer moves ahead while the right moves back. However, in the video only the left pointer is moved ahead, while the right pointer remained in place... I think if the right pointer is moved back as well as it should be, then in next iteration, 3 and 1 would get swapped resulting in {2,1,3,6,5} while the next sub-arrays would be {2,1} and {3,6,5}... Plz correct if wrong
This implementation only works when pivot = left + (right - left) // 2 (Doesn't work on pivot = right). However, a more sufficient quicksort implementation should comply for any potential pivot point, that's the point for using quicksort
In this case, yes. Since pivot is (left + right) /2 But suppose its random, then the left/right index will move beyond the pivot point. (I hope Im assuming that was the issue, and i explained the correct thing haha)
Santina asked this question... and it's at that point the interviewer decided you can't be coached up, and therefore they can't work with you at this time. Isn't it fun?
Hi Gayle - I just want to thank you for taking the time for these videos - you're visual style is extremely beneficial for me (visual learner). I am grateful...
This does not show what the code is doing, it's describing what's happening in the algorithm but from abstract overview. As a coder I like seeing both an abstract outlook but also explanations of the inner workings by desk-checking and tracing the execution of the code.
This is In response to the older comments below about variations in quicksort. The partition algorithm shown in this video doesn't move the pivot value, but does swap elements so that all elements less than pivot are located before all elements greater than pivot, and elements equal to pivot are not swapped. Other partition algorithms, such as Hoare partition scheme, will end up swapping the pivot element to it's proper sorted location, swap all elements less than pivot before the pivot, swap all elements greater than pivot after the pivot, while elements equal to pivot may or may not be swapped, and can end up before or after the pivot.
I wish she did the quicksort on the right side instead of the left @ 2:00 Once pivot is on the 7, the left pointer is stuck on the 8. Looks like her strategy would have the new partitions be [8][7,9,15]
While loop condition is very confusing. Say X is pivot, K is left element and Q is right element which means when you get to "IF" statement, it should satisfy this condition K > X and Q < X. If K is greater than X then K can never be smaller then Q because Q is smaller than K. It would only execute if K=Q.
left and right aren't the values 15 and 6, they are the index numbers. the conditional statement is ensuring that the left and right pointers haven't crossed each other
3:23 When there is a sequence of number 213 and you make 1 as pivot, it is never sorted! coz 2 and 3 should both appear on the right side and they can not be swaped !!
Is that really correct? I know after first sort , left side elements must be smaller than pivot and right side elements must be larger than pivot element but in this example, you have 8 still at left side and not well separated. So your code must compare pivot and 8 and swap them too
According to the code, the pivot can end up getting swapped, unlike in the animation at the beginning where the pivot was skipped. Am I seeing this correctly?
You are correct, the code does not match the animation or her verbal description. The left scan stops at elements >= pivot, and the right scan stops at elements
emmm.. wouldn't the first while loop within the while loop accumulate the left until it reaches < pivot (while doing nothing)? then move on to the next execution point? You sure this is right?
I am confused, as much as i learnt every element on the left side of the pivot must be smaller than the pivot and every element on the right of the pivot must be larger than the pivot. 8 > 7 yet you kept it on the left of the pivot.
Wow, some insane comments. I like this implementation, although the upfront explanation was challenging to follow. Before someone comments that she has copied and pasted the solution, no kidding, since the original solution was invented by Tony Hoare in 1959, I couldn't find his RUclips channel, unfortunately.
Наука
Every single quick sort video uses a different method, and they all do at least one weird thing without explaining. I'm not even sure if quick sort is a real thing at this point :)
Cheyno Mdingi Lol
So true, I'm having the same problem ahah
the smiley face doesn't make much sense in this context. I think that it all does the same thing just some methods keep the same array while others split it into different ones using recursion/multidimensionalarrays. Regardless, it appears that these two methods depend on what kind of approach you're taking -- loops or recursion.
This is the method that I was taught at Uni.
@@OneTimeCrazy smiley face makes sense but a laughing face XD would be better received by more people I guess.
Who here only 15 year professional development experience and I still only use these algorithms in interviews.
I watched over 40 videos about this algorithm. I still have no clue.
@@hujake5406 ouch
Depends if ur more soft eng or work in theoretical computer science
@@IStMl I'm learning computer science by myself. Do I need to be good at and understand every algorithms? I do understand them but I can't write them by myself without researching on the internet.
@@hujake5406 always check explanation and code in parallel
I understood the video at first. But, then I went into the comment section
lol same
You should not compute the middle point as (left + right)/2. If the array is very large (>2G) then the result of "left + right" may overflow and become negative. The proper way of choosing the midpoint pivot is: "left + (right-left)/2" which is mathematically equivalent but immune to overflow as "right > left" is an invariant that always holds and if "right" is representable then, "left" is also representable the result will never overflow. as it will be less than "right".
Emily Björk i
It was a bug that was in C library for 30 years until someone discovered it due to an error using big data.
this is a big plus in the interview
Very good point ma'am.
A much appreciated tip!
Hmm... all these years I thought 8 was bigger than 7.
I like Gayle... But 8 should really be swapped with the pivot 7..... This tutorial is VERY confusing....
Bros, the video is actually correct. Ill attempt to clarify, but i have a mild form of downs syndrome so please be gentle.
The pivot, (i like to call it the pivotValue for clarification), is just a number she selected randomly. In her code she just extracts the value at the arrays middle index, and its just a number you will compare all the other numbers to :)
Now for part two, she makes two pointers, these move towards each other, which kind of separates all the values into two piles "bigger than or equal to pivotValue: 7" and "smaller than pivotValue: 7".. And thats what you are seeing when the two arrows meet. The meeting point of the two arrows are kind of like a wall, separating the two piles, which will then be treated separately, and each of them will have quicksort() performed on them later.
So in the right pile, you have "7 and greater", and in the left pile, you have "smaller than 7".
And now the fun starts all over, the calls quicksort() on the left pile, and then right pile.
@Alexander K. Thanks that helped a lot
@@doktoren99 That was a brilliant explanation!
"All elements less than 7 should be before all elements greater than 7" is what she said which means its all true
IMPORTANT: the solution from the code in the video does sort the array, while the algorithm is wrong actually. It's very "quicksort", but it's not standard quicksort. To verify my point, you can run a demo in your IDE with debug mode, and watch how the pointers moving, and how the pivot moving. As many comments mentioned, the explanation and the code CONFUSING people. I won't suggest beginners waste time watching this video.
Don't even know why he's using a pointer. Just make 2 arrays 1 for left and 1 for right and let them sort by recursion.
@@anonymunsichtbar3715 I think that if you have a very large array It should use a lot of memory and we don't want that, but its a good point from you
Although this implementation and explanation was quite clear to me (though I'm seeing this as revision not learning it first time), I do understand why it may be confusing for new learners watching this, so just 2 things that I didn't think was explained well to hopefully clarify some people:
1. Pivot is NOT THE SAME as the partition point where you choose where to split the array in your current iteration: In the initial video explanation, don't be mistaken thinking that because the pivot is 7, then it is also where the partition is split, therefore everything before 7 should be less, and everything after 7 should be bigger. Also, the video is not wrong when it did not swap 8 and 7 (I see a lot of complaining comments on this), because it's really just up to the implementation itself. It could well be if right index >= pivot then keep moving, so since 7 == 7 then right index keep moving (and it does look like it since you see it sets partition point between 5 and 8, where everything before 5 is less than pivot and everything after 8 is equal to or greater than pivot, as there can always be duplicate numbers in the array and that could be the pivot number itself).
2. What you return as the partition index in the partition method DEPENDS ON YOUR IMPLEMENTATION: Since the point where you partition the arrays is in between two elements, it's completely up to you on how you want to represent this point in the array. In this case, the partition method is returning left because the while loop only exits when left and right cross-over each other, meaning left will be the index of the BEGINNING of the right-hand-side partition, and right will be the index of the END of the left-hand-side partition, and in the quickSort recursive method it calls to quickSort the left-hand-side partition with boundaries between left to "index-1", and right-hand-side partition between "index" to right. By all means, in partition method, you could choose to return right instead of left, then simply have quickSort call left to "index", and "index+1" to right. Or do some other kind of calculation to get your partition index, It is completely up to you.
Hope this helps!
Thanks, the pivot versus partition point was what got me in this one. I saw the 8 go to the left of 7 and then I got lost from there on out. But having the partition point where the 2 pointers meet makes total sense.
The animation and her implementation are different. In her implementation she has while arr[right]>pivot, keep moving but in the animation the condition is arr[right]>=pivot.
No, 7 is not in its final position, thereforce the algorithm they used is wrong. After each iteration of the sort, one entry must be in its final position.
Actually, her animation is right. Even though the condition is arr[right]>pivot ( and arr[left]=pivot on one side and
@@tomleeyrc40 That's not necessary under this quicksort implementation.
After each iteration the array is partitioned in two halves with respect to the pivot. the pivot can fall anywhere in the two halves, what matter is that everything less(or equal) is on the left half and everything greater(or equal) on the right half.
Repeat recursively for each halves until the size==1 and the array is sorted.
I just want to point out that the book example is completely different. Additionally I think it will be useful for people watching this to know that the "random" part of this isn't the index being chosen because that is not random, it's always the middle of the array. The value found in the middle of the array is what is unknown and random hence the O(n^2) possibility. I just wanted to make that very clear.
At 1.48min you said everything smaller than one side and bigger than other side of the pivot, where there is 8 exactly left to 7 which is pivot. Please explain.....
ERROR 404
she's saying that you can cut the array in two parts with each part containing only numbers smaller/greater than the pivot. in this case you could cut between 5 and 8 :)
The index of our pivot element is NOT our separating index. Which only makes sense, because we are assuming a randomly sorted array, so the randomly chosen value could also be the biggest in our whole dataset. Instead we'll keep moving the left and right index until left > right, which means that left has run over right. The right and left partitions are now still unsorted, which is the point of the quicksort algorithm. I hope this helps.
Looks like this video mixes pivot definition/purpose from one partition scheme with implementation of another one. Thus the confusion. en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme
The algorithm states that after each partinioining, the pivot will go into his final position, and that's not the case there. source: algs4.cs.princeton.edu/23quicksort/, en.wikipedia.org/wiki/Quicksort
I've been trying to understand it for the last few months because the book I have is terrible at explaining things. Now it all make sense.
I think the error is not with the sorting of the values -- that is perfectly correct.
The error is with where the left and right indices have ended. Left and right should criss-cross (at least from the code from my University notes) so in the first partition left ends at index 5 and right at index 4.
This is further validated if you reuse this idea for the quick select algorithm.
GitHub copilot sent me from inside VS Code when I was asking about quicksort, commented with the link. What a time to be alive!
Thanks for the code. I think it works. However, the aesthetics in this video don't make up for a bad explanation.
I understood at the first time watching the video. It ve never happened before with the other algorithm video explanations so I think this channel deserves a good thank you.
Best wishes, thumbs up
1:56 You said everything bigger than pivot (pivot = 7) is now at right side and everything smaller than pivot is now at left side of pivot. But 8 is still leftside of 7. Why?
Lol my thoughts exactly... Went straight to the comments to see if I was crazy or not
No, it means everything smaller than the pivot is in a left section and everything larger than the pivot is after that left section. The dividing index between the two sections does NOT need to be the pivot itself.
This is honestly so much more useful than college was...
public static void swap(int [] array, int left, int right){
int temp =0;
temp= array[right];
array[right]= array[left];
array[left]= temp;
}
array[left] = array[left] + array[right];
array[right] = array[left] - array[right];
array[left] = array[left] - array[right];
Hell yeah thanks man
Christine Hill
array[left] ^= array[right];
array[right] ^= array[left];
array[left] ^= array[right];
Great explanation. And the code works, too.
Nice video, does this actually work from observation it seems like it would break for an input [2,3,1] in the line of code that says "while(array[left] < pivot)" or when pivot is the largest element this would raise an index out of bounds error would it not?
for those watching, (left + right) / 2 can cause overflow. the author surely knows this, but might've assumed others do too. It is safer to do (left + (right - left) / 2) to avoid overflow.
Nice and short videos. Really good for reviewing.
code will work well if made following changes
while (left < right)
{
while (arr[left] < pivot)
left++;
while (arr[right] > pivot)
right--;
if (left < right) {
swap(&arr[left], &arr[right]);
}
}
It works either way
nice vid
+ another way to implement quicksort
I implemented this in C++ with vectors and it worked.
A working implementation similar to her theory in case anyone is wondering.
.
.
function quicksort(arr, low, high){
if(low < high){
let p = partition(arr, low, high);
quicksort(arr, low, p);
quicksort(arr, p+1, high);
}
}
function partition(arr, low, high){
let pivot = arr[low + Math.floor((high - low)/2)];
let l = low, h = high;
while(true){
while(arr[l] < pivot){
l++;
}
while(arr[h] > pivot){
h--;
}
if(l >= h) return h;
// Swap low and high element
[arr[l],arr[h]] = [arr[h],arr[l]];
// In case it swapped repeated elements,
// decrement higher indexes
// so it will not go infinite loop.
if(arr[l] === arr[h]) h--;
}
}
Now it makes sense finally!!!
1:54 if 7 is the pivot, then after all the swappings, 'right' and 'pivot' should be swapped. Only then the 'pivot' will be in it's correct position, as per the algorithm.
awesome tutorials , thanks a ton
Comment section of this video is more useful than the video itself.
true
its called community! it helps!
mistake in a hackerrank video! this is the day world ends!
is there anything wrong in line 32???
I think the condition of the "if function" should be (left>right)
no, because you still want to swap when "left" index is smaller than "right" index. Technically speaking, you should take out equal sign and just have it "
@@CJKims that's actually incorrect. I ran this myself and took out the equal sign and the outer while loop ran infinitely long. It's understandable, because imagine at the end of a partition, we have left = right. And the all the left sides have been sorted, and all the right sides have also been sorted (in the sense that they are smaller/greater than the pivot). Now, the outer while loop will keep continuing, since left
Actually i got confused by (left and right) i mean which one is value and which one is index. There should have been some distinction for them but the explanation was really good. Though code was a bit confusing.
I think at 1:45 it missed a step which is swaping "8" with the pivot"7"
This feels like merge's sort little annoying cousin. Haha. Thanks a lot for the explanation. Very clear and on point. I understood just watching it once.
In the real world its actually very practical to implement your own algorithms. Take Doom 3 for example. The developers implemented all their own libraries to ensure the code ran as fast as possible with minimal file sizes. This was very important as if they used existing libraries the code would of took up much more space and may of even prevented it from running on most consoles back in the day. This is also the case for embedded os with low computation power. Also 8 is greater than 7...
Please run your code to make sure it works before publishing an instructional video.
Thank you, this helped me out so much!
Also I can't be the only one to find it funny how the numbers and colorful letters fly around the screen during your example haha
Try example {1,2,3,2}, and you will find the pi for the first partition is wrong, although the last result is correct.
Let's go through it:
1st partition:
pivot=2
* Initially: left = 0; right = 3;
* After 1st loop: left = 2, right = 2
* After 2nd loop: left = 2, right = 1
* Exit from 3rd loop condition check
* Return 2
But actually it should return 1. This implementation seems have bugs in it.
In second iteration, when we sort {6,3,1,2,5} i understand we swap 6 with 2. According to the code provided later, after the swap the left pointer moves ahead while the right moves back. However, in the video only the left pointer is moved ahead, while the right pointer remained in place...
I think if the right pointer is moved back as well as it should be, then in next iteration, 3 and 1 would get swapped resulting in {2,1,3,6,5} while the next sub-arrays would be {2,1} and {3,6,5}...
Plz correct if wrong
For [2, 3, 1], what if we somehow chose 1 as pivot, it seems there is no swap, so it doesn’t seem to work.
Also, we do we do with [6, 5]?
It actually works just follow code. After the second partition ur array will be sorted
if you first find the exact median/index item, then you can always median bucket sort to get O(n log n) performance
Hello, just to say regardless of the video. There is a Korean coding interview book right next to Apple computer.
That's a bug inside the code. For example, it'll never stop if the input array is [6, 3, 1, 2, 5], and the pivot is 1.
How 2,1 becomes 1,2? I think it is the most complicated part..... Many teachers don't explain the last part, when only 2 components remain .
Why so many dislikes? That was the best you can learn of quicksort in under 10 mins.
This implementation only works when pivot = left + (right - left) // 2 (Doesn't work on pivot = right). However, a more sufficient quicksort implementation should comply for any potential pivot point, that's the point for using quicksort
These videos are great
Thanks, great explanation! :)
Thanks a lot Gayle, your explanation is crystal clear.
Hi Gayle, liking your book CTCI!
Thanks. That video helped alot.
you forgot one of the basic step in there which lead to this all confusion among the viewers
Correct me if I'm wrong. I'm guessing you don't really need the check "if (left
In this case, yes. Since pivot is (left + right) /2
But suppose its random, then the left/right index will move beyond the pivot point. (I hope Im assuming that was the issue, and i explained the correct thing haha)
Santina asked this question... and it's at that point the interviewer decided you can't be coached up, and therefore they can't work with you at this time. Isn't it fun?
Yeah, I took the pivot element as the left index and it was not working if I didn't have that "if(left
Santina DM me. You're hot and I need to know more about you. 你說中文嗎
The code used to explain quicksort is not completely right.
code is not working
Totally confused by this explanation. I haven't written a quicksort in about two months, so I forgot how. But this is just confusing.
Is it not useful to exchange the pivot with an up element in the end of partition function ? I don't see it in this implementation.
Hi Gayle - I just want to thank you for taking the time for these videos - you're visual style is extremely beneficial for me (visual learner). I am grateful...
if left == right then there is no point in calling swap, it's the same element. This plus the index change make sure your code won't work properly.
If the array was [3,4,7,5,1,2] wouldn't you get stuck in infinite recursion?
What a great channel! So glad I found this!
This does not show what the code is doing, it's describing what's happening in the algorithm but from abstract overview. As a coder I like seeing both an abstract outlook but also explanations of the inner workings by desk-checking and tracing the execution of the code.
She's just a dumb privileged Tool
This explanation is quit different from the Quick Sort in the CORMEN book!
It’s really helpful, I won’t tell you that at the first time I think this video is not good enough, what a fool.
Slowly unwinding this algorithm.
Question all those while loops in the partition isn’t showing worst case time complexity of O(n^2) ?
yeah I think it's because they are not evaluated at the same time. Same as using an if else block. EDIT: I don't think that code works lol.
Thank you so much Greets from Germany
the best quick sort ever written is the princeton algs4 quicksort!
you produce the video lessons in which software?
This is In response to the older comments below about variations in quicksort. The partition algorithm shown in this video doesn't move the pivot value, but does swap elements so that all elements less than pivot are located before all elements greater than pivot, and elements equal to pivot are not swapped. Other partition algorithms, such as Hoare partition scheme, will end up swapping the pivot element to it's proper sorted location, swap all elements less than pivot before the pivot, swap all elements greater than pivot after the pivot, while elements equal to pivot may or may not be swapped, and can end up before or after the pivot.
I wish she did the quicksort on the right side instead of the left @ 2:00
Once pivot is on the 7, the left pointer is stuck on the 8. Looks like her strategy would have the new partitions be [8][7,9,15]
Does the pivot ever get moved during a call to quick-sort?
Javascript implementation:
let arr = [6,3,1,2,5,8,7,9,15];
quickSort(arr);
console.log(arr);
function quickSort(arr){
let left = 0;
let right = arr.length-1;
return quickSortHelper(arr,left,right);
}
function quickSortHelper(arr,left,right) {
if (left >= right) {
// console.log(arr);
return arr;
}
let pivot = right;
let index = partition(arr, left, right, pivot);
quickSortHelper(arr, left, index - 1);
quickSortHelper(arr, index, right);
}
function partition(arr,left,right,pivot){
while(left arr[pivot]){
right--;
}
if(left >= right){
return left;
}else{
swap(arr,left,right);
left++;
right--;
}
}
return left;
}
function swap(arr,left,right) {
let temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
Finalllyyyy! Thanks man, a solution in JavaScript that actually works
she is comparing left and right, and swapping based on that, but those are indexes. They should be array[left] and array[right]
@George Dedaj But the while loop is already doing that
While loop condition is very confusing. Say X is pivot, K is left element and Q is right element which means when you get to "IF" statement, it should satisfy this condition K > X and Q < X. If K is greater than X then K can never be smaller then Q because Q is smaller than K. It would only execute if K=Q.
why if (left >= right) she just return and nothing to do ? We suppose to swap 15 and 6 no ?
left and right aren't the values 15 and 6, they are the index numbers. the conditional statement is ensuring that the left and right pointers haven't crossed each other
are all those imports necessary?
I don't think the partition part will work if there are duplicates in the array
It helped me a lot understanding better this algorithm
3:23 When there is a sequence of number 213 and you make 1 as pivot, it is never sorted! coz 2 and 3 should both appear on the right side and they can not be swaped !!
Is that really correct? I know after first sort , left side elements must be smaller than pivot and right side elements must be larger than pivot element but in this example, you have 8 still at left side and not well separated. So your code must compare pivot and 8 and swap them too
This confuses me as well.
The best explanation so far, watched so many videos, and this one is the best, I guess becaus e of the visualizing part
There are 2 while nested loops in the partition method, is the time complexity at best case still n log n for the implemented code ?
Thank you!
on line 32, if they're equal then what's the point of swapping them? if they're equal swap does nothing, right?
very good teacher
Thank you. Finally a thorough explanation :)
not ez to undesrtand but if understood you will feel that your brain is working
Wouldn't this break if pivot happens to be the largest or smallest in the list?
According to the code, the pivot can end up getting swapped, unlike in the animation at the beginning where the pivot was skipped. Am I seeing this correctly?
You are correct, the code does not match the animation or her verbal description. The left scan stops at elements >= pivot, and the right scan stops at elements
emmm.. wouldn't the first while loop within the while loop accumulate the left until it reaches < pivot (while doing nothing)? then move on to the next execution point? You sure this is right?
The theory is correct but implementation is wrong
while(arr[left] < pivot)
{
left++;
}
This may lead to array out of bound.
G Edhaya Chandran It breaks when left index matches pivot index
Very good explanation mam
7:08 shouldnt it be greater than or equal to the pivot, and less than OR EQUAL to the pivot
greater than or equal to the pivot
I wonder how many times she's said "Gayle Laakmann McDowell, author of Cracking the Coding Interview" in her lifetime
array is not sorted what happens after the 2 indexes meet at the middle ? It's 12 3 4 65 9. How does the 6 move after the 5 then
this video makes it more confusing to understand, at least for me. "Quick Sort - Computerphile" is much better video for me
I am confused, as much as i learnt every element on the left side of the pivot must be smaller than the pivot and every element on the right of the pivot must be larger than the pivot. 8 > 7 yet you kept it on the left of the pivot.
Will it work if array is having one or repeated number ?
Wow, some insane comments. I like this implementation, although the upfront explanation was challenging to follow. Before someone comments that she has copied and pasted the solution, no kidding, since the original solution was invented by Tony Hoare in 1959, I couldn't find his RUclips channel, unfortunately.
OK... going back to Derek Banas! Lol.
ha ha ha ye
This xD
yes, This Is Definitely Not Good For A Beginner, Derek Banas Rocks In This Sense