lumoto.py

# translating pseudocode from wikipedia's quicksort to python.                                                                     
# https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme                                                      

# algorithm quicksort(A, lo, hi) is                                                                                    
def quicksort(A, lo, hi):
    # if lo < hi then                                                                                                  
    if lo < hi:
        # p := partition(A, lo, hi)                                                                                    
        p = partition(A, lo, hi)
        # quicksort(A, lo, p - 1 )                                                                                     
        quicksort(A, lo, p - 1)
        # quicksort(A, p + 1, hi)                                                                                      
        quicksort(A, p + 1, hi)

# algorithm partition(A, lo, hi) is                                                                                    
def partition(A, lo, hi):
    # pivot := A[hi]                                                                                                   
    pivot = A[hi]
    # i := lo - 1                                                                                                      
    i = lo - 1
    # for j := lo to hi - 1 do                                                                                         
    for j in range(lo, hi):
        # if A[j] < pivot then                                                                                         
        if A[j] < pivot:
            # i := i + 1                                                                                               
            i = i + 1
            # swap A[i] with A[j]                                                                                      
            A[i], A[j] = A[j], A[i]
    # if A[hi] < A[i + 1] then                                                                                         
    if A[hi] < A[i + 1]:
        # swap A[i + 1] with A[hi]                                                                                     
        A[i+1], A[hi] = A[hi], A[i+1]
        # return i + 1                                                                                                 
    return i + 1

def test_sort():
    import random
    # build a list with repeated values from -10, to +9                                                                
    xs = 2 * list(range(-10,10))
    # test quicksort 1000 times.                                                                                       
    for _ in range(1000):
        # randomize xs                                                                                                 
        random.shuffle(xs)
        # sort them                                                                                                    
        quicksort(xs, 0, len(xs)-1)
        # check if sorted                                                                                              
        if sorted(xs) != xs:
            print("sort fails for: ", xs)

test_sort()