quicksort.py

importrandom
importmath

fromcollectionsimportCounter

random.seed(42)

defrandom_array(length, bottom, top):
return [random.randint(bottom, top) foriinrange(length)]

arr= [8, 2, 4, 7, 1, 3, 9, 6, 5]
#arr = [64, 34, 25, 12, 22, 11, 90, 110]

recursion_depth=0
n_operations=0

defquicksort(arr, start, end):
"""
 just by last element
 """
# original = arr[:] # for shallow copy
invariant=Counter(arr)
ifstart>=end:
returnarr
pivot=arr[end]
n=end
i=start-1
swap=0

globaln_operations
globalrecursion_depth
recursion_depth+=1

print(10*"=", f" Quicksort: {recursion_depth} ", 10*"=")
print(f"{start=}, {end=}")
print(arr)
print("pivot is:", pivot) 

forjinrange(start, end):
ifarr[j] <pivot:
i+=1
print(f"{i=}, {j=}, {arr[j]=}, {arr[i]=}")
swap=arr[j]
arr[j] =arr[i]
arr[i] =swap
n_operations+=1
arr[end] =arr[i+1]
arr[i+1] =pivot

# assert on sorting invariant:
# all elements have to match before and after, only position changes
modified=Counter(arr)
assertall([invariant[key] ==modified[key] forkeyininvariant.keys()]), "dang we lost someone"

quicksort(arr, start, i)
quicksort(arr, i+2, end)
returnarr

arr=quicksort(arr, 0, len(arr)-1)

print(f"\nFinal {arr}")
print(f"Total number of operations: {n_operations}")

# testing suite
n_operations=0
n_arrays=100
array_len=1000
max_number=10000
end=array_len-1
foriinrange(n_arrays):
recursion_depth=0
quicksort(random_array(array_len, 0, max_number), 0, end)
print(f"Average number of operations: {n_operations/n_arrays}")
print(f"Big O bound of operations (if not worst case): {array_len*math.log(array_len, 2)}")
print(f"Big O bound of operations (for worst case O(n^2)): {array_len**2}")