Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.
Em 1959, o cientista Donald Shell descobriu algo que mudaria para sempre o mundo. Nesta data, foi descoberto o algoritmo de ordenação conhecido como ShellSort. Ele tem como base um outro algoritmo já visto aqui no blog, o InsertionSort. Clique aqui para dar uma olhada, caso você não conheça.
A ordenação de Shell é boa para vetores de tamanho médio, talvez com até alguns milhares de itens, dependendo da particular implementação. Não é tão rápido quanto QuickSort (veremos aqui um dia) e outras ordenações O(N*logN), portanto, não é ótima para grandes massas de dados. Contudo, é muito mais rápida que as ordenações O(N²) como o SelectionSort (também não vimos ainda) e InsertionSort. O desempenho no pior caso não é muito pior que o do médio caso. Sua implementação é fácil, tornando seu código curto e simples. (Lafore R.)
O algoritmo citado como base do algoritmo ShellShort possui um problema: cópias demais. Imagine uma situação, onde em um conjunto um pequeno item está bem à direita, onde os itens grandes devem estar. Para mover esse pequeno item para seu devido lugar à esquerda, todos os itens intermediários, ou seja, os do meio desse intervalo, tem que ser deslocados em um espaço para a direita. Esse passo consome cerca de N cópias, apenas para um item. Nem todos os itens tem que ser movidos em N espaço completos, mas o item médio tem que ser movido em N/2 espaços, que tem N*N/2 deslocamentos para um total de N²/2 cópias. Logo, o desempenho dessa ordenação é O(N²) e isto é um grande problema. (Lafore R.)
E se existisse alguma forma de mover os itens menores para a esquerda sem mover os maiores para à direita ? Se sim, seria tal solução possível ?
Sim, é possível e é aqui onde a ordenação Shell ganha espaço. Seu segredo não é ordenar de forma direta como a ordenação Bolha faz, mas sim deixar o vetor quase ordenado para que a ordenação por inserção termine o trabalho. Mas como ele faz isso ?
Para que ele possa criar um vetor quase ordenado, ele precisa criar antes sub-vetores ordenados, os quais são independentes entre si. Tais são gerados através do uso de espaçamento entre elementos, também conhecido como incremento, e é normalmente conhecido pela letra h. Neste momento nossa cabeça com certeza se enche com mais dúvidas, pois ainda não temos idéia de como é esse espaçamento e como ele é gerado.
Vamos entrar depois nos detalhes de como o espaçamento é gerado. Por enquanto, vamos definir que nosso h é 4, representado no passo 1. Note que no passo adiante, passo 2, três elementos são marcados pela cor vermelha no vetor e a distância entre eles é justamente o valor de h. Após marcados, o sub-conjunto ou sub-vetor é criado, e já pode ser ordenado através da troca de lugar de seus elementos, assim o passo 3 é representado. Este processo de marcação, criação do sub-vetor e ordenação se repete por todo o vetor, de tal forma que após o primeiro sub-conjunto ter sido finalizado todas as posições anteriormente marcados são acrescidas de uma casa à direita. Tal processo termina quando não existem mais elementos no vetor para formar sub-conjuntos, e assim, ganha vida os passos 4, 5, 6, 7 e 8.
Note que alguns sub-vetores não precisaram sofrer ordenação visto que, pela ordem natural de seus elementos eles já estavam ordenados entre si, e que alguns sub-conjuntos somente possuem dois elementos. Isto acontece pelo fato de que se contarmos quatro casas iniciando do último elemento marcado iremos ultrapassar o tamanho do vetor, logo se referindo a uma posição que não existe.
Contudo, e se o nosso vetor aumentasse de tamanho ? Nosso h continuaria sendo 4 ? E antes de pensarmos nisso, quem sugeriu este valor para esta variável ? Foi achismo ou fundamentado ? Bolacha ou biscoito ?
Se você acha que o valor 4 foi atribuído para h por um simples chute meu, não queria te dizer mas você está enganado. Tal foi gerado através da seguinte fórmula recursiva: h = 3*h + 1, onde inicialmente h=1 e, é conhecida como sequência de intervalo ou lacuna. A particular sequência mostrada é atribuída a Knuth (Lafore R.). É importante ressaltar que existem outras abordagens para geração da sequência de intervalos, mas nesta implementação do algoritmo de ordenação Shell utilizaremos essa.
No algoritmo de ordenação, a fórmula que gera a sequência é usada primeiro em um laço curto para descobrir o intervalo inicial. O valor 1 é usado para o primeiro valor de h e a fórmula já apresentada é aplicada para gerar a sequência 1,4,13,40,121,364, etc. Esse processo termina quando o intervalo se torna maior que o vetor. Para um vetor com 1000 elementos, o sétimo número da sequência, 1093, é grande demais. Assim, começamos o processo de ordenação com o sexto número maior, criando uma ordenação em 364. Então, a cada vez no laço externo da rotina de ordenação, reduzimos o intervalo usando o inverso da fórmula dada anteriormente: h = (h-1) / 3. (Lafore R.)
Essa fórmula inversa gera a sequência inversa 364,121,40,13,4,1. Começando com 364, cada um desses números é usado para a ordenação do vetor. Quando o vetor tiver sido ordenado em 1, o algoritmo terá terminado. (Lafore R.)
Antes de analisarmos o algoritmo uma última pergunta ainda não foi respondida. Porque a ordenação Shell é muito mais rápida que a ordenação por inserção na qual ele é baseada ? Quando h é grande, o número de itens por passagens (trocas) é pequeno e os itens se movem em longas distâncias (como visto acima). Isto é muito eficiente. Quando h fica menor, o número de itens por passagem aumenta, mas os itens já estão mais próximos de suas posições ordenadas finais, o que é mais eficiente para a ordenação por inserção. É a combinação dessas tendências que torna a ordenação Shell tão eficiente.(Lafore R.)
Eis nossa implementação em Java.
Alguns pontos que valem a pena dar atenção.
Linha 4 até 6: Cria as partições baseado na sequência de intervalos de Knuth.
Linha 13 até 17: Algoritmo Insertion Sort já visto outrora.
Linha 13: O h-1 representa o fim do intervalo, e inner-h o valor dentro do intervalo.
Linha 15: Decrementa para percorrer outros intervalos.
Linha 19: Isto é feito para diminuir o tamanho das partições até chegar a 1.
Um mistério reside em torno da eficiência dessa ordenação, pois somente em casos especiais é possível averiguar tal. Com base em experimentos, existem várias estimativas que variam de O(N3/2)a O(N7/6), onde Nx/y representa a raiz y de N elevado a X, ou y√Nx . Assim se N for 100, N3/2 será a raiz quadrada de 1003, que é 1000. (Lafore R.)
E assim adicionamos mais um algoritmo para o nosso canivete de algoritmos de ordenação. Se você não sabe do que estou falando, dê uma clicada aqui e fique por dentro.
Para baixar o projeto utilize um dos links abaixo.
Link do Dropbox: https://www.dropbox.com/sh/8d5em1y1j9upke0/AAAvLf_sPeS4HRSBPH6YNHfra?dl=0
Link do GoogleDrive: https://drive.google.com/folderview?id=0BzDmhBY6luU6aThjTmx3OXNlUnM&usp=sharing
Dúvidas !? Sugestões ?! Críticas ou elogios ?!
Referências
Lafore R.; ESTRUTURAS DE DADOS E ALGORITMOS EM JAVA; 2004
Figuras:
Figura 1 - http://goodnewsmag.org/wp-content/uploads/2015/11/shell2.jpg
Figura 2 - Criação própria
Leia Mais ››
Em 1959, o cientista Donald Shell descobriu algo que mudaria para sempre o mundo. Nesta data, foi descoberto o algoritmo de ordenação conhecido como ShellSort. Ele tem como base um outro algoritmo já visto aqui no blog, o InsertionSort. Clique aqui para dar uma olhada, caso você não conheça.
 |
