Quicksort
Algoritmo [1, p. 171], [2, p. 176]:
def QuickSort(A, l=None, r=None):
if (l is None):
l = 0
if (r is None):
r = len(A)-1
if (l < r):
s = Partition(A, l, r)
QuickSort(A, l, s-1)
QuickSort(A, s+1, r)
Para a seleção do pivô / partição (método "Partition"), mostraremos 2 possibilidades:
1) Hoare Partition [2, p. 178]:
def Partition(A, l, r):
p = A[l]
(i, j) = (l, r+1)
i_greater_or_equal_j = False
while not i_greater_or_equal_j:
i_condition = False
while not i_condition:
i = i + 1
i_condition = (A[i] >= p)
j_condition = False
while not j_condition:
j = j - 1
j_condition = (A[j] <= p)
(A[i], A[j]) = (A[j], A[i])
i_greater_or_equal_j = (i >= j)
(A[i], A[j]) = (A[j], A[i])
(A[l], A[j]) = (A[j], A[l])
return j
2) [1, p. 171]
def Partition(A, p, r):
x = A[r]
i = p-1
for j in range(p, r):
if (A[j] <= x):
i = i + 1
(A[i], A[j]) = (A[j], A[i])
(A[i+1], A[r]) = (A[r], A[i+1])
return i+1
Exemplo:
if __name__ == '__main__':
x=[5, 3, 8, 9, 1, 7, 2, 4, 6, 7, 2, 4, 6, 8, 9, 1, 7]
QuickSort(x)
print x
Referências:
[1] Cormen, T. H.; Leiserson, C. E.; Rivest, R.; Stein, C. "Introduction to Algorithms". MIT Press, 2009. 3 ed.
[2] Levitin, A. "Introduction to the design and analysis of algorithms". Pearson, 2011. 3 ed.