Diferenças para "QuickSort"

Diferenças entre as versões de 3 e 11 (8 versões de distância)

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     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]

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])

-  ⇤ ← Revisão  3e 2004-09-18 22:00:41 → 
  Tamanho: 1221
  Editor: 200
  Comentário:
+   ← Revisão  11e 2008-09-26 15:13:40 → ⇥
  Tamanho: 4264
  Editor: OsvaldoSantanaNeto
  Comentário:
-Deleções são marcadas assim.
+Adições são marcadas assim.
 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.
 Linha 3:
-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.
-Linha 6:
+Linha 8:
-#!/usr/bin/env python
+#!python
# Written by Magnus Lie Hetland
-Linha 10:
+Linha 13:
-    last value
-Linha 14:
+Linha 16:
     done = 0
-Linha 18:
+Linha 20:
-            bottom = bottom+1
+            bottom = bottom + 1
-Linha 59:
+Linha 61:
+Exemplo retirado da http://en.wikipedia.org/wiki/Quicksort:

{{{
#!python
def partition(array, begin, end, cmp):
    while begin < end:
         while begin < end:
            if cmp(array[begin], array[end]):
                (array[begin], array[end]) = (array[end], array[begin])
                break
            end -= 1
         while begin < end:
            if cmp(array[begin], array[end]):
                (array[begin], array[end]) = (array[end], array[begin])
                break
            begin += 1
    return begin

def sort(array, cmp=lambda x, y: x > y, begin=None, end=None):
    if begin is None: begin = 0
    if end   is None: end   = len(array)
    if begin < end:
        i = partition(array, begin, end-1, cmp)
        sort(array, cmp, begin, i)
        sort(array, cmp, i+1, end)
}}}


Exemplo aproveitando códigos da lista python-brasil, idéia de José Alexandre Nalon, adaptada
por JoaoPauloFarias:

{{{
#!python

>>> def quicksort(l):
 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 []

>>> quicksort(lista)
[0, 1, 2, 3, 3, 4, 5, 7, 8, 8, 9, 9, 12, 13, 85, 99]
>>> lista
[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


{{{
#!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])
}}}

Veja também:

Diferenças para "QuickSort"