| Figura 1 - Donald L. Shell |
O algoritmo citado como base do algoritmo ShellShort possui um problema: cópias demais. Imagine uma situação, onde em um conjunto um pequeno item está bem à direita, onde os itens grandes devem estar. Para mover esse pequeno item para seu devido lugar à esquerda, todos os itens intermediários, ou seja, os do meio desse intervalo, tem que ser deslocados em um espaço para a direita. Esse passo consome cerca de N cópias, apenas para um item. Nem todos os itens tem que ser movidos em N espaço completos, mas o item médio tem que ser movido em N/2 espaços, que tem N*N/2 deslocamentos para um total de N²/2 cópias. Logo, o desempenho dessa ordenação é O(N²) e isto é um grande problema. (Lafore R.)
E se existisse alguma forma de mover os itens menores para a esquerda sem mover os maiores para à direita ? Se sim, seria tal solução possível ?
Sim, é possível e é aqui onde a ordenação Shell ganha espaço. Seu segredo não é ordenar de forma direta como a ordenação Bolha faz, mas sim deixar o vetor quase ordenado para que a ordenação por inserção termine o trabalho. Mas como ele faz isso ?
Para que ele possa criar um vetor quase ordenado, ele precisa criar antes sub-vetores ordenados, os quais são independentes entre si. Tais são gerados através do uso de espaçamento entre elementos, também conhecido como incremento, e é normalmente conhecido pela letra h. Neste momento nossa cabeça com certeza se enche com mais dúvidas, pois ainda não temos idéia de como é esse espaçamento e como ele é gerado.
 |
