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:
- Given an array, set the last position to be a pivot
- Move the pivot to the actual sorted position in the array
- 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/
Top comments (2)
Thanks, Linxea.
I have a better one in Ruby:
omg what sourcery is this, looks like competitive programming