Quick Sort

Hey Chenge, this is for you.

Here's my take at Quick Sort. I realised I didn't have the best example half way through the animation. It was too late. All the drawing and animating while on the train to work... Put it as a lesson learned.

Here's the code:

 def quicksort(start, end, array): if start < end: pivot = partition(start, end, array) quicksort(start, pivot - 1, array) quicksort(pivot + 1, end, array) def partition(start, end, array): actualPivotPosition = start pivotValue = array[end] for i in range(start,end): if array[i] < pivotValue: array[i], array[actualPivotPosition] = array[actualPivotPosition], array[i] actualPivotPosition += 1 array[actualPivotPosition], array[end] = array[end], array[actualPivotPosition] return actualPivotPosition array = [5,7,8,1,3,2,4,6] quicksort(0, len(array) - 1, array) print ("Array:", array) # Array: [1, 2, 3, 4, 5, 6, 7, 8] 

Steps:

1. Given an array, set the last position to be a pivot
2. Move the pivot to the actual sorted position in the array
3. Continue to sort the subarray before and after the pivot with Step 1

The worst case is when the pivot is always the smallest or biggest. To prevent that from happening, you can choose a random position, swap the random position with the last head, then continue with the same sorting thingy.

Check out a better tutorial at https://www.geeksforgeeks.org/quick-sort/