Quick Sort Algorithm

quick-sort.py

import random

def Partition(A, pivot_idx, l, r):
    #Choose a random value to be the pivot
    pivot = A[pivot_idx]

    #Move pivit to first position in subarray
    A[l], A[pivot_idx] = A[pivot_idx], A[l]
    
    #stores the idx of the last value less than or equal to the pivot
    #at the end of the algorithm the pivot will be swapped with the element
    #at this position thus ensuring everything to the left of the pivot is
    #less than or equal to th pivot. 
    #
    #The value is initalized at the current idx of the pivot
    
    last_val_lte_pivot = l
    
    #j explores each element in the subarray starting with the one to the immediate
    #right of the pivot
    #
    #The for loop then compares the jth element to the pivot and makes any
    #necessary swaps
    for j in range(l + 1, r):
        if A[j] <= pivot:
            A[last_val_lte_pivot + 1], A[j] = A[j], A[last_val_lte_pivot + 1]
            last_val_lte_pivot += 1
    A[l], A[last_val_lte_pivot] = A[last_val_lte_pivot], A[l]
    return last_val_lte_pivot
            
            

def QuickSort(A, l = 0, r = None):
    if r == None:
        r = len(A)

    n = len(A[l:r])
    if n == 1 or n == 0:
        return A[l:r]
    else:
        #Choose Random
        pivot_idx = random.randint(l, r-1)
        
        #Choose first
        #pivot_idx = l        
        
        #Choose Last 
        #pivot_idx = (r-1)
        
        #Choose Median
#        first, middle, last = l, (l + ((r-1)-l)//2), (r - 1)
#        if (A[first] <= A[middle] <= A[last]) or (A[last] <= A[middle] <= A[first]):
#            pivot_idx = middle
#        elif (A[middle] <= A[first] <= A[last]) or (A[last] <= A[first] <= A[middle]):
#            pivot_idx = first
#        else:
#            pivot_idx = last
                    
        split = Partition(A, pivot_idx, l, r)
        QuickSort(A, l, split)
        QuickSort(A, split + 1, r)