Python: QuickSort algorithm explained 

Great explanation! I love the way you used "border" to name your pointer, instead of plain "i" and "j". It makes the algorithm much easier to understand! Thank you!

See code on my GitHub repository here, github.com/joeyajames/Python

on the video: 41 is never actually compared to the pivot. Had it been any other value lower than the pivot in place of 41 then it would have ended in the right end side side partition.I suggest that one step was skipped by not comparing " border" to the pivot. Additionally at the end of each run pict should be swapped with border -1. I ran a few examples this way, and it seems to work fine now. Lmk all if if you reached the same conclusions or I missed something.

at 7:25 line 28, you increment border before swapping, just wanna make sure its correct ?

Isn't it too complicated? I wrote it for few minutes and it's just 4 lines and by my opinion a lot easier to understand: ``` def quick_sort(a_list): if len(a_list) < 2: return a_list lesser = quick_sort([x for x in a_list[1:] if x a_list[0]]) return sum([lesser, [a_list[0]], bigger], []) ```

Dear Joe James your python videos are great.keep sending some more

This is the best and most visually explained concept of quicksort.

what is threshold supposed to be in quicksort2?

Is there a flaw with this algorith when I sort the following list? [32,18,9,27,28,21,29,7,12,4] first partition gives [4,9,27,21,7,12,28,32,18,29 and 28 was the pivot..But still got 18 on the right

Is there any reason why you couldn't do a while loop in the partition method for the sort? while i pivot array[i], array[j] = array[j], array[i] i++

How would you write quick sort algorithm in pseudocode?

Thanks for the video Joe. While the code you provide may correctly sort, I'm having a problem with visual demonstration provided. 1. the #41 is never compared to the pivot in the first pass. but every number would need to be checked to insure all #'s less than pivot are to left of pivot. For example change 41 to 1 an the visual example will not work because no comparison is made with that position. 2. at (2:55) if 13 happened to be 21, the swap would not happen, and so you would not be able to swap the pivot with that boarder location, or if you did there would be a 21 in the first location

Seems like we never compared the element in the initial border position with the pivot? For example, in the first pass, the initial border element 41 never got compared to the first pivot? We just got lucky that it happens to belong in the right half so the fact that it never got compared ended up not hurting us?

At 2:54 , if the 8th term was something like 80 and not 13, you wouldn't switch it with the border. Thus you finished going through the list. But what would you do with the pivot and border? As at that specific instance, the border is 54 so you wouldn't switch it with 17 as then you would have 54 on the left side. IE: 17, 5, 6, 3 ,54, 41, 29, 22, 80 where 17 is the pivot, 54 is the border, and you've reached the final value of 80 that you compare with your pivot

it was so easy to understand explaination. thank you very much.

get_pivot (starting near 6:29) is incorrect, or at least does not always return the index of the median of the three values considered. Consider A[low] == 10, A[mid] == 5, A[hi] == 0. get_pivot will return hi in this case but should return mid.

thanks for this playlist all your videos in this playlist ar awesome.

in the partition method, why do we increase the value of border before performing the swap?

I may be wrong, but in the partition function, within the for loop, shouldn't you increment your border position after swapping the border element with the current element? 7:00

Time 0:45 13 is smaller than pivot and is on the right side

random pivots does not ensure nlogn...worst case time complexity is still O(n^2) e.g. when all the elements are identical. the only way of ensuring nlogn is by choosing a pivot close to the median

great video, ty for keeping the video short

Good stuff mate

Hey this is great! I have to write basically this for a class assignment and then do a bunch of stuff with it. So this is really handy for getting me started!

Hello, Joe. thank you for great videos. Can you tell me please why in your python file you measure execution time with "t1 = time.clock()", but not with cProfile library? Thank you

Mr. James one minor doubt, how exactly do we decide on the border element??? is it the element immediately after the pivot ??

@06:05 Change to quick_sort2(A, low, p) to get the correct final answer.

This might be a "duh" question like my lat, but I tried to implement the code you have in this video, but don;t understand what to use in place of "hi" and "low." Mid is defined in getPivot but many functions use low and hi as parameters. I try using their places within the list [0] and [-1] and tha does not work either. I feel like I am missing something, as defining them yields syntax errors.

Thanks for the video, but there were a lot of comparisons that were not right, be it on the first iteration, left iteration and median for right iteration. We’re they deliberate to see if we comment???? Lol. Keep up the good work

hello Joe James, what is threshold in quick_sort2 function?

Good Video James

What if low>hi? Pls explain

threshold in quick_sort2 is not defined.

Hi. Your (wrong) explanation doesn't match with your (right) code. 1. border = left (not left+1) 2. every time an item less then pivot found - only then! border+=1 - and only now! the found item is swapped with the border one only in this case all the less-than-pivot items jumped to the left of the border with last of them exactly on the border Thank you for your very short and clear and logical code of the quick sort

I think the algorithm you explained is wrong. Consider array 5 6 7 8 9 10. 5 is the pivot and 6 is the boarder, since 7 8 9 10 is all greater than 5, we don't swap and thing but pivot and board. This gives 6 5 7 8 9 10 which 6 appears to the left of 5.

Y we choose 22 has pivot

Thank you.

Hello dear sir , I need help in parallel quicksort with python, please help me

You're the best!

why use a algorithm when list is already sorted?

Awesome

i like the music

I love this. it is very helpful, putting this algorithms into practice. Problem is, when i try accessing the link above, it results in a 404

Saviour

I can't believe I just wasted 30min of my life trying to figure out this code just to realice that the get_piv function is broken! This might not be a big deal for many, but for beginner programmers it can be very frustrating. This video has a great description on how the algorithm works, but this guy should try testing his code a few more times before making a video with a broken code.

not get answer properly

too complicated you have made it