quicksortfail.py

import random

generate = lambda length=10, min=0, max=100 : [random.randint(min, max) for _ in range(length)]

# Quicksort, recur parameter is just for debug purposes
def quicksort(array, recur=0):
    # Prints out the array's current statet in a readable format
    def repr():
        temp = list(map(str, array))
        if lm == rm:
            temp[lm] = 'LR' + temp[lm]
        else:
            temp[lm] = 'L' + temp[lm]
            temp[rm] = 'R' + temp[rm]
        temp[pivot] = 'P' + temp[pivot]
        print('[{}]'.format(', '.join(temp)))

    # Swaps two indexes of an array    
    def swap(x, y):    
        array[x], array[y] = array[y], array[x]

    if len(array) <= 1:
        return array

    # Not particularly sure what to put pivot at?
    pivot = (len(array) // 2)
    # pivot = len(array) - 1
    lm = 0
    rm = len(array) - 1

    repr()
    while lm != rm:
        if array[lm] < array[pivot]:
            lm += 1
        elif array[rm] >= array[pivot]:
            rm -= 1
        else:
            swap(lm, rm)
        repr()

    print('>', end='')
    swap(lm, pivot)
    # pivot, lm, rm = lm, pivot, pivot

    repr()
    print('\nLEFT {}'.format(recur + 1))
    left = quicksort(array[:pivot], recur=recur+1)

    print('\nRIGHT {}'.format(recur + 1))
    right = quicksort(array[pivot+1:], recur=recur+1)

    return left + [array[pivot]] + right

# Sorts & returns an array, misc function
def sorteth(arr):
    arr.sort()
    return arr

# Returns true if the array is sorted
def verify(original):
    return sorteth(list(original)) == original

# Compares two arrays, must be same length
# Marks differences between the two arrays with *
def compare(real, unreal):
    temp = [str(num) + '*' if num != real[index] else str(num) for index, num in enumerate(unreal)]
    return '[{}]'.format(', '.join(temp))

random.seed(2)

# Testing purposes of comparing my array vs a properly sorted array

for _ in range(1):
    original = generate()
    real = sorteth(list(original))
    myquicksort = quicksort(original)
    if real != myquicksort:
        print('\nOrig: {}\nReal: {}\nMine: {}'.format(original, real, compare(real, myquicksort)))