Implementation (Part 2)
Lição 6 de 9 do curso Insertion Sort - Série DSA da Coddy.
Cenário: Ordenando [5, 2, 9, 1, 5]
Passo 1: Estado Inicial
- Array Original: [5, 2, 9, 1, 5]
- Imagine isso como nossa mão de cartas (ou um array de números).
Passo 2: Primeiro Elemento (i=1, key=2)
- Começamos com a segunda carta (elemento): key = 2.
- Compare 2 com 5 (o único elemento ordenado até agora).
- Como 2 é menor, deslocamos o 5 para a direita e inserimos o 2 em seu lugar.
- Array Atualizado: [2, 5, 9, 1, 5]
Passo 3: Segundo Elemento (i=2, key=9)
- Movemos para a próxima carta: key = 9.
- Compare 9 com 5.
- Como 9 é maior, não há necessidade de deslocamento.
- Array Atualizado: [2, 5, 9, 1, 5] (sem alterações)
Passo 4: Terceiro Elemento (i=3, key=1)
- Movemos para a próxima carta: key = 1.
- Compare 1 com 9, depois com 5.
- Desloque 9 e 5 para a direita, abrindo espaço para o 1.
- Array Atualizado: [1, 2, 5, 9, 5]
Passo 5: Quarto Elemento (i=4, key=5)
- Movemos para a próxima carta: key = 5.
- Compare 5 com 9.
- Como 5 é menor, não há necessidade de deslocamento.
- Array Atualizado: [1, 2, 5, 9, 5] (sem alterações)
Passo 6: Quinto Elemento (i=5, key=5)
- Movemos para a última carta: key = 5.
- Compare 5 com 9.
- Como 5 é menor, não há necessidade de deslocamento.
- Array Atualizado: [1, 2, 5, 5, 9]
Resultado Final:
- Array Ordenado: [1, 2, 5, 5, 9]
Em cada passo, estamos escolhendo uma carta (elemento), comparando-a com as que já estão ordenadas e colocando-a no lugar certo, deslocando as outras se necessário. Repetimos esse processo até que todo o array esteja ordenado.
Desafio
FácilAgora, implemente o loop interno, que realiza a ordenação para cada elemento.
Complete a ordenação dentro da função insertionSort.
A função também deve imprimir os elementos do array ao final, um por um, com uma nova linha entre eles.
Use as lições anteriores e a dica como referência :)
Experimente você mesmo
def insertionSort(arr):
for i in range(1, len(arr)):
key = arr[i]
print(key)
Todas as lições de Insertion Sort - Série DSA
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity