Scribd
Carregar
3 visualizações2 páginas

Shell Sort Pedro

O Shell Sort é um algoritmo de ordenação que melhora o Insertion Sort ao usar um intervalo chamado gap, que diminui até chegar a 1. Sua complexidade varia de O(n log n) no melhor caso a O(n^2) no pior caso, e é um algoritmo in-place com complexidade de espaço O(1). Embora eficiente para conjuntos de dados moderados, o Shell Sort não é estável, pois pode alterar a ordem relativa de elementos iguais.

Enviado por

d947481865
Direitos autorais
© All Rights Reserved
Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.
Formatos disponíveis
Baixe no formato DOCX, PDF, TXT ou leia on-line no Scribd
3 visualizações2 páginas

Shell Sort Pedro

O Shell Sort é um algoritmo de ordenação que melhora o Insertion Sort ao usar um intervalo chamado gap, que diminui até chegar a 1. Sua complexidade varia de O(n log n) no melhor caso a O(n^2) no pior caso, e é um algoritmo in-place com complexidade de espaço O(1). Embora eficiente para conjuntos de dados moderados, o Shell Sort não é estável, pois pode alterar a ordem relativa de elementos iguais.

Enviado por

d947481865
Direitos autorais
© All Rights Reserved
Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.
Formatos disponíveis
Baixe no formato DOCX, PDF, TXT ou leia on-line no Scribd

Shell Sort

Introdução
O Shell Sort é um algoritmo de ordenação que funciona como uma melhoria do Insertion
Sort. A ideia principal é comparar elementos distantes entre si, usando um intervalo
chamado gap, que vai diminuindo ao longo do processo até chegar a 1.

Modo de Funcionamento
1. Define-se um gap inicial (geralmente n/2)
2. Divide-se o vetor em grupos
3. Aplica-se Insertion Sort em cada grupo
4. Reduz-se o gap
5. Repete-se até gap = 1

Complexidade
Melhor caso: O(n log n)
Caso médio: O(n (log n)^2)
Pior caso: O(n^2)
Espaço: O(1)
O desempenho depende muito da sequência de gaps escolhida.

Estabilidade
O Shell Sort não é estável, pois pode alterar a ordem relativa de elementos iguais.

Espaço
O Shell Sort é um algoritmo in-place, com complexidade de espaço O(1), pois não
utiliza estruturas auxiliares significativas.

Exemplo ilustrado:

Vetor inicial: [9 8 3 7 5 6 4 1]

Gap = 4: (9,5) (8,6) (3,4) (7,1)


Após ordenação parcial: (5,9) (6,8) (3,4) (1,7)

Conclusão
O Shell Sort é um algoritmo simples e eficiente para conjuntos de dados moderados,
melhorando o desempenho do Insertion Sort ao reduzir deslocamentos.

Você também pode gostar