5.10. O Shell Sort¶

O shell sort, às vezes chamaado de “ordenação por incrementos diminutos”, melhora a ordenação por inserção ao quebrar a lista original em um número menor de sublistas, as quais são ordenadas usando a ordenação por inserção. A forma única como essas sublistas são escolhidas é a chave para o shell sort. Em vez de quebrar a lista em sublistas de itens contíguos, o shell sort usa um incremento i, às vezes chamado de gap, para criar uma sublista escolhendo todos os itens que estão afastados i itens uns dos outros.

Isso pode ser visto na Figura 6. Essa lista tem nove itens. Se usarmos um incremento de três, serão três sublistas, cada uma sendo submetida à ordenação por inserção. Depois de realizado esse processo, ficamos com a lista mostrada em Figura 7. Embora essa lista não esteja completamente ordenada, algo muito interessante aconteceu. Ao ordenarmos as sublistas, os itens ficaram mais próximos de onde eles pertencem de fato.

Figura 6: Shell Sort com Incremento de Três¶

Figura 7: Shell Sort depois de Ordenar Cada Sublista¶

A Figura 8 mostra uma ordenação por inserção final usando um incremento de um; em outras palavras, uma ordenação por inserção convencional. Observe que ao realizar as ordenações de sublistas anteriores, reduzimos agora o número total de operações de deslocalmento necessárias para colocar a lista na sua ordem final. Nesse caso, precisamos de apenas mais quatro deslocamentos para completar o processo.

Figura 8: ShellSort: Uma Inserção Final Com Incremento de 1¶

Figura 9: Sublistas Iniciais para um Shell Sort¶

Dissemos antes que a forma como os incrementos são escolhidos é uma característica única do shell sort. A função mostrada em ActiveCode 1 usa um conjunto de diferentes incrementos. Nesse caso, começamos com \(\frac {n}{2}\) sublistas. No passo seguinte, \(\frac {n}{4}\) sublistas são ordenadas. Eventualmente, uma única lista é ordenada com a ordenação por inserção básica. A Figure 9 mostra as primeiras sublistas para o nosso exemplo usando esse incremento.

A seguinte chamada da função shellSort mostra as listas parcialmente ordenadas depois de cada incremento, com a ordenação final sendo uma ordenação por inserção com incremento de um.

À primeira vista, você pode pensar que o shell sort não tem como ser melhor que a ordenação por inserção, já que ele a utiliza na lista toda como um último passo. Acontece que essa ordenação por inserção final não precisa realizar muitas comparações (ou deslocamentos), já que a lista foi pré-ordenada por ordenações por inserção incrementais anteriores, como descrito acima. Em outras palavras, cada passagem produz uma lista que está “mais ordenada” que a anterior. Isso faz com que a passagem final seja muito eficiente.

Embora uma análise geral do shell sort esteja além do escopo deste texto, podemos dizer que ele tende a ficar entre \(O(n)\) e \(O(n^{2})\), baseado no comportamento descrito acima. Para os incrementos mostrados em Listing 5, o desempenho é \(O(n^{2})\). Alterando o incremento, por exemplo, usando \(2^{k}-1\) (1, 3, 7, 15, 31, e assim por diante), o shell sort pode executar a \(O(n^{\frac {3}{2}})\).