Suponha uma lista ordenada
e capacidade
. Inicialmente,
.
a) Escreva o algoritmo para inserir o elemento 20 na lista ordenada
de forma que a lista continue ordenada. Explique cada passo e descreva o novo estado da lista.
a) Escreva o algoritmo para inserir o elemento 20 na lista ordenada
Passo 1
Beleza, vamos lá! A questão pede para a gente inserir o número 20 na lista ordenada
sem bagunçar a ordem. A gente vai precisar entender como funciona uma lista ordenada e como inserir um elemento mantendo essa ordem. Basicamente, vamos seguir um algoritmo passo a passo para achar onde o 20 deve entrar na lista.
Passo 2
Primeiro, vamos lembrar o que é uma lista ordenada. Uma lista ordenada é uma sequência de elementos dispostos em ordem crescente ou decrescente. No nosso caso, está em ordem crescente. Para inserir um novo elemento mantendo essa ordem, a gente precisa encontrar a posição correta onde esse elemento deve ficar.
Passo 3
Vamos identificar onde o número 20 se encaixa na nossa lista
. Para isso, comparamos o 20 com os elementos da lista do começo ao fim até encontrar o primeiro número maior que 20.
- 5 < 20? Sim.
- 12 < 20? Sim.
- 15 < 20? Sim.
- 18 < 20? Sim.
- 22 > 20? Ah, chegou o lugar!
Isso significa que o 20 deve ser inserido antes do 22.
Passo 4
Agora, vamos escrever o algoritmo para fazer isso. O algoritmo basicamente percorre a lista até encontrar onde o novo elemento deve ser inserido. Aqui está uma versão simples em pseudocódigo:
- Iniciar na primeira posição da lista.
- Comparar o novo elemento (20) com o elemento atual da lista.
- Se o 20 for maior que o elemento atual, passar para o próximo.
- Se não, inserir o 20 nessa posição.
- Aumentar o contador de elementos da lista.
Passo 5
Aplicando esse algoritmo na nossa lista:
- Começamos com n = 7 elementos.
- Comparamos 20 com 5 → 20 > 5 → seguimos.
- Comparamos 20 com 12 → 20 > 12 → seguimos.
- Comparamos 20 com 15 → 20 > 15 → seguimos.
- Comparamos 20 com 18 → 20 > 18 → seguimos.
- Comparamos 20 com 22 → 20 < 22 → inserimos o 20 aqui.
Passo 6
Após inserir o 20 antes do 22, a nova lista fica assim:
E o contador de elementos agora é
.
Resposta
Depois de seguir o algoritmo, o elemento 20 foi inserido na posição correta, e a nova lista ordenada é
com
elementos.