Estruturas de Dados I
Algoritmos de Ordenação pt.2*
*Bom, esse sendo o primeiro post de Estruturas de Dados, vou fazer como disse que faria. Passar o resumo da matéria atual e pouco a pouco, fazer posts com resumos das matérias já vistas.
Hoje vi a segunda parte dos algoritmos de ordenação. Os métodos sofisticados ou algoritmos eficientes.
Os que vimos até agora foram:
- Shell Sort
- Merge Sort
- Quick Sort
Shell Sort é um algoritmo de ordenação sofisticado ou eficiente. Um algoritmo simples de entender, relativamente rápido de processar e fácil de implementar.
Seu nome vem de Donald Shell, que o criou em 1959 com a idéia de dividir um grande vetor de dados em vetores menores, ordenando-os e fazendo isso novamente para ter um único vetor praticamente ordenado e então trabalhar em cima dele, que seria mais prático e rápido. O algoritmo de Shell Sort em si mesmo não ordena nada, mas aumenta a eficiência de outros algoritmos de ordenação (como o da inserção e seleção, que serão vistos no próximo post de EDA), o que definitivamente faz sentido quando se entende como ele funciona.
Princípios básicos:
- O Shell Sort se baseia em uma variável chamada de incremento de sequência, ou incremento de shell, que é dado por h e ao decorrer da execução do algoritmo, é decrementada até 1.
- Utilizando o incremento de shell, o algoritmo compara elementos distantes em um vetor, em vez de comparar os adjacentes.
- No algoritmo, a ordenação é realizada em vários passos, usando uma sequência de valores do incremento de shell <h1, h2, h3…hN> onde começando por hN selecionamos apenas os valores que estão hN elementos distantes um do outro, então ordenamos esses elementos com algum algoritmo de ordenação simples como bolha, seleção ou inserção. Deste modo, apenas os elementos selecionados serão ordenados, os outros são todos ignorados.
Fig. 1 - Shell Sort com hN = 4
A Fig. 1 é um exemplo de como são selecionados os elementos do vetor usando a variável incremento de shell. Sempre selecionamos os elementos que estão hN elementos distantes um do outro. O segundo ciclo (h2) da figura mostra bem isso. Notem que os valores selecionados foram sempre de 2 em 2, pois h2 = 2.
- Como escolher valores para h?
Existem vários modos de escolher valores para h baseados em estudos de eficiência, você pode até escolher os valores que quiser, apesar de ser altamente não recomendável por questões de eficiência. O método de seleção de valores para h proposto por Donald Shell foi h = n/2 onde n é o número de elementos do vetor, mas já foi provado que sua eficiência é baixa. O que vimos hoje foi o da sequência de Donald Knuth, explicado como:
h = 3*h+1
E a sequência gerada: 1, 4, 13, 40, 121, 364, 1093, 3280…
Partindo de h = 1[*] precisamos do maior valor possível que seja menor que o número de elementos no vetor, então basta calcular:
h1 = 3*1+1 = 4
h2 = 3*4+1 = 13
h 3 = 3*13+1 = 40
etc.Para decrementar os valores de h até h=1 podemos usar a fórmula inversa:
h = (h-1)/3
…3280, 1093, 364, 121, 40, 13, 4, 1. - [*] O valor mais baixo possível de h sempre deve ser 1, para que seja possível comparar elementos adjacentes. Veja a Fig. 1 novamente e note que o último passo da ordenação é h = 1, que faz a comparação e ordenação dos elementos adjacentes
- Exemplificando:
Se ainda não deu pra entender bem, veja assim:
hN= valor mais alto na fórmula que seja menor que o número de elementos no vetor.
Por ex: Para um vetor de 20 elementos, hN = 13 pois 3*13+1 = 40 que é maior que 20.Ou ainda, em C:/* tamanho é o número de elementos no nosso * vetor fictício */ int tamanho = 20, h = 1; while(h < tamanho) { h = 3*h+1; } /* ao final desse laço, h valerá 13, já que como * vimos no exemplo acima, o próximo resultado da * equação seria 40, que não iria satisfazer a * condição h < tamanho. */
void shellSort(int *vet, int tamanho) {
//Cria variáveis auxiliares
int i , j , valor;
//Cria a variável h que será usada para selecionar
//os grupos de valores do vetor
int h = 1;
do {
//Aqui como usamos do/while, pegamos o valor 40
//como último valor aceito, não 13.
//Vamos entender o porquê disso mais pra baixo.
h = 3*h+1;
} while(h < tamanho);
do {
//Aqui dividimos o incremento de shell para montar
//os grupos de valores que serão ordenados. Depois de
//todos os valores de h serem ordenados, dividimos h
//novamente e ordenamos pares mais próximos, até que
//h = 1 e os pares adjacentes sejam ordenados.
h /= 3;
//É aqui que a comparação e a ordenação acontecem:
for(i = h; i < tamanho; i++) {
//Valor vai receber o h-ésimo elemento do vetor
valor = vet[i];
//j vai ser o índice do elemento que será comparado
//com valor. Ex: Na primeira iteração do laço:
//Se h = 13 e i = 13 então j = 0 pois j = 13 - 13.
//Então vet[13] será comparado com vet[0], então com
//vet[1] e etc. até i < tamanho e h será dividido
//novamente para selecionar um novo grupo de elementos
//em uma distância menor e os ordenará.
j = i - h;
//Aqui é feita a troca de lugares entre os elementos,
//Seguindo o nosso exemplo, se vet[13] < vet[0],
//então vet[13] recebe o valor de vet[0].
while (j >= 0 && valor < vet[j]) {
vet[j + h] = vet[j]; //vet[13] recebe vet[0]
j -= h; //Aqui se j = 0 e h = 13, j = -13.
}
//Para que aqui, vet[0] receba o valor de vet[13]
vet[j + h] = valor;
}
//E a validação de h > 1 é feita para que quando
//a última ordenação h1 for feita, o programa termine.
} while( h > 1);
}
Fig. 2 - Shell Sort em sequência 8-4-2-1
Caderno Geek 