Irei mostrar alguns dos principais algoritmos de ordenação, veremos como funciona o Bubble Sort, Selection Sort, Quick Sort, Merge Sort e Heap Sort.
Não colocarei códigos aqui, até porque é muito fácil de encontrar, apenas o funcionamento com explicações e demonstrações em vídeos.
P.S.: Alguns vídeos têm sons!
BUBBLE SORT
O bubble sort, ou ordenação por flutuação (literalmente “por bolha”), é um algoritmo de ordenação dos mais simples. A ideia é percorrer o vetor diversas vezes, a cada passagem fazendo flutuar para o topo o maior 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.
Características :
Algoritmo muito simples;
Lento para ordenar grande número de elementos, mas eficiente com poucos elementos;
O(n2) comparações e trocas;
Adaptativo: O(n) comparações e trocas se o algoritmo estiver parcialmente ordenado.
Pior Caso: O(n2), Caso Médio O(n2) melhor caso O(n).
Animação:
SELECTION SORT
O selection sort (ordenação por seleção) é um algoritmo de ordenação baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os (n-1) elementos restantes, até os últimos dois elementos.
Pior Caso: O(n2), Caso Médio O(n2) Melhor caso O(n2).
Animação:
QUICK SORT
O Quick Sort é um algoritmo baseado em Divisão e Conquista. Isso significa que ele divide sucessivamente um problema e partes menores . O próximo passo é solucionar recursivamente os sub-problemas, ou seja ordenar os elementos, e só então combinar as soluções menores de forma a obter a solução final.
Complexidade:
Pior Caso: O(n2), Caso Médio: O(nlogn) e Melhor caso:O(nlogn).
Animação:
MERGE SORT
Sua idéia básica é muito fácil: criar uma sequência ordenada a partir de duas outras também ordenadas. Para isso, ele divide a sequência original em pares de dados, ordena-as; depois as agrupa em sequências de quatro elementos, e assim por diante, até ter toda a sequência dividida em apenas duas partes.
Os três passos úteis dos algoritmos dividir-para-conquistar, ou divide and conquer, que se aplicam ao merge sort são:
Dividir: Dividir os dados em subsequências pequenas;
Conquistar: Classificar as duas metades recursivamente aplicando o merge sort;
Combinar: Juntar as duas metades em um único conjunto já classificado.
Complexidade:
Pior Caso: O(nlogn), Caso Médio: O(nlogn), Melhor caso:O(nlogn).
Animação:
HEAP SORT
• HeapSort também é um método de seleção – ordena através de sucessivas seleções doelemento correto a ser posicionado em um segmento ordenado
• O HeapSort utiliza um heap binário paramanter o próximo elemento a serselecionado – heap binário: árvore binária mantida na forma de vetor – o heap é gerado e mantido no próprio vetor a ser ordenado (no segmento não-ordenado)
Complexidade:
Pior Caso: O(nlogn), Caso Médio: O(nlogn), Melhor caso:O(nlogn).
Você sabe o que é um Heap? Primeiro vamos entender o que é um Heap.
Heap Binário – Exemplo
• raiz da árvore: primeira posição do vetor
• filhos de um nodo na posição i: posições 2i e 2i + 1
• pai de um nodo na posição i: posição ëi / 2û
Heap Binário Máximo
• Heap Binário tal que um nodo pai tem valor maior ou igual ao valor dos nodos filhos
Funcionamento
1. Transformação do vetor em um heap binário máximo (Construção do Heap)
2. Ordenação – a cada iteração seleciona-se o maior elemento (na raiz do heap) e o adiciona no início de um segmento ordenado – após cada seleção de elemento, o heap deve ser reorganizado para continuar sendo um heap binário máximo.
• Método auxiliar responsável pelo ajuste de um elemento no heap – método ajustaElemento(posição, vetor.lenght)
– realiza trocas no heap para posicionar
corretamente um elemento
• Exemplo: ajustaElemento(1, 7)
Ajuste de Elementos
• Executa até que o elemento seja transferido para uma posição i > ën/2û – após a posição ën/2û , o elemento já é um nodo folha
Etapa de Ordenação
• A cada iteração seleciona o maior elemento do heap (sempre está na primeira posição) e o troca com o elemento no final do segmento não- ordenado
• Após a troca, o novo elemento raiz do heap deve ser ajustado (deve-se chamar ajustaElemento para o nodo raiz)
• O processo termina quando o heap tiver somente 1 elemento (vetor ordenado) Nesse caso, um Heap Máximo.
Referências:
Wikipédia
Vimeo.com
Ordenação de Dados(III)
UFSC-CTC-INE
INE5384 – Estruturas de Dados
Prof. Ronaldo S. Mello
UNICAMP
Abraços!
