Considere a seguinte sequência de chaves do vetor [25, 18, 30, 5, 10, 12, 3,22,15,7,9]. 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 é:
h = 5
Vamos realizar as comparações e trocas com $ h = 5 $:
  1. Comparar 25 e 12 (índices 0 e 5). Como 25 > 12, trocamos:
[25, 18, 30, 5, 10, 12, 3, 22, 15, 7, 9]
2. Comparar 18 e 3 (índices 1 e 6). Como 18 > 3, trocamos:
h = 5
  1. Comparar 30 e 22 (índices 2 e 7). Como 30 > 22, trocamos:
[12, 18, 30, 5, 10, 25, 3, 22, 15, 7, 9]
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:
[12, 3, 30, 5, 10, 25, 18, 22, 15, 7, 9]
  1. Comparar 25 e 9 (índices 5 e 10). Como 25 > 9, trocamos:
[12, 3, 22, 5, 10, 25, 18, 30, 15, 7, 9]
Após todas as trocas com $ h = 5 $, a lista fica:
[12, 3, 22, 5, 7, 25, 18, 30, 15, 10, 9]

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:
h = 3
Vamos realizar as comparações e trocas com $ h = 3 $:
  1. Comparar 12 e 5 (índices 0 e 3). Como 12 > 5, trocamos:
h = 3
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:
[12, 3, 22, 5, 7, 9, 18, 30, 15, 10, 25]
  1. Comparar 12 e 18 (índices 3 e 6). Como 12 < 18, não trocamos.
  2. Comparar 7 e 30 (índices 4 e 7). Como 7 < 30, não trocamos.
  3. Comparar 22 e 15 (índices 5 e 8). Como 22 > 15, trocamos:
h = 3
7. Comparar 18 e 10 (índices 6 e 9). Como 18 > 10, trocamos:
[5, 3, 22, 12, 7, 9, 18, 30, 15, 10, 25]
  1. Comparar 30 e 25 (índices 7 e 10). Como 30 > 25, trocamos:
[5, 3, 9, 12, 7, 22, 18, 30, 15, 10, 25]
Após todas as trocas com $ h = 3 $, a lista fica:
[5, 3, 9, 12, 7, 15, 18, 30, 22, 10, 25]

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:
h = 1
Vamos ordenar passo a passo:
  1. Comparar 5 e 3: Como 5 > 3, trocamos:
[5, 3, 9, 12, 7, 15, 10, 25, 22, 18, 30]
2. 5 e 9: 5 < 9, sem troca.
3. 9 e 12: 9 < 12, sem troca.
4. 12 e 7: 12 > 7, trocamos:
[3, 5, 9, 12, 7, 15, 10, 25, 22, 18, 30]
  • Agora, comparamos 9 e 7: 9 > 7, trocamos:
[3, 5, 9, 7, 12, 15, 10, 25, 22, 18, 30]
5. 12 e 15: 12 < 15, sem troca.
6. 15 e 10: 15 > 10, trocamos:
[3, 5, 7, 9, 12, 15, 10, 25, 22, 18, 30]
  • Agora, comparamos 12 e 10: 12 > 10, trocamos:
[3, 5, 7, 9, 12, 10, 15, 25, 22, 18, 30]
7. 15 e 25: 15 < 25, sem troca.
8. 25 e 22: 25 > 22, trocamos:
[3, 5, 7, 9, 10, 12, 15, 25, 22, 18, 30]
  • Agora, comparamos 15 e 22: 15 < 22, sem troca.
  1. 25 e 18: 25 > 18, trocamos:
[3, 5, 7, 9, 10, 12, 15, 22, 25, 18, 30]
- Agora, comparamos 22 e 18: 22 > 18, trocamos:
[3, 5, 7, 9, 10, 12, 15, 22, 18, 25, 30]
  1. 25 e 30: 25 < 30, sem troca.
Após todas as trocas com $ h = 1 $, a lista fica ordenada:
[3, 5, 7, 9, 10, 12, 15, 18, 22, 25, 30]

Resposta

Após todas as trocas com $ h = 5 $, $ h = 3 $ e $ h = 1 $, a lista ordenada fica:
h = 5

Exercícios relacionados