basic-programs/python/recursion/quicksort.py at master · ProjectRipo/basic-programs · GitHub

46 lines (30 loc) · 1.01 KB

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:

left += 1

if left == hi:

break

while arr[right] > 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)

Expand file tree