Insertion Sort (Ordenação por Inserção)
O Insertion Sort (Ordenação por Inserção) é muito semelhante ao algoritmo Selection Sort. É bastante intuitivo e mantém a parte esquerda do array ordenada enquanto avança passo a passo até chegar ao fim do array.
Mais concretamente, no algoritmo de Insertion Sort, começamos a partir do elemento mais à esquerda e movemo-nos progressivamente para a direita. Assim que encontramos um elemento mais pequeno do que os que estão à sua esquerda, procedemos ao deslocamento de todos esses elementos (um a um) para a direita, abrindo espaço para inserir o valor atual na posição correta. Por exemplo, se tivermos o array
[0, 2, 4, 1, 10, 8] e estivermos a analisar o valor 1, primeiro deslocamos o 4 e depois o 2 para a direita, posicionando o 1 entre o 0 e o 2. O resultado é [0, 1, 2, 4, 10, 8]. De seguida, passamos ao elemento 10: não fazemos nada, pois é maior do que todos os elementos à esquerda. Por fim, analisamos o 8, deslocamos o 10 para a direita e inserimos o 8 entre o 4 e o 10.a = [...]
for i in range(1, len(a)): # começar a partir do segundo elemento
while i > 0 and a[i] < a[i - 1]: # enquanto o elemento atual for menor
a[i - 1], a[i] = a[i], a[i - 1] # trocar o elemento atual com o anterior
i -= 1 # manter o controlo do índice do elemento atual
print(a)O Insertion Sort insere o elemento atual na sua posição correta no array já processado. No pior dos cenários, se os elementos do array estiverem em ordem decrescente, será preciso deslocar todos os elementos que vêm antes de
i para posicionar corretamente o elemento atual, resultando num total de operações.Vamos simular o algoritmo em vários arrays:
[4, 1, -1, 0, 2, 8]
i = 1⇒ troca ⇒[1, 4, -1, 0, 2, 8]
i = 2⇒ troca ⇒[1, -1, 4, 0, 2, 8]⇒ troca ⇒[-1, 1, 4, 0, 2, 8]
i = 3⇒ não fazer nada
i = 4⇒ troca ⇒[-1, 1, 0, 4, 2, 8]⇒ troca ⇒[-1, 0, 1, 2, 4, 8]
i = 5⇒ não fazer nada
- imprime
[-1, 0, 1, 2, 4, 8]
[10, 5, 1, -7]
i = 1⇒ troca ⇒[5, 10, 1, -7]
i = 2⇒ troca ⇒[5, 1, 10, -7]⇒ troca ⇒[1, 5, 10, -7]
i = 3⇒ troca ⇒[1, 5, -7, 10]⇒ troca ⇒[1, -7, 5, 10]⇒ troca ⇒[-7, 1, 5, 10]
[1, 2, 3, 4, 5]
i = 1⇒ não fazer nada
i = 2⇒ não fazer nada
i = 3⇒ não fazer nada
i = 4⇒ não fazer nada
Desafio
Dado
n inteiros, ordena-os em ordem crescente usando Insertion Sort.Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ 1000), o número de elementos no array.A linha seguinte contém
n inteiros separados por espaço ( ≤ ≤ ).Saída
O programa deve imprimir o array de entrada ordenado em ordem crescente.
Exemplos
Entrada | Saída |
5
5 5 3 2 3 | 2 3 3 5 5 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB