# Quick Sort

### linxea γ»1 min read

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/

Classic DEV Post from Nov 28 '18

Thanks, Linxea.

I have a better one in Ruby:

omg what sourcery is this, looks like competitive programming