'''
In this module, we implement quicksort
Time complexity (average case) : O(n * log n)
Time complexity (worse case) : O(n ^ 2)

'''


def quicksort(arr, left, right):
    '''
    Sort array using  quicksort
    
    '''
    pass
    

def partition(arr, left, right):
    pass

@@ -223,57 +223,1356 @@
     
-pass%0A    %0A%0Adef partition(arr, left, right):%0A    pass
+if left %3C right:%0A%09%09pivot = partition(arr, left,right)%0A%09%09quick_sort(arr, left,pivot - 1)%0A%09%09quick_sort(arr, pivot + 1, right)%0A    %0A%0Adef partition(arr, left, right):%0A    '''%0A    Partition array around pivot value such that all values%0A    less than the pivot value are to the left of the pivot value%0A    and all values greater than the pivot value are to the right%0A    %0A    Three ways to choose pivot:%0A    1) First value in the array%0A    2) A random value in the array%0A    3) Median of 3 where the median of the first value, last %0A       value and the middle value is chose as the pivot%0A    %0A    '''%0A    pivot_value = arr%5Bleft%5D%0A%09index = left + 1%0A%09for j in range(left + 1, right+1):%0A%09%09if arr%5Bj%5D %3C pivot_value:%0A%09%09%09arr%5Bindex%5D, arr%5Bj%5D = arr%5Bj%5D, arr%5Bindex%5D%0A%09%09%09index += 1%0A%09arr%5Bindex - 1%5D, arr%5Bleft%5D = arr%5Bleft%5D, arr%5Bindex-1%5D%0A%09return index-1%0A%09%0A# Alternate implementation of the partition method%0A# def partition(alist, left, right):%0A# %09pivot_value = alist%5Bleft%5D%0A# %09left_mark = left + 1%0A# %09right_mark = right%0A# %09while left_mark %3C right_mark:%0A# %09%09while alist%5Bleft_mark%5D %3C pivot_value:%0A# %09%09%09left_mark += 1%0A# %09%09while alist%5Bright_mark%5D %3E pivot_value:%0A# %09%09%09right_mark -=1%0A# %09%09if left_mark %3C right_mark:%0A# %09%09%09alist%5Bleft_mark%5D, alist%5Bright_mark%5D = alist%5Bright_mark%5D, alist%5Bleft_mark%5D%0A# %09alist%5Bleft%5D, alist%5Bright_mark%5D = alist%5Bright_mark%5D, alist%5Bleft%5D%0A# %09return right_mark
 %0A

Update quicksort.py