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.
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.
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".
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.
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.
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.
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 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.
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]); } }
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.
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.
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...
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.
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.
I thought this video explains this very well, especially after trying to understand the other videos on quicksort, the comments dont seem to know what they are talking about
On the first iteration 8 > 7 so 8 should be moved to the right of 7. I think it is important to explain very carefully otherwise people will not get the idea or get confused :)
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--; } }
This video is flawed in multiple details: 1) it is never clearly mentioned when a partition is "sorted". 2) it is never clearly mentioned how the new partition boundaries are picked. 3) you do not clearly distinguish between pivot and separation index. What I like though is that you actually code it and explain what you do.
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
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 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
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.
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.
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
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.
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 UA-cam channel, unfortunately.
The code is working but in the video the swap method is not represented, because the swap method is too common for other sorting techniques. For the people who don't know what to put in the swap method, or for the people who don't know Java programming language, here's the additional code to insert in your class: public static void swap(int[] array, int left, int right) { int temp = array[left]; array[left] = array[right]; array[right] = temp; } public static void main(String[] args) { //Unsorted array int[] array = {3, 1, 8, 5, 6, 2, 4, 9, 7}; //Sorting the array through static method quicksort Solution.quicksort(array); //Printing the numbers in sorted order one by one for(int i = 0; i < array.length; i++) { System.out.println(array[i]); } }
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?
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
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
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?
she is saying everything bigger then pivot is on one side and everything smaller then pivot is on the other side. that's really confusing.!! in 1:51, the pivot is 7 and yet 8 is on the left side of the pivot instead of the right side.. same thing at 0:38 where the pivot 7 after the value of 9.
@@kevincui1631 She said everything bigger than 7 should be on 'one side'.... erm let me rephrase then.. why there are bigger numbers then 7 on both sides?
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]
Very useful tutorial. The relative high dislikes just reflects the frustration of some people. Quicksort is a algorithm with different variants. Everybody expects the algorithm that he is studying in the university.
I've fixed the given code. Seems it works now: class QuickSort { public static void sort(int[] array) { quickSort(array, 0, array.length - 1); } private static void quickSort(int[] array, int left, int right) { if (left >= right) { return; } int pivot = array[left + (right - left) / 2]; int index = partition(array, left, right, pivot); quickSort(array, left, index - 1); quickSort(array, index, right); } private static int partition(int[] array, int left, int right, int pivot) { while (left pivot && right >= left) { right--; } if (left
Oh man. This code looks fishy. The loop conditions inside partition() seem dubious to me. I doubt that this code was tested and reviewed thoroughly. You should throw some randomized testing and some eyeballs at your code to shake out all the bugs before you publish a video about it.
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.
Explanation in the beginning and the code at the end doesn't match. The while-loop in partition function (8:13), "right" stops decrementing when the value arrives at the pivot since pivot isn't greater than pivot itself. But in the explanation (1:44), your "right" index already passed pivot. You should change those while loops to if-statements and make it stop at array length or 0, and have swap in a better conditioned if-statement. Honestly, just rewrite partition function. Don't use nested while loops when you don't have to. It just creates confusion thinking squared time, when yours is in linear time. Concept-wise, good, but make sure you post an optimal programming solutions.
I pretty much understand this video, except the if (left >= right) return ... and she keeps saying "if left is greater than right, just return; there's nothing to do" ... how is there nothing to do when those are out of order? I'm sure I'm missing something but it's a bizarre comment
Hilariously this would fail the Quicksort part 1 and part 2 exercises on HackerRank because it doesn't maintain the order of the elements in each partition.
i don't understand how this random floating pivot could possibly sort the list faster with how many iterations it looks like it takes to sort things in the correct order.
Been developing desktop apps for yeeeeears and never had to write algos, gotta know how to use them but not implement them, however there comes a time when you wanna go deeper and be more efficient I'm starting to like Algos......
Most of the tutorials are great but this is flawed and this implementation will not work for [5, 4, 1, 3, 7]. The pivot will be 1 and it is the smallest element in the array so the while loop that looks for something smaller than the pivot will go out of bounds.
*You in your book, just like recruiters and interviewers at FaceBook say to go to **LeetCode.com** and your book to practice the interview questions. Also both admit that these are fundamental questions that everyone has seen before.* *You then carry on, and in your book say that if we have seen an interview question before, we should let the interviewer know, so, what is up with that? They ask questions that everyone has seen, and then we are supposed to let them know?* *They ask us to practice these questions, and then we are supposed to tell them that we have seen them before?* *Also you say tech companies are OK with false negatives, but what about false positives? people who read your book and pass the interview, but are not good!!!*
how does it work when she is partitioning partition(low, index - 1) partition(index, high) shouldnt it be partition(low, index - 1) partition(index + 1, high)
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.
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 !!
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?
this code has bug, we cant choose last one as pivot, other wise will loop forever, since arr[left] and arr[right] will both be bigger than pivot. example of my cpp code(will crush) update: I've found the solution for my problem change if(low= high) return low; std::swap(arr[low++], arr[high--]); and this is Hoare’s parition scheme, another implementation is Lomuto’s Partition Scheme, you can google these two for more information int partition2(std::vector &arr, int low, int hight) { int key = arr[hight]; while(low key) hight--; if(low = hight) return; int index = partition2(arr, low, hight); quickSort2(arr, low, index - 1); quickSort2(arr, index, hight); } void quickSort2(std::vector &arr) { quickSort2(arr, 0, arr.size() - 1); } int main() { int arr[] = {12, 11, 13, 5, 6, 33, 4234, 35, 66, 77, 234, 534, 53, 4545, 456, 5, 6, 87, 78}; std::vector test(arr, arr + sizeof(arr) / sizeof(int)); quickSort2(test); }
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
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.
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!
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
I understood the video at first. But, then I went into the comment section
lol same
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
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.
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 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.
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];
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
Thanks for the code. I think it works. However, the aesthetics in this video don't make up for a bad explanation.
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!
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.
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.
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...
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!
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
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.
I thought this video explains this very well, especially after trying to understand the other videos on quicksort, the comments dont seem to know what they are talking about
On the first iteration 8 > 7 so 8 should be moved to the right of 7. I think it is important to explain very carefully otherwise people will not get the idea or get confused :)
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--;
}
}
Please run your code to make sure it works before publishing an instructional video.
if you first find the exact median/index item, then you can always median bucket sort to get O(n log n) performance
This video is flawed in multiple details:
1) it is never clearly mentioned when a partition is "sorted".
2) it is never clearly mentioned how the new partition boundaries are picked.
3) you do not clearly distinguish between pivot and separation index.
What I like though is that you actually code it and explain what you do.
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
I think at 1:45 it missed a step which is swaping "8" with the pivot"7"
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.
you forgot one of the basic step in there which lead to this all confusion among the viewers
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
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.
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 implemented this in C++ with vectors and it worked.
This is honestly so much more useful than college was...
Totally confused by this explanation. I haven't written a quicksort in about two months, so I forgot how. But this is just confusing.
Hi Gayle, liking your book CTCI!
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
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.
Learned many new concepts from this video. Today i got to know that 8 is smaller than 7 (:
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
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
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 .
The code used to explain quicksort is not completely right.
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.
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
Algo fails with ArrayIndexOutOfBoundException in few cases. try {4,1,3,6,5,8,7}
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 UA-cam channel, unfortunately.
The code is working but in the video the swap method is not represented, because the swap method is too common for other sorting techniques. For the people who don't know what to put in the swap method, or for the people who don't know Java programming language, here's the additional code to insert in your class:
public static void swap(int[] array, int left, int right) {
int temp = array[left];
array[left] = array[right];
array[right] = temp;
}
public static void main(String[] args) {
//Unsorted array
int[] array = {3, 1, 8, 5, 6, 2, 4, 9, 7};
//Sorting the array through static method quicksort
Solution.quicksort(array);
//Printing the numbers in sorted order one by one
for(int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
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. 你說中文嗎
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
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.
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?
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
she is saying everything bigger then pivot is on one side and everything smaller then pivot is on the other side. that's really confusing.!! in 1:51, the pivot is 7 and yet 8 is on the left side of the pivot instead of the right side.. same thing at 0:38 where the pivot 7 after the value of 9.
You misunderstood this method. She said everything bigger than 7 should be on 'one side', not on the right side of 7. Feel the difference.
@@kevincui1631 She said everything bigger than 7 should be on 'one side'.... erm let me rephrase then.. why there are bigger numbers then 7 on both sides?
Nusakan what do you mean by both sides? It looks like all the number greater than 7 are on one side to me.
Paul Tan No. 7 and 8 shouldn’t be swapped !
@@kevincui1631 1:51
code is not working
If the array was [3,4,7,5,1,2] wouldn't you get stuck in infinite recursion?
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]
nice vid
+ another way to implement quicksort
This explanation is quit different from the Quick Sort in the CORMEN book!
Very useful tutorial. The relative high dislikes just reflects the frustration of some people. Quicksort is a algorithm with different variants. Everybody expects the algorithm that he is studying in the university.
I've fixed the given code. Seems it works now:
class QuickSort {
public static void sort(int[] array) {
quickSort(array, 0, array.length - 1);
}
private static void quickSort(int[] array, int left, int right) {
if (left >= right) {
return;
}
int pivot = array[left + (right - left) / 2];
int index = partition(array, left, right, pivot);
quickSort(array, left, index - 1);
quickSort(array, index, right);
}
private static int partition(int[] array, int left, int right, int pivot) {
while (left pivot && right >= left) {
right--;
}
if (left
Oh man. This code looks fishy. The loop conditions inside partition() seem dubious to me. I doubt that this code was tested and reviewed thoroughly. You should throw some randomized testing and some eyeballs at your code to shake out all the bugs before you publish a video about it.
Yeap, when I walk through the logic, it did not make sense to me and I just tried it with c#, it does not work.
Code and logic works fine. I recommend to learn merge sort first
I don't think the partition part will work if there are duplicates in the array
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.
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
Hello, just to say regardless of the video. There is a Korean coding interview book right next to Apple computer.
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.
she has a swap method but doesn't have a swap function from what I can tell. I found this highly confusin.
Explanation in the beginning and the code at the end doesn't match. The while-loop in partition function (8:13), "right" stops decrementing when the value arrives at the pivot since pivot isn't greater than pivot itself. But in the explanation (1:44), your "right" index already passed pivot. You should change those while loops to if-statements and make it stop at array length or 0, and have swap in a better conditioned if-statement. Honestly, just rewrite partition function. Don't use nested while loops when you don't have to. It just creates confusion thinking squared time, when yours is in linear time. Concept-wise, good, but make sure you post an optimal programming solutions.
I pretty much understand this video, except the if (left >= right) return ... and she keeps saying "if left is greater than right, just return; there's nothing to do" ... how is there nothing to do when those are out of order? I'm sure I'm missing something but it's a bizarre comment
while (array[right] > pivot && left < right) {
...}
Wow the other way that partition is typically written is so confusing. This one is so intuitive.
ofcourse it is, she copied someone else's work
Thanks for the show off of your knowledge but I understood nothing. Seems I am not alone with that problem.
For those of you who can't understand the I recommend to learn Merge Sort first. This explanation is very good
Hilariously this would fail the Quicksort part 1 and part 2 exercises on HackerRank because it doesn't maintain the order of the elements in each partition.
Why does 8 remain on the left side of the 7?
She's too busy copy and pasting her "BOOK" in different languages 🤣
i don't understand how this random floating pivot could possibly sort the list faster with how many iterations it looks like it takes to sort things in the correct order.
You didn't even sort the array fully. disappointed.
the best quick sort ever written is the princeton algs4 quicksort!
Been developing desktop apps for yeeeeears and never had to write algos, gotta know how to use them but not implement them, however there comes a time when you wanna go deeper and be more efficient I'm starting to like Algos......
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.
Most of the tutorials are great but this is flawed and this implementation will not work for [5, 4, 1, 3, 7]. The pivot will be 1 and it is the smallest element in the array so the while loop that looks for something smaller than the pivot will go out of bounds.
not ez to undesrtand but if understood you will feel that your brain is working
*You in your book, just like recruiters and interviewers at FaceBook say to go to **LeetCode.com** and your book to practice the interview questions. Also both admit that these are fundamental questions that everyone has seen before.*
*You then carry on, and in your book say that if we have seen an interview question before, we should let the interviewer know, so, what is up with that? They ask questions that everyone has seen, and then we are supposed to let them know?*
*They ask us to practice these questions, and then we are supposed to tell them that we have seen them before?*
*Also you say tech companies are OK with false negatives, but what about false positives? people who read your book and pass the interview, but are not good!!!*
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 ?
Nice and short videos. Really good for reviewing.
Except everything the left of the pivot is not actually less than the pivot in your example.
how does it work when she is partitioning
partition(low, index - 1)
partition(index, high)
shouldnt it be
partition(low, index - 1)
partition(index + 1, high)
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.
Now it makes sense finally!!!
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 !!
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 best explanation so far, watched so many videos, and this one is the best, I guess becaus e of the visualizing part
this video makes it more confusing to understand, at least for me. "Quick Sort - Computerphile" is much better video for me
this code has bug, we cant choose last one as pivot, other wise will loop forever, since arr[left] and arr[right] will both be bigger than pivot.
example of my cpp code(will crush)
update:
I've found the solution for my problem
change
if(low= high)
return low;
std::swap(arr[low++], arr[high--]);
and this is Hoare’s parition scheme, another implementation is
Lomuto’s Partition Scheme, you can google these two for more information
int partition2(std::vector &arr, int low, int hight)
{
int key = arr[hight];
while(low key)
hight--;
if(low = hight) return;
int index = partition2(arr, low, hight);
quickSort2(arr, low, index - 1);
quickSort2(arr, index, hight);
}
void quickSort2(std::vector &arr)
{
quickSort2(arr, 0, arr.size() - 1);
}
int main()
{
int arr[] = {12, 11, 13, 5, 6, 33, 4234, 35, 66, 77, 234, 534, 53, 4545, 456, 5, 6, 87, 78};
std::vector test(arr, arr + sizeof(arr) / sizeof(int));
quickSort2(test);
}
Great explanation. And the code works, too.