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
<!--▼
{{quote|[...]um adaptativo, estável, merge sort natural, modestamente chamado de timsort (hey, eu ganhei ele <wink>). 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.}}
▲<!--
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>
|