Algorítmos de Ordenação - Parte III

Estes primeiros algorítmos são bastante óbvios, embora não apresentem bom desempenho.

Straight Insertion Sort (Ordenação por Inserção Direta)

Este é um dos mais simples algorítmos de ordenação e funciona como um jogador de cartas organizando a sua mão. Durante a execução deste algorítmo, as primeiras chaves estão ordenadas (no início esta parte esta vazia, no final todas as chaves foram ordenadas). Pegamos a primeira chave ainda não ordenada e achamos o seu lugar nas já ordenadas e a inserimos aí. Repetimos isto até que todas as chaves estejam ordenadas (ver a Figura 1) Este algorítmo pode levar a muitas movimentações de chaves, principalmente se elas estiverem em ordem inversa no início. Ele é bastante simplas de codificar, não requer memória adicional e é estável. É evidente que os tempos médio e máximo são proporcionais a N².

Figura 1 - Ordenando por Straight Insertion

Bubble Sort (Ordenação por Bolhas)

A idéia aqui é semelhante à inserção direta, mas, ao invés de fazermos várias comparações e depois inserir a chave atual no lugar correto, trocamos imediatamente de lugar a chave atual com a anterior se descobrimos que uma deve vir antes da outra. Desta forma os valores menores sobem para o topo da lista, como bolhas na água (ver a Figura 2). Como o Straight Insertion, é muito simples, não requer memória adicional, é estável e os tempos médio e máximo são proporcionais a N².

Figura 2 - Ordenando com o Bubble Sort (passo final)

Na próxima parte vamos ver um algorítmo menos comum, o Shell Sort.