GitHub Viewer
from random import randint
def _quicksort(arr, lo, hi):
if lo < hi:
p = partition(arr, lo, hi)
_quicksort(arr, lo, p-1)
_quicksort(arr, p+1, hi)
def partition(arr, lo, hi):
#pivot is chosen as first element of list
#shuffle pivot ie first element with any other element randomly
randidx = randint(lo,hi)
arr[randidx], arr[lo] = arr[lo], arr[randidx]
pivot = arr[lo]
left, right = lo, hi
while True:
while arr[left] pivot:
right -= 1
if right == lo:
break
if (left >= right):
break
arr[left], arr[right] = arr[right], arr[left]
arr[lo], arr[right] = arr[right], arr[lo]
return right
def quicksort(arr):
if type(arr) is list:
_quicksort(arr, 0, len(arr)-1)