ALGORÍTMOS DE ORDENAÇÃO DE DADOS

...

Por ser de fácil entendimento e implementação, o Bubble Sort (bolha) está entre os mais conhecidos métodos de ordenação de dados. O princípio do Bubble Sort é a troca de valores entre posições consecutivas, fazendo com que os valores mais altos (ou mais baixos) “borbulhem” para o final dos dados, daí o nome Bubble Sort.

Exemplo de ordenação em ordem crescente:

5 - 3 - 1 - 4 - 2

Primeiro compara-se as duas primeiras posições, nesse caso os números 5 e 3, se o primeiro número for maior que o segundo número deve-se fazer uma troca de posição entre eles. Assim ficando:

3 - 5 - 1 - 4 - 2

Após isso, é necessário executar o mesmo passo até o fim da sequência. 5 é maior que 1, então:

3 - 1 - 5 - 4 - 2

5 é maior que 4, logo:

3 - 1 - 4 - 5 - 2

E por último, 5 maior que 2:

3 - 1 - 4 - 2 - 5

Perceba agora que o último valor está em seu lugar adequado. Agora é necessário ordenar o resto da sequência, porém o último item não precisará ser verificado novamente. Então: 1 - 3 - 4 - 2 - 5, 1 - 3 - 2 - 4 - 5, 1 - 2- 3 - 4 - 5.

Conclusão, o Bubble Sort é um método simples de ser implementado e de algoritmo estável, porém, o fato do arquivo já estar ordenado não ajuda em nada, pois ele terá que percorrer todos os dados para efetuar a verificação.

---------------------------------------------------------------

Quick Sort

Quicksort é um método de ordenação muito rápido e eficiente. O Quicksort adota a estratégia de divisão e conquista. A estratégia consiste em 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. Os passos são:

- Escolha um elemento da lista, denominado pivô;

- Rearranje a lista de forma que todos os elementos anteriores ao pivô sejam menores que ele, e todos os elementos posteriores ao pivô sejam maiores que ele. Ao fim do processo o pivô estará em sua posição final e haverá duas sublistas não ordenadas. Essa operação é denominada partição;

- Recursivamente ordene a sublista dos elementos menores e a sublista dos elementos maiores;

A base da recursão são as listas de tamanho zero ou um, que estão sempre ordenadas. O processo é finito, pois a cada iteração pelo menos um elemento é posto em sua posição final e não será mais manipulado na iteração seguinte.

Exemplo de Ordenação:

Vetor não ordenado:

3-6-4-5-1-7-2

Primeiro se descobre o meio vetor para começar a ordenar que será nosso pivô:

3-6-4-5-1-7-2

Depois pela regra de ordenação do Quicksort todos maiores que o pivô fica a direita e as menores a esquerda:

3-2-4-1-5-7-6

Depois o pivô é divido novamente mas agora só com a parte esquerda do para a ordenação

3-2-4-1

Depois disso é encontrado o pivô novamente:

3-2-4-1

Depois é repetido o mesmo processo todos os maiores ficam a direita e os menores a esquerda:

1-2-4-3

Depois de ordenado a primeira parte desse sublista é ordenado a segunda parte dessa sublista:

4-3

Depois que ordena essa parte ele vai para a outra parte a esquerda do vetor principal

5-7-6

Onde é encontrado o pivô:

5-7-6

E depois se ainda não estiver ordenado ele faz novamente:

5-6

Ficando no final

1-2-3-4-5-6-7

O Quicksort pode ser considerado um dos métodos, mais rápidos, quando temos valores do vetor é alta, mas quando a quantidade é menor de itens, ele é mais lento que o bubble sort.

---------------------------------------------------------------

Insertion Sort

Insertion sort, ou ordenação por inserção, é um simples algoritmo de ordenação, eficiente quando aplicado a um pequeno número de elementos. Em termos gerais, ele percorre um vetor de elementos da esquerda para a direita e à medida que avança vai deixando os elementos mais à esquerda ordenados. O algoritmo de inserção funciona da mesma maneira com que muitas pessoas ordenam cartas em um jogo de baralho como o pôquer.

Uma de suas características é que há menor número de trocas e comparações entre os algoritmos de ordenação quando o vetor está ordenado.

Por exemplo, considere que o primeiro elemento está ordenado (ou seja, na posição correta). A partir do segundo elemento, insere os demais elementos na posição apropriada entre aqueles já ordenados. O elemento é inserido na posição adequada movendo-se todos os elementos maiores para posição seguinte do vetor.

Mais interessante que o Bubble Sort para popular um vetor.

O elemento da posição 0 (valor 50) é comparado com o elemento da posição 1 (valor 30).

0

1

2

3

4

50

30

40

20