Quicksort

The idea,

  1. The pivot is always the last index of the array
    [5,1,7,3,4] -> 4 is the pivot
  2. Move all the value small than 4 to the front of the array
    [5,1,7,3,4], 5 > 4, do nothing
    [1,5,7,3,4], 1 < 4, move 1 to the front of the array
    [1,5,7,3,4], 7 > 4, do nothing
    [1,3,7,5,4], 3 < 4, move 3 to the front of the array
  3. Move pivot to the correct position
    [1,3,4,5,7]
  4. Return the new position and repeat everything from 1 - 4 for all the values before and after of the new position

The implementation,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def quicksortHelper(arr, start, end):
if start < end:
partitionIndex = partition(arr, start, end)
quicksortHelper(arr, start, partitionIndex - 1)
quicksortHelper(arr, partitionIndex + 1, end)
return arr

def partition(arr, start, end):
pivotValue = arr[end]
pointerIndex = start
for i in range(start, end):
if arr[i] < pivotValue:
arr[i], arr[pointerIndex] = arr[pointerIndex], arr[i]
pointerIndex += 1

arr[end], arr[pointerIndex] = arr[pointerIndex], arr[end]

return pointerIndex

def quicksort(arr):
return quicksortHelper(arr, 0, len(arr) - 1)

arr = [5, 1, 7, 3, 4]
print(quicksort(arr))
# [1, 3, 4, 5, 7]

Ya,

this is what I do in my free time now.