Quick Sort:

date posted: 2019-12-28

Sorting algorithm that uses divide and conquer technique iteratively, breaking down list into two smaller lists and sorting them and repeating it until there are no lists to break down.

When given a list [7,4,3,1,6,5,2] :

1. Pick an element called "pivot". Move all elements smaller than "pivot" to left of the pivot and larger elements on its right. We call this partitioning
2. Now you'll have left list, pivot, right list. Choose another pivot for each left and right list.
3. Repeat until list cannot be partitioned anymore.

So following steps above, 1. pick last element as a pivot and move other elements as explained to get

[2 ,1, 3, 4, 5, 6, 7]

left list = [2,1,3,4] and right list = [6,7]

2. picking new pivots for left and right list to be 4 and 7.

for right list since 6 is less than the pivot we need to move it to right which is already in the right place therefore no need to change anything. Then we are only left with [6] list on left of pivot and [] list on right of pivot hence we are finished on the right.

On left list, all elements are less than pivot therefore it only outputs left list [2,1,3]. We repeat the process until no partioning can be done.

Now, one might be wondering why I picked last element as a pivot. If my list has already been sorted and picked last element as pivot it will give me worst performance since each iteration, it will create list with length n-1 to its left. So one of the most important part of quick sort is choosing the right pivot.

How to pick a pivot:

1. Randomly
   • Pros: Easy to implement
   • Cons: there is probability of choosing largest value in already sorted list
2. Median of first three elements
   • Pros:No chance of choosing largest value in pre-sorted list
   • Cons:Takes extra time to fine median.