## DEV Community is a community of 550,695 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# 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/

## Discussion

chenge

Thanks, Linxea.

I have a better one in Ruby:

``````def qs a
(pivot = a.pop) ?
qs(a.select{|i| i <= pivot}) + [pivot] + qs(a.select{|i| i > pivot}) :
[]
end
``````
ann lin

omg what sourcery is this, looks like competitive programming