Revisão das 01h59min de 10 de dezembro de 2017 editar Gilson Mendes da Silva Júnior (discussão \| contribs) 14 edições →‎Análise de Complexidade ← Ver a alteração anterior		Revisão das 14h36min de 28 de fevereiro de 2018 editar desfazer Mschlindwein (discussão \| contribs) Autorrevisores 100 076 edições m "Extendidos" não existe em Português. Ver a alteração posterior →
Linha 15: TimSort <ref name=":0" /> é um algoritmo híbrido de ordenação baseado no [[Merge sort\|MergeSort]] e [[Insertion sort\|InsertionSort]]. O algoritmo baseia-se na ideia de que, no mundo real, um vetor de dados a ser ordenado contém sub-vetores já ordenados, não importando como (decrescentemente ou crescentemente). Assim, o TimSort está à frente da maioria dos algoritmos de ordenação, mesmo não apresentando descobertas matemáticas complexas. O fato é que na realidade o TimSort não é um algoritmo autônomo, mas um híbrido, uma combinação eficiente de outros algoritmos, temperado com as idéias do autor. O algoritmo completo comentado, traduzido do [[Python]] para [[Java (linguagem de programação)\|Java]] pode ser encontrado no site da [http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/raw_files/new/src/share/classes/java/util/TimSort.java openjdk]. O algoritmo ordena um segmento específico do vetor de entrada incrementalmente da esquerda para a direita, buscando por consecutivos elementos ordenados. Se esses segmentos não forem grande o suficente eles são ~~extendidos~~estendidos e ordenados usando o [[Insertion sort\|InsertionSort]]. A posição de início e o tamanho dos segmentos gerados são armazenados em uma [[Pilha (informática)\|pilha]]. Durante a execução alguns desses segmentos são combinados (via [[Merge sort\|Mergesort]]) de acordo com condições analisadas sobre os elementos que estão no topo da pilha, garantindo que os comprimentos dos segmentos gerados estão diminuindo e o comprimento de cada segmento gerado é maior que a soma dos próximos dois. No final, faz-se o merge de todos elementos restante, resultando em um vetor ordenado. TimSort é um algoritmo de ordenação bastante eficiente se comparado aos demais existentes na literatura. Isso o levou a ser escolhido como algoritomo de ordenação padrão em linguagens de programação como [[Python]] e [[Java (linguagem de programação)\|Java]].

Timsort: diferenças entre revisões