Skip to content

Instantly share code, notes, and snippets.

@Xevion
Created July 2, 2019 21:39
Show Gist options
  • Save Xevion/08fbf4fb7180928cde7598f3838908c9 to your computer and use it in GitHub Desktop.
Save Xevion/08fbf4fb7180928cde7598f3838908c9 to your computer and use it in GitHub Desktop.
import random
generate = lambda length=10, min=0, max=100 : [random.randint(min, max) for _ in range(length)]
def partition(array, start, end):
def swap(x, y):
array[x], array[y] = array[y], array[x]
pivotIndex = start
pivotValue = array[end]
for i in range(start, end + 1):
if array[i] < pivotValue:
swap(i, pivotIndex)
pivotIndex += 1
swap(pivotIndex, end)
return pivotIndex
def quicksort(array, start, end):
if start >= end:
return
index = partition(array, start, end)
quicksort(array, start, index - 1)
quicksort(array, index + 1, end)
def verify(array):
prev = array[0]
for val in array:
if val < prev:
return False
prev = val
return True
for _ in range(1000):
array = generate()
# print(array)
quicksort(array, 0, len(array)-1)
# print(array)
if not verify(array):
print('Failed')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment