Timsort

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Timsort
classe Algoritmo de ordenação
estrutura de dados Array, Listas ligadas
complexidade pior caso \Theta(n\log n)
complexidade caso médio \Theta(n\log n)
complexidade melhor caso \Theta(n)
complexidade de espaços pior caso \Theta(n)
estabilidade estável
data 2002
Algoritmos

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 arrays em Java SE 7.1

Tim Peters descreve o algoritmo da seguinte forma2 :

[...]um adaptativo, estável, merge sort natural, modestamente chamado de timsort (hey, eu mereço <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. 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.


Como o merge sort, é um algoritmo de ordenação por comparação estável com uma complexidade de pior caso de \Theta(n \log n).3

De acordo com a teoria da Informação, nenhuma ordenação por comparação pode executar em menos de \log_2(n!), no caso médio, o que exige que a ordenação por comparação tome um tempo de \Omega(n \log n) em dados aleatórios. No entanto, em dados do mundo real, o Timsort muitas vezes exige muito menos do que \log_2(n!), porque ele tira vantagem do fato de que sublistas dos dados podem já estar em ordem ou ordem inversa.4

Ver também[editar | editar código-fonte]

Referências

Ligações externas[editar | editar código-fonte]