| Figura 2 - Criação dos sub-vetores através do uso da técnica de espaçamento |
Note que alguns sub-vetores não precisaram sofrer ordenação visto que, pela ordem natural de seus elementos eles já estavam ordenados entre si, e que alguns sub-conjuntos somente possuem dois elementos. Isto acontece pelo fato de que se contarmos quatro casas iniciando do último elemento marcado iremos ultrapassar o tamanho do vetor, logo se referindo a uma posição que não existe.
Contudo, e se o nosso vetor aumentasse de tamanho ? Nosso h continuaria sendo 4 ? E antes de pensarmos nisso, quem sugeriu este valor para esta variável ? Foi achismo ou fundamentado ? Bolacha ou biscoito ?
Se você acha que o valor 4 foi atribuído para h por um simples chute meu, não queria te dizer mas você está enganado. Tal foi gerado através da seguinte fórmula recursiva: h = 3*h + 1, onde inicialmente h=1 e, é conhecida como sequência de intervalo ou lacuna. A particular sequência mostrada é atribuída a Knuth (Lafore R.). É importante ressaltar que existem outras abordagens para geração da sequência de intervalos, mas nesta implementação do algoritmo de ordenação Shell utilizaremos essa.
No algoritmo de ordenação, a fórmula que gera a sequência é usada primeiro em um laço curto para descobrir o intervalo inicial. O valor 1 é usado para o primeiro valor de h e a fórmula já apresentada é aplicada para gerar a sequência 1,4,13,40,121,364, etc. Esse processo termina quando o intervalo se torna maior que o vetor. Para um vetor com 1000 elementos, o sétimo número da sequência, 1093, é grande demais. Assim, começamos o processo de ordenação com o sexto número maior, criando uma ordenação em 364. Então, a cada vez no laço externo da rotina de ordenação, reduzimos o intervalo usando o inverso da fórmula dada anteriormente: h = (h-1) / 3. (Lafore R.)
Essa fórmula inversa gera a sequência inversa 364,121,40,13,4,1. Começando com 364, cada um desses números é usado para a ordenação do vetor. Quando o vetor tiver sido ordenado em 1, o algoritmo terá terminado. (Lafore R.)
Antes de analisarmos o algoritmo uma última pergunta ainda não foi respondida. Porque a ordenação Shell é muito mais rápida que a ordenação por inserção na qual ele é baseada ? Quando h é grande, o número de itens por passagens (trocas) é pequeno e os itens se movem em longas distâncias (como visto acima). Isto é muito eficiente. Quando h fica menor, o número de itens por passagem aumenta, mas os itens já estão mais próximos de suas posições ordenadas finais, o que é mais eficiente para a ordenação por inserção. É a combinação dessas tendências que torna a ordenação Shell tão eficiente.(Lafore R.)
Eis nossa implementação em Java.
1: private void shellSort(int[] array){
2: int begInterv, endInterv, h=1, temp;
3:
4: while(h<=nElems/3){
5: h = h*3 +1;
6: }
7:
8: while(h>0){
9: for (endInterv = h; endInterv < array.length; endInterv++) {
10: temp = array[endInterv];
11: begInterv = endInterv;
12:
13: while (begInterv > h-1 && array[begInterv-h] >= temp) {
14: array[begInterv] = array[begInterv-h];
15: begInterv -= h;
16: }
17: array[begInterv] = temp;
18: }
19: h = (h-1)/3;
20: }
21: }
Alguns pontos que valem a pena dar atenção.
Linha 4 até 6: Cria as partições baseado na sequência de intervalos de Knuth.
Linha 13 até 17: Algoritmo Insertion Sort já visto outrora.
Linha 13: O h-1 representa o fim do intervalo, e inner-h o valor dentro do intervalo.
Linha 15: Decrementa para percorrer outros intervalos.
Linha 19: Isto é feito para diminuir o tamanho das partições até chegar a 1.
Um mistério reside em torno da eficiência dessa ordenação, pois somente em casos especiais é possível averiguar tal. Com base em experimentos, existem várias estimativas que variam de O(N3/2)a O(N7/6), onde Nx/y representa a raiz y de N elevado a X, ou y√Nx . Assim se N for 100, N3/2 será a raiz quadrada de 1003, que é 1000. (Lafore R.)
E assim adicionamos mais um algoritmo para o nosso canivete de algoritmos de ordenação. Se você não sabe do que estou falando, dê uma clicada aqui e fique por dentro.
Para baixar o projeto utilize um dos links abaixo.
Link do Dropbox: https://www.dropbox.com/sh/8d5em1y1j9upke0/AAAvLf_sPeS4HRSBPH6YNHfra?dl=0
Link do GoogleDrive: https://drive.google.com/folderview?id=0BzDmhBY6luU6aThjTmx3OXNlUnM&usp=sharing
Dúvidas !? Sugestões ?! Críticas ou elogios ?!
Deixe aí nos comentários, me mande um e-mail ou, na nossa página do facebook.
E-mail: precisoestudarsempre@gmail.com
Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA
Referências
Lafore R.; ESTRUTURAS DE DADOS E ALGORITMOS EM JAVA; 2004
Figuras:
Figura 1 - http://goodnewsmag.org/wp-content/uploads/2015/11/shell2.jpg
Figura 2 - Criação própria
