Olá caros amigos,
Abaixo um breve descrição dos metodos de ordenação e sua complexidade.
Inicialmente é um esquema pra prova de Analise de Algotimo, futuramente vou colocar implementações e imagens!
Bubble
A ideia é percorrer o vector diversas vezes, a cada passagem fazendo flutuar para o topo o menor elemento da sequência. Essa movimentação lembra a forma como as bolhas em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo.
Complexidade: O(n²)
Heap
O método de ordenação heap sort consiste numa árvore binária completa que obedece às seguintes propriedades:
• Se o nó x é pai do nó y, então chave(x)>chave(y).
• No último nível da árvore as folhas “são colocadas” em sequência, da esquerda para direita.
Complexidade: O (n log n)
Bogo
A técnica milenar tem por ideia você embaralhar o baralho, e de tempo em tempo conferir se as cartas estão em ordem. O processo se repete até que finalmente o baralho esteja ordenado.
Complexidade: O(n * n!)
Count
1. Cria cnt[M+1] e b[max N]
2. Inicializa todas as posições de cnt a 0.
3. Percorre o vector a e, para cada posição i de a faz cnt[a[i]+1]++ o que faz com que, no final, cada posição i de cnt contem o nº de vezes que a chave i-1 aparece em a.
4. Acumula em cada elemento de cnt o elemento somado ao elemento anterior: cnt[i] indica a posição ordenada do primeiro elemento de chave i.
5. Guarda em b os valores de a ordenados de acordo com b[cnt[a[i]++]=a[i]
6. Copia b para a.
Complexidade: O(n)
Shell
É uma extensão da ordenação por inserção
O Método de Inserção troca itens adjacentes quando procura o ponto de inserção na seqüência destino
Se o menor item estiver na posição mais a direita no vetor, então o número de comparações e movimentações é igual a n – 1 para encontrar o seu ponto de inserção
Complexidade: O(n²)
Selection
1. No primeiro passo você encontra o maior valor, e então troca ele pelo último item. Assim o maior item está agora na posição N.
2. No segundo passo você faz uma varredura apenas nos N-1 elementos. O maior dos itens é troca de posição com o item na posição N-1. Assim o maior de todos os itens está aogra na última posição; o segundo maior na segunda maior posição.
3. Este processo é repetido, com um item sendo colocado na sua posição correta a cada vez.
4. Depois de N passos, a coleção inteira de dados está ordenada.
Complexidade: O(n²)
Merge
1. Dividir: Dividir os dados em subsequências pequenas;
2. Conquistar: Classificar as duas metades recursivamente aplicando o merge sort;
3. Combinar: Juntar as duas metades em um único conjunto já classificado.
Complexidade: O(n log n)
Quick
1. Dividir o problema de ordenar um conjunto de n itens em dois problemas menores
2. Ordenar independentemente os problemas menores
3. Combinar os resultados para produzir a solução do problema maior
Complexidade: O(n²)
Radix
Radix sort é um algoritmo de ordenação que ordena inteiros processando dígitos individuais.
Métodos que tiram proveito das propriedades digitais destes números
Processamento e comparação de pedaços (bits) das Chaves
Complexidade: O(n*k) , onde K pode ser considerado sua gramática
Bucket
Bucket sort, ou bin sort, é um algoritmo de ordenação que 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.
Complexidade: O(n)
Insert
Os elementos são divididos em uma seqüência de destino a1, ..., ai-1 e em uma seqüência fonte ai, ..., an.
Em cada passo, a partir de i =2, o i-ésimo item da seqüência fonte é retirado e transferido para a seqüência destino sendo inserido na posição adequada
Complexidade: O(n²)
Cocktail
Este metodo de ordenação funciona como o Bubble Sort, mas de forma bidirecional e também é conhecido como shakesort.
Complexidade: O(n²)
Gnome
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.
Complexidade: O(n²)
