@jimmyryan5880
Who here only 15 year professional development experience and I still only use these algorithms in interviews.
@emilybjoerk
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".
@7heLostAndDamned
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!
@rkcst6503
Hmm... all these years I thought 8 was bigger than 7.
@lomoyang3034
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.
@tarunmathur7797
I understood the video at first. But, then I went into the comment section
@saqueebabdullah9142
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.....
@VatsalRajyaguru17143
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?
@DyslexicAnaboko
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.
@johndunne3983
public static void swap(int [] array, int left, int right){
int temp =0;
temp= array[right];
array[right]= array[left];
array[left]= temp;
}
@HillWouston
Thanks for the code. I think it works. However, the aesthetics in this video don't make up for a bad explanation.
@florencechan8863
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.
@ashishdhupkar5065
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]);
}
}
@AndreasBaumgartnerMUC
GitHub copilot sent me from inside VS Code when I was asking about quicksort, commented with the link. What a time to be alive!
@jordanyono5645
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.
@timcook3410
mistake in a hackerrank video! this is the day world ends!
@Rollbaa
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--;
}
}
@k.arslan7959
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
@yhy78979
I think at 1:45 it missed a step which is swaping "8" with the pivot"7"
@cheyno237