2878
Comentário:
|
← Revisão 13e 2009-11-17 09:20:20 ⇥
4715
|
Deleções são marcadas assim. | Adições são marcadas assim. |
Linha 1: | Linha 1: |
= 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. |
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. |
Linha 7: | Linha 5: |
Logo abaixo, outro exemplo. | Logo abaixo, outros exemplos. |
Linha 9: | Linha 7: |
{{{ #!python # Written by Magnus Lie Hetland |
{{{#!python # Written by Magnus Lie Hetland |
Linha 18: | Linha 15: |
done = 0 | done = 0 |
Linha 60: | Linha 57: |
import string print string.join(map(str,list)) |
print ' '.join(map(str,list)) |
Linha 63: | Linha 59: |
Linha 66: | Linha 61: |
{{{ #!python |
{{{#!python |
Linha 90: | Linha 84: |
Exemplo aproveitando códigos da lista python-brasil, idéia de José Alexandre Nalon, adaptada por JoaoPauloFarias: | |
Linha 91: | Linha 86: |
Exemplo aproveitando códigos da lista python-brasil, idéia de José Alexandre Nalon, adaptada por JoaoPauloFarias: {{{ #!python |
{{{#!python |
Linha 99: | Linha 89: |
if l: left = [x for x in l if x < l[0]] right = [x for x in l if x > l[0]] if len(left) > 1: left = quicksort(left) if len(right) > 1: right = quicksort(right) return left + [l[0]] * l.count(l[0]) + right return [] |
if l: left = [x for x in l if x < l[0]] right = [x for x in l if x > l[0]] if len(left) > 1: left = quicksort(left) if len(right) > 1: right = quicksort(right) return left + [l[0]] * l.count(l[0]) + right return [] |
Linha 114: | Linha 104: |
Exemplos encontrados em uma pesquisa na web, são algoritimos curtos que usam recursos bacanas da linguagem, um deles usa as novas funcionalidades da versão 2.5. Esse só funciona com PYTHON 2.5, último acesso em 27 de março de 2008, endereço: http://news.e-scribe.com/314 {{{ >>> q=lambda s:s if len(s)<2 else q([x for x in s[1:]if x<s[0]])+[s[0]]+q([x for x in s[1:]if x>=s[0]]) >>> print q([9,7,5,3,1,8,6,4,2]) [1, 2, 3, 4, 5, 6, 7, 8, 9] }}} O seguinte vem do site ASPN, Python CookBook, último acesso em 27 de março de 2008, endereço: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/66473 {{{ >>> def qsort(L): if len(L) <= 1: return L return qsort( [ lt for lt in L[1:] if lt < L[0] ] ) + \ [ L[0] ] + qsort( [ ge for ge in L[1:] if ge >= L[0] ] ) }}} E por fim um utilizando lambda, é necessário paginar o texto algumas vezes, último acesso em 27 de março de 2008, endereço: http://www.ntecs.de/old-hp/uu9r/lang/html/python.en.html {{{#!python # # QuickSort in Python # von Michael Neumann # def quicksort(arr): if len(arr) <= 1: return arr m = arr[0] return quicksort(filter(lambda i,j=m: i<j, arr)) + \ filter(lambda i,j=m: i==j, arr) + \ quicksort(filter(lambda i,j=m: i>j, arr)) # Aufruf print quicksort([5,99,2,45,12,234,29,0]) }}} Uma outra implementação possível usaria ''list comprehentions'', que usualmente são consideradas mais legíveis: {{{#!python def quicksort(arr): if len(arr) <= 1: return arr m = arr[0] return quicksort([i for i in arr if i < m]) + \ [i for i in arr if i == m] + \ quicksort([i for i in arr if i > m]) print quicksort([5,99,2,45,12,234,29,0]) }}} |
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, outros exemplos.
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 print ' '.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]
Exemplos encontrados em uma pesquisa na web, são algoritimos curtos que usam recursos bacanas da linguagem, um deles usa as novas funcionalidades da versão 2.5.
Esse só funciona com PYTHON 2.5, último acesso em 27 de março de 2008, endereço: http://news.e-scribe.com/314
>>> q=lambda s:s if len(s)<2 else q([x for x in s[1:]if x<s[0]])+[s[0]]+q([x for x in s[1:]if x>=s[0]]) >>> print q([9,7,5,3,1,8,6,4,2]) [1, 2, 3, 4, 5, 6, 7, 8, 9]
O seguinte vem do site ASPN, Python CookBook, último acesso em 27 de março de 2008, endereço: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/66473
>>> def qsort(L): if len(L) <= 1: return L return qsort( [ lt for lt in L[1:] if lt < L[0] ] ) + \ [ L[0] ] + qsort( [ ge for ge in L[1:] if ge >= L[0] ] )
E por fim um utilizando lambda, é necessário paginar o texto algumas vezes, último acesso em 27 de março de 2008, endereço: http://www.ntecs.de/old-hp/uu9r/lang/html/python.en.html
1 #
2 # QuickSort in Python
3 # von Michael Neumann
4 #
5
6 def quicksort(arr):
7 if len(arr) <= 1: return arr
8 m = arr[0]
9 return quicksort(filter(lambda i,j=m: i<j, arr)) + \
10 filter(lambda i,j=m: i==j, arr) + \
11 quicksort(filter(lambda i,j=m: i>j, arr))
12
13
14
15 # Aufruf
16 print quicksort([5,99,2,45,12,234,29,0])
Uma outra implementação possível usaria list comprehentions, que usualmente são consideradas mais legíveis: