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

Métodos de Ordenação

Shell Sort, Buble Short, Quick Sort, Comb Sort e Inserção Direta
by

Paulo Ricardo Marinho

on 20 October 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Métodos de Ordenação

Paulo Ricardo Marinho Oliveura RA:0882/09
Marcelo de Sotti Sabbo Sanches RA:0313/09 Complexidade de Algoritmos Algoritmo de Ordenação Métodos de Ordenação Em ciência da computação é um algoritmo que coloca os elementos de uma dada sequência em uma certa ordem - em outras palavras, efetua sua ordenação completa ou parcial. Shell Sort QuickSort É o algoritmo mais rápido que se conhece entre os de ordenação interna para uma ampla variedade de situações. Foi escrito em 1960 e publicado em 1962 por C. A. R. Hoare. Testes dos Métodos Foram efetuados testes com duas massas de dados com tamanho de 100.000 valores, uma com valores aleatórios e a outra com valores 100% desordenados e sequencias. Estes valores foram ordenados utilizando os seguintes métodos: Arquivo Aleatório Arquivo Desordenado Este algoritmo é uma extensão do método InsertShort proposto por Donald Shell em 1959. Métodos simples
- Insertion sort
- Selection sort
- Bubble sort
- Comb sort

Métodos sofisticados :
- Quick sort
- Merge sort
- Heapsort
- Shell sort
- Radix sort
- Gnome sort
- Count sort
- Bucket sort
- Cocktail sort
- Timsort A ordenação Shell utiliza a quebra sucessiva da sequência a ser ordenada e implementa a ordenação por inserção na sequência obtida. O diferencial do ShellSort é a divisão em h intervalos que ele realiza para posteriormente aplicar o método de inserção. Vantagens Shellsort é uma ótima opção para arquivos de tamanho moderado. Sua implementação é simples e requer uma quantidade de código pequena. Desvantagens O tempo de execução do algoritmo é sensível à ordem inicial do arquivo. O método não é estável Exemplo de execução O método de seleção de valores para h utilizado foi proposto por Donald Knuth. Explicado como:
h = 3*h+1
onde h seja o maior valor possível menor que o tamanho do vetor.
A sequência gerada é: 1, 4, 13, 40, 121, 364, 1093, 3280... O método de seleção de valores para h proposto por Donald Shell foi h = n/2 onde n é o número de elementos do vetor. Mas foi provado que sua eficiencia é baixa. Testes Foram efetuados testes considerando o tamanho de h, em um vetor aleatório com 100.000 valores aleatórios. Adotando a estratégia "Dividir para conquistar" o funcionamento resume-se a dividir o problema de ordenar um vetor de n posições em dois outros menores. Vantagens É extremamente eficiente para ordenar arquivos de dados. Necessita de apenas uma pequena pilha como memória auxiliar. Requer cerca de n log n comparações em média para ordenar n itens. Desvantagens Tem um pior caso O(n2) comparações. Sua implementação é muito delicada e difícil: Um pequeno engano pode levar a efeitos inesperados para algumas entradas de dados. Exemplo de Execução CombSort O algoritmo Comb sort (ou Combo sort ou ainda algoritmo do pente) é um algoritmo de ordenação relativamente simples, e faz parte da família de algoritmos de ordenação por troca. Foi desenvolvido em 1980 por Wlodzimierz Dobosiewicz. Como funciona - Exemplo Primeira Varredura (h = 5 div 1,3 = 3)
28 26 30 24 25 compara par (28,24): troca.
24 26 30 28 25 compara par (26,25): troca. Segunda Varredura (h = 3 div 1,3 = 2)
24 25 30 28 26 compara par(24,30): não troca
24 25 30 28 26 compara par(25,28): não troca
24 25 30 28 26 compara par(30,26): troca Implementação Terceira Varredura (h = 2 div 1,3 = 1)
24 25 26 28 30 compara par(24,25): não troca
24 25 26 28 30 compara par(25,26): não troca
24 25 26 28 30 compara par(26,28): não troca
24 25 26 28 30 compara par(28,30): não troca Inserção Direta
ShellSort
BubbleSort
CombSort
QuickSort Complexidade dos Métodos Todos estes métodos apresentam uma determinada complexidade média, estas foram representadas na tabela abaixo: Como funciona O Algoritmo repetidamente reordena diferentes pares de itens, separados por um salto, que é calculado a cada passagem. Método semelhante ao Bubble Sort, porém mais eficiente. Na Bubble sort, quando quaisquer dois elementos são comparados, eles sempre têm um gap (distância um do outro) de 1. A idéia básica do Comb sort é que a diferença pode ser muito mais do que um. O gap (intervalo) começa como o comprimento da lista a ser ordenada dividida pelo fator de encolhimento (em geral 1,3) Exemplo de Execução Fim Ms. André Mendes Garcia
Full transcript