|
Tamanho: 2904
Comentário:
|
Tamanho: 2878
Comentário:
|
| Deleções são marcadas assim. | Adições são marcadas assim. |
| Linha 10: | Linha 10: |
| #!/usr/bin/env python | #!python |
| Linha 67: | Linha 67: |
| #!/usr/bin/env python | #!python |
Quicksort
Script de ordenação rádida, inventado por C.A.R. Hoare. O algoritmo gasta o tempo proporcional a n log(n) em média e a n² no pior caso.
O código abaixo foi extraído de http://www.hetland.org/python/quicksort.html e foi escrito por Magnus Lie Hetland e os comentários foram removidos.
Logo abaixo, outro exemplo.
1 # Written by Magnus Lie Hetland
2
3 def partition(list, start, end):
4 pivot = list[end]
5 bottom = start-1
6 top = end
7
8 done = 0
9 while not done:
10
11 while not done:
12 bottom = bottom + 1
13
14 if bottom == top:
15 done = 1
16 break
17
18 if list[bottom] > pivot:
19 list[top] = list[bottom]
20 break
21
22 while not done:
23 top = top-1
24
25 if top == bottom:
26 done = 1
27 break
28
29 if list[top] < pivot:
30 list[bottom] = list[top]
31 break
32
33 list[top] = pivot
34 return top
35
36 def quicksort(list, start, end):
37 if start < end:
38 split = partition(list, start, end)
39 quicksort(list, start, split-1)
40 quicksort(list, split+1, end)
41 else:
42 return
43
44 if __name__=="__main__":
45 import sys
46 list = map(int,sys.argv[1:])
47 start = 0
48 end = len(list)-1
49 quicksort(list,start,end)
50 import string
51 print string.join(map(str,list))
Exemplo retirado da http://en.wikipedia.org/wiki/Quicksort:
1 def partition(array, begin, end, cmp):
2 while begin < end:
3 while begin < end:
4 if cmp(array[begin], array[end]):
5 (array[begin], array[end]) = (array[end], array[begin])
6 break
7 end -= 1
8 while begin < end:
9 if cmp(array[begin], array[end]):
10 (array[begin], array[end]) = (array[end], array[begin])
11 break
12 begin += 1
13 return begin
14
15 def sort(array, cmp=lambda x, y: x > y, begin=None, end=None):
16 if begin is None: begin = 0
17 if end is None: end = len(array)
18 if begin < end:
19 i = partition(array, begin, end-1, cmp)
20 sort(array, cmp, begin, i)
21 sort(array, cmp, i+1, end)
Exemplo aproveitando códigos da lista python-brasil, idéia de José Alexandre Nalon, adaptada por JoaoPauloFarias:
1 >>> def quicksort(l):
2 if l:
3 left = [x for x in l if x < l[0]]
4 right = [x for x in l if x > l[0]]
5 if len(left) > 1:
6 left = quicksort(left)
7 if len(right) > 1:
8 right = quicksort(right)
9 return left + [l[0]] * l.count(l[0]) + right
10 return []
11
12 >>> quicksort(lista)
13 [0, 1, 2, 3, 3, 4, 5, 7, 8, 8, 9, 9, 12, 13, 85, 99]
14 >>> lista
15 [1, 5, 3, 9, 2, 4, 8, 7, 3, 9, 8, 12, 13, 0, 99, 85]
