Timsort: diferenças entre revisões

Conteúdo apagado Conteúdo adicionado
Linha 14:
'''Timsort''' é um [[algoritmo de ordenação]] híbrido derivado do [[merge sort]] e do [[insertion sort]], projetado para ter boa performance em vários tipos de dados do mundo real. Foi inventado por Tim Peters em 2002 para ser usado na linguagem de programação [[Python]], e tem sido o algoritmo de ordenação padrão de Python desde a versão 2.3. Ele atualmente é usado para ordenar [[array|arrays]] em [[Java (linguagem de programação)|Java SE 7]].<ref>http://hg.openjdk.java.net/jdk7/tl/jdk/rev/bfd7abda8f79</ref>
 
Tim Peters describesdescreve theo algorithmalgoritmo asda followsseguinte forma<ref>http://bugs.python.org/file4451/timsort.txt</ref>:
<!--
 
{{quote|[...]um adaptativo, estável, merge sort natural, modestamente chamado de timsort (hey, eu ganhei ele &lt;wink&gt;). Tem desempenho sobrenatural em muitos tipos de arrays parcialmente ordenados (menos de lg(N!) comparações necessárias, e tão poucas quanto N-1), no entanto, tão rápido quanto o algoritmo anterior altamente sintonizado, híbrido, samplesort de Python em matrizes aleatórias.
Tim Peters describes the algorithm as follows<ref>http://bugs.python.org/file4451/timsort.txt</ref>:
 
Em suma, a rotina principal passa sobre a matriz uma vez, da esquerda para a direita, alternadamente, identificando o próximo passo, em seguida, fundindo-os em passos anteriores "inteligentemente". Todo o resto é complicação pela velocidade, e alguma medida duramente conquistada da eficiência de memória.}}
{{quote|[...] an adaptive, stable, natural mergesort, modestly called timsort (hey, I earned it &lt;wink&gt;). It has supernatural performance on many kinds of partially ordered arrays (less than lg(N!) comparisons needed, and as few as N-1), yet as fast as Python's previous highly tuned samplesort hybrid on random arrays.
 
<!--
In a nutshell, the main routine marches over the array once, left to right, alternately identifying the next run, then merging it into the previous runs "intelligently". Everything else is complication for speed, and some hard-won measure of memory efficiency.}}
 
Like merge sort, it is a [[stable sort|stable]] [[comparison sort]] with a [[Best, worst and average case|worst-case time complexity]] of <math>\Theta(n \log n)</math>.<ref>http://mail.python.org/pipermail/python-dev/2002-July/026837.html</ref>