Shellsort
Leia isso em outros idiomas: English.
Shellsort, também conhecido como Shell sort ou método de Shell, é uma classificação de comparação in-loco. Pode ser visto tanto como um generalização da ordenação por troca (bubble sort) ou ordenação por inserção (ordenação por inserção). O método começa classificando pares de elementos distantes um do outro, então progressivamente reduzindo a distância entre os elementos a serem comparados. Iniciando com elementos distantes, pode mover alguns fora do lugar elementos em posição mais rápido do que um simples vizinho mais próximo intercâmbio
Como o Shellsort funciona?
Para nosso exemplo e facilidade de compreensão, tomamos o intervalo
de 4. Faça uma sub-lista virtual de todos os valores localizados no
intervalo de 4 posições. Aqui esses valores são
{35, 14}, {33, 19}, {42, 27} e {10, 44}
Comparamos valores em cada sublista e os trocamos (se necessário) na matriz original. Após esta etapa, o novo array deve parece com isso
Então, pegamos o intervalo de 2 e essa lacuna gera duas sub-listas
- {14, 27, 35, 42}, {19, 10, 33, 44}
Comparamos e trocamos os valores, se necessário, no array original. Após esta etapa, a matriz deve ficar assim
OBS: Na imagem abaixo há um erro de digitação e a matriz de resultados deve ser
[14, 10, 27, 19, 35, 33, 42, 44].
Finalmente, ordenamos o resto do array usando o intervalo de valor 1. A classificação de shell usa a classificação por inserção para classificar a matriz.
Complexidade
| Nome | Melhor | Média | Pior | Memória | Estável | Comentários |
|---|---|---|---|---|---|---|
| Shell sort | n log(n) | depends on gap sequence | n (log(n))2 | 1 | Não |