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/

Comments

[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