Created
February 3, 2020 08:17
-
-
Save uptown/56f0cee6a172295fbbc9d0fe86c2d6a7 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# generate random integer values | |
from random import randint | |
def swap(arr, x, y): | |
temp = arr[x] | |
arr[x] = arr[y] | |
arr[y] = temp | |
def partition(arr, left, right): | |
pivot = arr[left] | |
low = left + 1 | |
high = right - 1 | |
while low <= high: | |
while low <= high and arr[low] <= pivot: | |
low += 1 | |
while high >= low and arr[high] >= pivot: | |
high -= 1 | |
if low < high: | |
swap(arr, low, high) | |
swap(arr, left, high) | |
return high | |
def quick_sort(arr, left, right): | |
if left < right - 1: | |
q = partition(arr, left, right) | |
quick_sort(arr, left, q) | |
quick_sort(arr, q + 1, right) | |
return arr | |
def qs(arr): | |
arr2 = arr[:] | |
quick_sort(arr, 0, len(arr)) | |
arr2.sort() | |
assert arr2 == arr | |
return arr | |
for i in range(1, 1000): | |
print(qs([randint(1, 200) for ii in range(0, 1000)])) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment