This is great video! but, I feel the algo provided in the end is not the same as the way he was explaining.. I went ahead and wrote my code for it same way he explained: ``` class Solution: def sortArray(self, nums: List[int]) -> List[int]: def quicksort(nums, lo, hi): if lo < hi: partition_resting_point = partition(nums, lo, hi) quicksort(nums, lo, partition_resting_point - 1) quicksort(nums, partition_resting_point + 1, hi) def partition(nums, lo, hi): pivotIdx = random.randint(lo, hi) nums[pivotIdx], nums[hi] = nums[hi], nums[pivotIdx] pivot = nums[hi] l_idx = lo r_idx = hi-1 while l_idx
Yeah, in the early days I didn't spend enough time on pseudocode. Trying to fix that now by building out this repo: github.com/msambol/youtube/blob/master/sort/quick_sort.py. Thanks for the feedback!
To ones without enough background knowledge, this video omits details of execution of each step. But to ones with, this is concise and covers sufficient key points of quick sort. Thanks a lot for your video sharing.
After you swap itemFromLeft and the pivot at the end, itemFromLeft is now at the end of the array. So, use that as the *new* pivot. Repeat that until its sorted.
@@kennethquilantang8080 after 7 is put in its correct position, remember that all numbers to the right of 7 are greater than 7. In this case, there is only one number - 8. A partition with just one number is already sorted, so you can ignore it and move on to sort [6,5] to the left of 7. For sorting [6,5] choose 5 as the pivot. itemFromLeft is therefore 6, and itemFromRight has no value because no number in the array smaller than 5. Therefore, we can stop and swap itemFromLeft and the pivot to leave [5,6]. Yes, the video is unclear because it does not explain these cases. The point is that each time you put the pivot into it's correct position, you have "split" the array into two parts - one part has all numbers bigger than the pivot and the other part has all numbers smaller than the pivot. Parts with *just one* element are already sorted. If a part is already sorted, no itemFromLeft can be found. If a part is unsorted, you are guaranteed to find an itemFromLeft, and if the index of itemFromRight < the index of itemFromLeft *OR* itemFromRight does not exist then you can swap itemFromLeft and the pivot to put the pivot into its correct position in the whole array.
I study computer science, and once, I had an exam with a few sort algorithms in it. I didn't really study but about twenty minutes before the exam I watched your 2-4 minute videos on these sort algorithms and I passed the exam. Thank you for helping me.
I've been looking at it for a few minutes now, and I can believe that this pseudocode is accurate, but I'd have to check the details of what the partition function is doing to be sure, but it seems legit. Assuming your language of choice will permit a self-referential function like that.
@@diabl2master The recursion is fine... he's talking about how `partition` is putting the pivot on the left wall instead of the right. In the video the pivot is on the right side.
@@jscholex That would be a failure of technically reflecting, not intuitively reflecting, the walkthrough. I'm not sure OP was referring to that, but who knows.
If anyone is confused at the 1:10, basically he doesn't go through the loop. Instead he jumps to when item from left is higher or item from right is smaller etc. There is a left and right pointer that checks for the condition and then left++ or right-- if its not correct. itemsfromRight goes from 1 cuz its smaller, and then the right-- checks 7, not smaller, right--, checks 8 not smaller, right-- and then it checks the 0 and see that its smaller.
N Betancourt cuz the way he explains it IS confusing I’ve watched this a couple of times, thought I understood went to the exam and screwed up Now that I’ve watched other videos I understand that the way he explains it is confusing
He didn't explain what quick sort does in general, what it can be applied to, and left some holes in the explanation that someone with no experience would struggle to grasp. Which is a shame.
Hey, Thanks for the explanasion, It was a clear and concise video, however the pseudocode is somewhat wrong I believe in 3 things: In Partition, the order of operations is not correct: increment leftwall first, then swap. The final swap in Partition is not correctly swapping the pivot's original position with A[leftwall]. The recursive calls in Quicksort should be updated to exclude the pivot_location from the ranges, properly dividing the array into segments that exclude the sorted pivot. here is the corrected version: Quicksort(A as array, low as int, high as int) if (low < high) pivot_location = Partition(A, low, high) Quicksort(A, low, pivot_location - 1) Quicksort(A, pivot_location + 1, high) Partition(A as array, low as int, high as int) pivot = A[low] leftwall = low for i = low + 1 to high if (A[i] < pivot) then leftwall = leftwall + 1 swap(A[i], A[leftwall]) swap(A[low], A[leftwall]) return(leftwall) Thanks again!
thank u so much, i have an exam tommorow and was stressing bc i couldnt figure out how quick sort work with my teacher's explanation and this just simplified it easily. tysm ;-;
Thank u very much Sir, I got it completely. Actually I'd missed my college online lecture b/c of sleeping... U saved me just night before exam, as urs is the shortest video on YT.
This is great. The simple explanation and the especially simple pseudocode towards the end makes it easy to understand the core concept of the algorithm.
Thank you so much, i have a pc science test today, and i didn'T understand since i can't speak german that well and i am still learning it, this guy explained it all
The pseudocode is hard to read, but the variable name "leftwall" is really good, this gives me a vivid concept of how the leftmost larger item was swapped and the "wall" moved.
@@blurryhorizon I suppose that in the Partition function, the "pivot = A[low]" should actually be "pivot = A[high]"? Very confusing so I wrote it down and found out that the pseudocode doesn't work properly. // Oh just realised that although pivot = A[low] might works as well but the pseudocode is totally wrong for Partition function jeez..
I watched several videos, including my school books, and I had no idea what they were saying with left to right and could not get the answers in the correct order because of that. I was able to understand after watching your video and it allowed me to get past my assignment. Thank you.
I guess, In the quicksort explanation he moves the pivot to the RIGHT END of the array. In the pseudocode, he moves the pivot to the LEFT end of the array. And after the swapping is done, he then brings the pivot to the original position from the LEFTEND. I've seen too many quicksort algorithm videos and this works the best for all my cases.
The video explains the concept of quicksort, a recursive algorithm used for sorting arrays. It emphasizes the importance of choosing a pivot and demonstrates the process of partitioning the array. The video also mentions the pseudocode for quicksort and discusses its time complexity. Understanding Quicksort Algorithm 00:00 Quicksort is a recursive algorithm that uses a pivot to sort an array. 00:13 The pivot is placed in its correct position, with smaller items to the left and larger items to the right. 03:24 Choosing the pivot properly is crucial for the performance of the algorithm.
I really like this explanation. This moves the pivot out of the way and swaps it back with the itemFromLeft pointer. That's so much easier than some other videos I've seen where the pivot is in the middle of the action and we're confused with >= or
Why the pseudocode doesn't intuitively reflect the walk through? (Quote from Wikipedia) "The pivot selection and partitioning steps can be done in several different ways; the choice of specific implementation schemes greatly affects the algorithm's performance." There are two partition schemes: 1. Lomuto partition scheme, which is the pseudocode provided in the video. 2. Hoare partition scheme, which is the walkthrough in the video. Comparison (Quote from Wikipedia) 1. "As the Lomuto partition scheme is more compact and easy to understand, it is frequently used in introductory material, although it is less efficient than Hoare's original scheme." 2. "Hoare's scheme is more efficient than Lomuto's partition scheme because it does three times fewer swaps on average, and it creates efficient partitions even when all values are equal." To understand the Lomuto partition scheme more, I recommend a RU-vid video called "Quicksort: Partitioning an array" by KC Ang.
For those who are not understanding the pseudo code, here is the code that matches the demonstration: private static int partition(int[] arr, int low, int high) { int itemFromLeft = low, itemFromRight = high, pivot = arr[high]; while(itemFromLeft < itemFromRight) { //you need the second condition for the rare case where the pivot is the largest while(arr[itemFromLeft] = pivot && itemFromRight != low) itemFromRight--; if(itemFromLeft < itemFromRight) { int temp = arr[itemFromLeft]; arr[itemFromLeft] = arr[itemFromRight]; arr[itemFromRight] = temp; } } int temp = arr[high]; arr[high] = arr[itemFromLeft]; arr[itemFromLeft] = temp; return itemFromLeft; } *Keep in mind that his pseudo code is 100% correct, it just shows a different partition method that can be used to do the same thing. Also I did this rather quickly so if there are any bugs please let me know*
Take a pivot as the biggest number, the code will recurse an infinite number of times. And you can't simply swap A[i] and A[leftwall] in for loop based on A[i] < pivot. We also need to consider if A[high] < pivot before swapping.
I'm a little confused. In your very detailed, and helpful, explanation of itemFromLeft and itemFromRight it makes total sense. It is similar to the method Gayle uses in her QuickSort video to keep going and swap left and right having both points meet each other. Your implementation, however, seems to go a completely different route by using a for loop with only one pointer and swapping with a wall, similar to Harvard's CS50 class on QuickSort. Also, I found your code kinda confusing by swapping the values and not indexes. I had some problems running that code. My partition looks like this: public static int Parition(int[] array, int left, int right) { // Make starting pivot the last one for now int pivot = array[right]; int leftWall = left; // Go through array until index is reached for (int i = left; i < right; i++) { // If item at array[i] is less than or equal to pivot then switch with leftwall if(array[i]
I was able to write quick sort in a day when I first learned it, and now I completely forgot and feel stupid. This is my major, how tf did I forget this algorithm.
I feel like the pseudo code would reflect the presentation a lot more if we let pivot be A[high] with rightwall=high-1. Then the conditional statement to initiate swap would be if(A[i]>pivot), and of course having rightwall=rightwall+1
