Skip to content

Instantly share code, notes, and snippets.

@rmb122
Created October 9, 2022 17:14
Show Gist options
  • Save rmb122/7a645d5bd0135c70fc8f46bdf4442b39 to your computer and use it in GitHub Desktop.
Save rmb122/7a645d5bd0135c70fc8f46bdf4442b39 to your computer and use it in GitHub Desktop.
python quicksort
import copy
import random
import time
import typing
def lomuto_quicksort(arr: typing.List[int]):
if len(arr) <= 1:
return
def _quicksort(arr: typing.List[int], start: int, end: int):
if end - start <= 1:
return
mid = arr[start]
new_part_idx = start
for i in range(start + 1, end):
if arr[i] < mid:
new_part_idx += 1
arr[i], arr[new_part_idx] = arr[new_part_idx], arr[i]
arr[start], arr[new_part_idx] = arr[new_part_idx], arr[start]
_quicksort(arr, start, new_part_idx + 1)
_quicksort(arr, new_part_idx + 1, end)
_quicksort(arr, 0, len(arr))
def hoare_quicksort(arr: typing.List[int]):
if len(arr) <= 1:
return
def _quicksort(arr: typing.List[int], start: int, end: int):
if end - start <= 1:
return
mid = arr[(start + (end - 1)) // 2]
left_idx = start
right_idx = end - 1
while True:
while arr[left_idx] < mid:
left_idx += 1
while arr[right_idx] > mid:
right_idx -= 1
if left_idx >= right_idx:
break
arr[left_idx], arr[right_idx] = arr[right_idx], arr[left_idx]
left_idx += 1
right_idx -= 1
_quicksort(arr, start, right_idx + 1)
_quicksort(arr, right_idx + 1, end)
_quicksort(arr, 0, len(arr))
def lomuto_quicksort_worklist(arr: typing.List[int]):
if len(arr) <= 1:
return
worklist = [(0, len(arr))]
while len(worklist) > 0:
start, end = worklist.pop()
mid = arr[start]
new_part_idx = start
for i in range(start + 1, end):
if arr[i] < mid:
new_part_idx += 1
arr[i], arr[new_part_idx] = arr[new_part_idx], arr[i]
arr[start], arr[new_part_idx] = arr[new_part_idx], arr[start]
tmp = new_part_idx + 1
if tmp - start > 1:
worklist.append((start, tmp))
if end - tmp > 1:
worklist.append((tmp, end))
def hoare_quicksort_worklist(arr: typing.List[int]):
if len(arr) <= 1:
return
worklist = [(0, len(arr))]
while len(worklist) > 0:
start, end = worklist.pop()
mid = arr[(start + (end - 1)) // 2]
left_idx = start
right_idx = end - 1
while True:
while arr[left_idx] < mid:
left_idx += 1
while arr[right_idx] > mid:
right_idx -= 1
if left_idx >= right_idx:
break
arr[left_idx], arr[right_idx] = arr[right_idx], arr[left_idx]
left_idx += 1
right_idx -= 1
tmp = right_idx + 1
if tmp - start > 1:
worklist.append((start, tmp))
if end - tmp > 1:
worklist.append((tmp, end))
def benchmark(algo: typing.Callable[[typing.List[int]], None],
testcase=typing.List[typing.List[int]],
verify=False):
start_time = time.time()
for case in testcase:
if verify:
print(case)
algo(case)
if verify:
print(case)
assert case == sorted(case)
end_time = time.time()
return end_time - start_time
testcase = [[random.randint(-256, 256) for _ in range(256)]
for _ in range(25565)]
print(f'{benchmark(lomuto_quicksort, copy.deepcopy(testcase)) = }')
print(f'{benchmark(lomuto_quicksort_worklist, copy.deepcopy(testcase)) = }')
print(f'{benchmark(hoare_quicksort, copy.deepcopy(testcase)) = }')
print(f'{benchmark(hoare_quicksort_worklist, copy.deepcopy(testcase)) = }')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment