Considere a seguinte sequência de chaves do vetor [25, 18, 30, 5, 10, 12,
. Qual será o conteúdo da lista após todas as trocas completas para um h=5 e h=3 e por fim h=1, nessa ordem, utilizando o Algoritmo do ShellSort?
Passo 1
Beleza, vamos resolver esse exercício que pede para aplicar o algoritmo ShellSort na sequência de chaves [25, 18, 30, 5, 10, 12, 3, 22, 15, 7, 9] utilizando os valores de intervalo $ h = 5 $, depois $ h = 3 $ e por fim $ h = 1 $. O ShellSort é um método de ordenação que melhora o Insertion Sort ao permitir a troca de elementos que estão distantes, reduzindo o tempo de ordenação geral.
Passo 2
Primeiro, vamos entender como funciona o ShellSort. Ele ordena os elementos em vários passos usando diferentes valores de intervalo $ h $. Em cada passo, os elementos são comparados e trocados se necessário, com uma distância $ h $ entre eles. Começamos com um intervalo maior e vamos diminuindo até chegar a 1. Quando $ h = 1 $, é como um Insertion Sort comum.
Passo 3
Vamos começar com $ h = 5 $. Isso significa que vamos comparar elementos que estão 5 posições apartadas na lista. Se o elemento anterior for maior que o seguinte, trocamos.
Nossa lista inicial é:
Vamos realizar as comparações e trocas com $ h = 5 $:
- Comparar 25 e 12 (índices 0 e 5). Como 25 > 12, trocamos:
2. Comparar 18 e 3 (índices 1 e 6). Como 18 > 3, trocamos:
- Comparar 30 e 22 (índices 2 e 7). Como 30 > 22, trocamos:
4. Comparar 5 e 15 (índices 3 e 8). Como 5 < 15, não trocamos.
5. Comparar 10 e 7 (índices 4 e 9). Como 10 > 7, trocamos:
- Comparar 25 e 9 (índices 5 e 10). Como 25 > 9, trocamos:
Após todas as trocas com $ h = 5 $, a lista fica:
Passo 4
Agora, vamos diminuir o intervalo para $ h = 3 $ e repetir o processo. Com $ h = 3 $, comparamos elementos que estão 3 posições apartadas.
Lista atual:
Vamos realizar as comparações e trocas com $ h = 3 $:
- Comparar 12 e 5 (índices 0 e 3). Como 12 > 5, trocamos:
2. Comparar 3 e 7 (índices 1 e 4). Como 3 < 7, não trocamos.
3. Comparar 22 e 9 (índices 2 e 5). Como 22 > 9, trocamos:
- Comparar 12 e 18 (índices 3 e 6). Como 12 < 18, não trocamos.
- Comparar 7 e 30 (índices 4 e 7). Como 7 < 30, não trocamos.
- Comparar 22 e 15 (índices 5 e 8). Como 22 > 15, trocamos:
7. Comparar 18 e 10 (índices 6 e 9). Como 18 > 10, trocamos:
- Comparar 30 e 25 (índices 7 e 10). Como 30 > 25, trocamos:
Após todas as trocas com $ h = 3 $, a lista fica:
Passo 5
Por fim, vamos usar $ h = 1 $, que é como um Insertion Sort comum. Vamos percorrer a lista e inserir cada elemento na posição correta em relação aos anteriores.
Lista atual:
Vamos ordenar passo a passo:
- Comparar 5 e 3: Como 5 > 3, trocamos:
2. 5 e 9: 5 < 9, sem troca.
3. 9 e 12: 9 < 12, sem troca.
4. 12 e 7: 12 > 7, trocamos:
- Agora, comparamos 9 e 7: 9 > 7, trocamos:
5. 12 e 15: 12 < 15, sem troca.
6. 15 e 10: 15 > 10, trocamos:
- Agora, comparamos 12 e 10: 12 > 10, trocamos:
7. 15 e 25: 15 < 25, sem troca.
8. 25 e 22: 25 > 22, trocamos:
- Agora, comparamos 15 e 22: 15 < 22, sem troca.
- 25 e 18: 25 > 18, trocamos:
- Agora, comparamos 22 e 18: 22 > 18, trocamos:
- 25 e 30: 25 < 30, sem troca.
Após todas as trocas com $ h = 1 $, a lista fica ordenada:
Resposta
Após todas as trocas com $ h = 5 $, $ h = 3 $ e $ h = 1 $, a lista ordenada fica: