Python: QuickSort algorithm explained

Example of how to implement a Quick Sort algorithm in Python 3, with code. Quick Sort is a recursive, divide-and-conquer sorting algorithm.

PYTHON SORTING ALGORITHMS

#Python

[evanzhao]

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!

[manishbolbanda]

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

[balakrishnavaidyanathan]

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

[dilio]

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

[slater]

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

[johnnyphoney]

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]])
bigger = quick_sort([x for x in a_list[1:] if x > a_list[0]])
return sum([lesser, [a_list[0]], bigger], [])
```

[Philippe.C.A-R]

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.

[manishbolbanda]

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

[jmcremer]

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.

[abovebelow]

what is threshold supposed to be in quicksort2?

[jameskerr]

great video, ty for keeping the video short

[sirseatofbelt]

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!

[saurabhmahra]

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

[karima_ax]

How would you write quick sort algorithm in pseudocode?

[NvideaMan]

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

[michalvolf]

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

[thndesmondsaid]

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

[danielqiu]

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

[SO-jpgh]

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?

[Fire_Fly_]

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