Metodos de Ordenação

Prévia do material em texto

SOCIEDADE DE ENSINO 
SUPERIOR ESTÁCIO DE SÁ
Métodos de Ordenação
Nome: 						Mat.: 
Disciplina: Estrutura de Dados 	Professor: 
 
Rio de Janeiro
Data: - - 
MÉTODOS SIMPLES
SELECTION SORT 
Seleciona o menor valor do vetor (ou o maior dependendo da ordem requerida), sendo esse o menor valor, ele ainda verifica os valores até encontrar o menor valor entre os vetores e depois ordena em ordem crescente (ou decrescente) em suas respectivas posições.
INSERTION SORT
Verifica o menor valor dos vetores e puxa para a esquerda realocando-se em uma posição de um valor menor que o dele próprio. Passa apenas uma vez pelos vetores finalizando seu processo.
BUBBLE SORT
Percorre o vetor por diversas vezes, a cada passagem fazendo flutuar para o topo o maior elemento da sequência.
COMB SORT		
Reordena diferentes pares de itens, separados por um salto, que é calculado a cada passagem.O salto seria para evitar lentidão.
MÉTODOS SOFISTICADOS 
MERGE SORT
Pega os vetores separa em 2 grupos por exemplo, depois verifica os menores valores e armazena-os em ordem crescente. Dividir(o problema em vários sub-problemas e resolver esses sub-problemas através da recursividade) e Conquistar(após todos os sub-problemas terem sido resolvidos ocorre a conquista que é a união das resoluções dos sub-problemas).
HEAPSORT
Conjuntos ordenados aleatoriamente, tem um uso de memória bem comportado e o seu desempenho em pior cenário é praticamente igual ao desempenho em cenário médio.
SHELL SORT
O algoritmo passa várias vezes pela lista dividindo o grupo maior em menores. Nos grupos menores é aplicado o método da ordenação por inserção. Implementações do algoritmo.
RADIX SORT
O radix sort LSD começa do dígito menos significativo até o mais significativo, ordenando tipicamente da seguinte forma: chaves curtas vem antes de chaves longas, e chaves de mesmo tamanho são ordenadas lexicograficamente. Isso coincide com a ordem normal de representação dos inteiros, como a seqüência "1, 2, 3, 4, 5, 6, 7, 8, 9, 10". Os valores processados pelo algoritmo de ordenação são frequentemente chamados de “chaves”, que podem existir por si próprias ou associadas a outros dados. As chaves podem ser strings de caracteres ou números.
Já o radix sort MSD trabalha no sentido contrário, usando sempre a ordem lexicográfica, que é adequada para ordenação de strings, como palavras, ou representações de inteiros com tamanho fixo. A seqüência "b, c, d, e, f, g, h, i, j, ba" será ordenada lexicograficamente como "b, ba, c, d, e, f, g, h, i, j". Se essa ordenação for usada para ordenar representações de inteiros com tamanho variável, então a representação dos números inteiros de 1 a 10 terá a saída "1, 10, 2, 3, 4, 5, 6, 7, 8, 9".
GNOME SORT
O algoritmo percorre o vetor comparando seus elementos dois a dois, assim que ele encontra um elemento que está na posição incorreta, ou seja, um número maior antes de um menor, ele troca a posição dos elementos, e volta com este elemento até que encontre o seu respectivo lugar.
COUNTING SORT
As chaves podem tomar valores entre 0 e M-1. Se existirem k0 chaves com valor 0, então ocupam as primeiras k0 posições do vetor final: de 0 a k0-1.
BUCKET SORT
funciona dividindo um vetor em um número finito de recipientes. Cada recipiente é então ordenado individualmente, seja usando um algoritmo de ordenação diferente, ou usando o algoritmo bucket sort recursivamente. O bucket sort tem complexidade linear (Θ(n)) quando o vetor a ser ordenado contém valores que são uniformemente distribuídos.
COCKTAIL SORT
 ordena em ambas as direções em cada passagem através da lista.
QUICK SORT
Rearranjar as chaves de modo que as chaves "menores" precedam as chaves "maiores". Em seguida o Quicksort ordena as duas sublistas de chaves menores e maiores recursivamente até que a lista completa se encontre ordenada.
REFERÊNCIAS:
http://hg.openjdk.java.net/jdk7/tl/jdk/rev/bfd7abda8f79
http://www.dei.isep.ipp.pt/~i960231/ei/bubblesort.htm
http://manfred.com.br/index.php/bsi/estrutura-de-dados-ii/154-aula-03-ordenacao-pelos-metodos-insertion-sort-e-selection-sort
http://www.decom.ufop.br/toffolo/site_media/uploads/2011-2/bcc202/slides/20._ordenacao_em_tempo_linear.pdf