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".
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.
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.
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.
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.
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.
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]); } }
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 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.
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.
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
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
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
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?
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
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
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...
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.
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?
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.
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
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?
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.
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?
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 :)
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)
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.
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.
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.
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
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.
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 !!
In line 16, we have int pivot= array[(left+right)/2]; and then in lines 28 and 32, we compare array elements at left and right indices with pivot. If I use int pivot= (left+right)/2; and then compare array elements at left and right indices with array[pivot], the sorting gets messed. I want to understand why. Any help would be appreciated.
@@jasonc2033 I get that. My question is, if I take middle index as pivot, and then compare array[pivot] with elements in the left and the right, why does the answer vary. The sort messes up in this case.
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
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]
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]); } }
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.
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.
yes, when arr[left] is bigger than the pivot, and choose last element as pivot, ends up both arr[left] and arr[right] are bigger than the pivot, so this will not work, cant swap, other wise will loop forever, like my program did.
*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!!!*
You didn't bother explaining what happens to the pivot values after the partitions are sorted.... and that is literally the most important part :/ They are supposed to swap into the spot where the left and right pointers overlap. Doing so guaranties that is their final sorted location.
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 TH-cam channel, unfortunately.
There are cases where you have to perform n^2 operations, as the example showed in the video, so θ(n log n) does not bound the algorithm from above. The Theta notation does not mean the average runtime complexity. We use θ( f(n) ) when we want to indicate that the asymptotic complexity is bounded from above and below by c*f(n) for some constant c. Since that is not always the case, we don't have θ(n log n).
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!
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
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.
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
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.
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.
GitHub copilot sent me from inside VS Code when I was asking about quicksort, commented with the link. What a time to be alive!
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
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 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
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.
Thanks for the code. I think it works. However, the aesthetics in this video don't make up for a bad explanation.
I think at 1:45 it missed a step which is swaping "8" with the pivot"7"
Please run your code to make sure it works before publishing an instructional video.
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.
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 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.
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
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
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?
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
mistake in a hackerrank video! this is the day world ends!
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
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...
you forgot one of the basic step in there which lead to this all confusion among the viewers
I don't think the partition part will work if there are duplicates in the array
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.
If the array was [3,4,7,5,1,2] wouldn't you get stuck in infinite recursion?
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
Comment section of this video is more useful than the video itself.
true
its called community! it helps!
code is not working
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.
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--;
}
}
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
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
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 ?
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. 你說中文嗎
she has a swap method but doesn't have a swap function from what I can tell. I found this highly confusin.
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.
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?
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 .
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
This is honestly so much more useful than college was...
Why does 8 remain on the left side of the 7?
She's too busy copy and pasting her "BOOK" in different languages 🤣
Why so many dislikes? That was the best you can learn of quicksort in under 10 mins.
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 :)
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 implemented this in C++ with vectors and it worked.
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 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.
why are we swapping left and right number if left is equal to right?
blondey tool is on indefinite vacation to answer anything
if you first find the exact median/index item, then you can always median bucket sort to get O(n log n) performance
on line 32, if they're equal then what's the point of swapping them? if they're equal swap does nothing, right?
You didn't even sort the array fully. disappointed.
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.
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.
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
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
not working for {10,80,30,90,40,50,70}
8 is greater than 7 but you put it on the left of 7 , really? will you pass Google' coding interview with this ?
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.
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
Algo fails with ArrayIndexOutOfBoundException in few cases. try {4,1,3,6,5,8,7}
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 !!
can anyone explain why index and index + 1 instead of the above index-1 and index would give me stack overflow?
Wouldn't this break if pivot happens to be the largest or smallest in the list?
In line 16, we have
int pivot= array[(left+right)/2];
and then in lines 28 and 32, we compare array elements at left and right indices with pivot.
If I use int pivot= (left+right)/2;
and then compare array elements at left and right indices with array[pivot], the sorting gets messed. I want to understand why. Any help would be appreciated.
@@jasonc2033 I get that. My question is, if I take middle index as pivot, and then compare array[pivot] with elements in the left and the right, why does the answer vary. The sort messes up in this case.
if the result is bigger than pivot one one side, why 8 is before 7?????
blondey's too busy copy and pasting
Will it work if array is having one or repeated number ?
Anyone know why she has while loops moving indexes left and right if less than pivot without swapping?
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
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.
Thanks for the show off of your knowledge but I understood nothing. Seems I am not alone with that problem.
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.
Hi Gayle, liking your book CTCI!
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]
how did you move 8 before 7 ? It should have elements lesser than 7.
Lets say i have array 8,7,9,15 and pivot is 9 then how it will work ?
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]);
}
}
so bubblesort.. ?
Does the pivot ever get moved during a call to quick-sort?
i did your code verbatim and it never reaches the base case
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.
@ 1:52 -- 8 > 7 but still 8 is on the lest side of 7, why?
idiotBlondie's tool is too busy to care 🤣
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.
Learned many new concepts from this video. Today i got to know that 8 is smaller than 7 (:
nice vid
+ another way to implement quicksort
There is no hard & fast rule to select pivot, This code is not working when some choose last elements as pivot.
yes, when arr[left] is bigger than the pivot, and choose last element as pivot, ends up both arr[left] and arr[right] are bigger than the pivot, so this will not work, cant swap, other wise will loop forever, like my program did.
*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!!!*
You didn't bother explaining what happens to the pivot values after the partitions are sorted.... and that is literally the most important part :/
They are supposed to swap into the spot where the left and right pointers overlap. Doing so guaranties that is their final sorted location.
Hello, just to say regardless of the video. There is a Korean coding interview book right next to Apple computer.
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 TH-cam channel, unfortunately.
while (array[right] > pivot && left < right) {
...}
Shouldn't we be using Theta to showcase the average runtime rather than Big O?
So, it should be:
- θ(n log n)
- O(n^2)
no?
There are cases where you have to perform n^2 operations, as the example showed in the video, so θ(n log n) does not bound the algorithm from above.
The Theta notation does not mean the average runtime complexity. We use θ( f(n) ) when we want to indicate that the asymptotic complexity is bounded from above and below by c*f(n) for some constant c. Since that is not always the case, we don't have θ(n log n).
@@bela-chan Thanks for clarification!
@@riccardopolacci6501 No problem, hope it helped!