Timsort: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m ajustes gerais nas citações, outros ajustes usando script |
|||
Linha 2:
|classe =[[Algoritmo de ordenação]]
|imagem =
|estrutura =[[Array]], [[Lista ligada|Listas ligadas]]
|data =2002
|pior_caso =<math>\Theta(n\log n)</math>
Linha 11:
}}
'''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
Tim Peters descreve o algoritmo da seguinte forma<ref>http://bugs.python.org/file4451/timsort.txt</ref>:
Linha 19:
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 [[
De acordo com a [[teoria da Informação]], nenhuma [[ordenação por comparação]] pode executar em menos de <math>\log_2(n!)</math>, no caso médio, o que exige que a ordenação por comparação tome um tempo de <math>\Omega(n \log n)</math> em dados aleatórios. No entanto, em dados do mundo real, o Timsort muitas vezes exige muito menos do que <math>\log_2(n!)</math>, porque ele tira vantagem do fato de que sublistas dos dados podem já estar em ordem ou ordem inversa.<ref>{{
==
* [[Merge sort]]
* [[Insertion sort]]
Linha 30:
{{Referências}}
==
* [http://corte.si/posts/code/timsort/index.html Visualising Timsort] - a fonte para a imagem desta página.
| |||