Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

TP1

No description
by

Anderson Nascimento

on 21 October 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of TP1

TIM SORT
Anderson Nascimento
O TimSort 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
Universidade Catolica de Minas Gerais , Projeto de Algoritmos, 2013
Obrigado,
Anderson Nascimento.
Projeto de Algoritmos
O TIMSORT, atualmente é usado
para ordenar arrays em Java SE 7
O que é o TIMSORT
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.
Como o TimSort Funciona
Timsort foi projetado para tirar vantagem de ordenações parciais que já existem na maioria dos dados do mundo real. Timsort opera encontrando subconjuntos de execuções, pelo menos dois elementos são necessarios.
A execução do Timsort verifica se os dados são ou não- descendente. Se for descendente, ele deve ser estritamente descendente , posteriormente a execução é modificada por uma simples permuta de elementos de ambas as extremidades convergentes no meio.

Uma execução natural do TimSort é uma sub-matriz que já está encomendada. Os Runs(execuções) naturais em dados do mundo real podem ser de comprimentos variados, o Timsort escolhe uma técnica de classificação, dependendo da duração da execução.
Por exemplo, se o comprimento de percurso é menor do que um determinado valor, o tipo de inserção é utilizada. Assim Timsort é uma espécie de adaptação.
Uma vez executado, os comprimentos são otimizados e as execuções são mescladas. Quando é encontrada uma execução e o algoritmo empurra o seu endereço de comprimento e de base sobre uma pilha. A função determina se o prazo deve ser mesclado com execuções anteriores.
Timsort não mescla execuções consecutivas, porque isso faria com que o elemento comum a todas as três execuções se tornassem fora de ordem com relação ao prazo médio.
A fusão dos funcionamentos adjacentes é feita com a ajuda da memória temporária. A memória temporária é o tamanho da menor das duas listas.
O algoritmo copia a menor das duas execuções para a memória temporária e, em seguida, utiliza a memória original (do menor prazo) e da memória do outro prazo para armazenar a saída ordenada.
Complexidade do espaço O(n)
Pesquisa Binária
é um algoritmo de busca em vetores que segue o paradigma de divisão e conquista. Ela parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca comparando o elemento buscado (chave) com o elemento no meio do vetor.
O que é a Pesquisa Binária
Se o elemento do meio do vetor for a chave, a busca termina com sucesso. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor. E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor.
Buscando uma coleção ordenada é uma tarefa comum. Um dicionário é uma lista ordenada de definições de palavras. Dada uma palavra, pode-se encontrar a sua definição. A lista telefônica é uma lista ordenada de nomes de pessoas, endereços e números de telefone. Sabendo o nome de alguém permite encontrar rapidamente o seu número de telefone e endereço.
Universidade Catolica de Minas Gerais. Projeto de Algoritmos. 2013
Full transcript