Algorithms: Quicksort

Learn the basics of quicksort. This video is a part of HackerRank's Cracking The Coding Interview Tutorial with Gayle Laakmann McDowell.

[cheyno]

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 :)

[jimmyryan]

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

[heLostAndDamned]

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!

[lomoyang]

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.

[tarunmathur]

I understood the video at first. But, then I went into the comment section

[VatsalRajyaguru]

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?

[rkcst]

Hmm... all these years I thought 8 was bigger than 7.

[saqueebabdullah]

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

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

[johndunne]

public static void swap(int [] array, int left, int right){
int temp =0;
temp= array[right];
array[right]= array[left];
array[left]= temp;
}

[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!

[allaboutcs]

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.

[yhy]

I think at 1:45 it missed a step which is swaping "8" with the pivot"7"

[HillWouston]

Thanks for the code. I think it works. However, the aesthetics in this video don't make up for a bad explanation.

[florencechan]

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.

[ashishdhupkar]

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]);

}
}

[walterpinto]

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.

[ayseryucel]

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.

[AlgosExplained]

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]