1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| def partition(arr, start, end):
pivot = arr[start]
arr[end], arr[start] = arr[start], arr[end]
i = start
for j in xrange(start, end, 1):
if arr[j] <= pivot:
if i != j:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[end], arr[i] = arr[i], arr[end]
return i
def qsort_r(arr, start, end):
if start < end:
p = partition(arr, start, end)
qsort_r(arr, start, p - 1)
qsort_r(arr, p + 1, end)
def qsort(arr):
qsort_r(arr, 0, len(arr) - 1)
|