41 lines
792 B
Python
Executable File
41 lines
792 B
Python
Executable File
#!/usr/bin/env python3
|
|
# vim: set ts=2 sw=2 et tw=80:
|
|
|
|
import sys
|
|
import random
|
|
|
|
|
|
def partition(A, begin, end):
|
|
v_i = random.randrange(begin, end)
|
|
v = A[v_i]
|
|
A[v_i], A[end - 1] = A[end - 1], A[v_i]
|
|
i = begin
|
|
j = end - 2
|
|
while j >= i:
|
|
if A[j] > v:
|
|
j = j - 1
|
|
elif A[i] <= v:
|
|
i = i + 1
|
|
else:
|
|
A[i], A[j] = A[j], A[i]
|
|
j = j - 1
|
|
i = i + 1
|
|
A[i], A[end - 1] = A[end - 1], A[i]
|
|
return i
|
|
|
|
|
|
def quicksort(A, begin, end):
|
|
if begin < end - 1:
|
|
i = partition(A, begin, end)
|
|
print(A[begin:i], A[i], A[i + 1:end])
|
|
quicksort(A, begin, i)
|
|
quicksort(A, i + 1, end)
|
|
print(A[begin:i], A[i], A[i + 1:end])
|
|
|
|
|
|
if __name__ == "__main__":
|
|
args = [int(x) for x in sys.argv[1:]]
|
|
print(args)
|
|
quicksort(args, 0, len(args))
|
|
print(args)
|