Ordenação por Inserção
A ideia por trás do algoritmo de ordenação por inserção é simples. Para um vetor $A$ de $n$ números, execute os seguintes passos:
-
A cada iteração $i$ do algoritmo, troque de posição o elemento $A[i]$ com cada elemento maior que ele que esteja à sua esquerda.
Seguindo a regra acima, a cada iteração $i$ do algoritmo, todos os elementos à esquerda do índice $i$ estarão ordenados e elementos à direita do elemento no índice $i$ ainda não foram processados (podem ser menores, iguais, ou maiores que o elemento em $A[i]$).
Com as ideias acima em mente, podemos implementar o algoritmo de ordenação por inserção da seguinte forma:
def ordenacao_insercao(A):
n = len(A)
# Percorre o arranjo A.
for j in range(1, n):
chave = A[j]
i = j - 1
# Insere o elemento A[j] na posição correta.
while i >= 0 and A[i] > chave:
A[i + 1] = A[i]
i = i - 1
A[i + 1] = chave
A = random.sample(range(-10, 10), 10)
print("Arranjo não ordenado: ", A)
ordenacao_insercao(A)
print("Arranjo ordenado:", A)Arranjo não ordenado: [7, -1, 4, -7, 2, 3, -9, 5, 1, 8] Arranjo ordenado: [-9, -7, -1, 1, 2, 3, 4, 5, 7, 8]
No pior caso, o algoritmo de ordenação por inserção possui complexidade quadrática ($O(n^2)$) no número de elementos do vetor de entrada, é um algoritmo in-place e é estável.
Se você quiser acompanhar visualmente a execução do algoritmo de ordenação por inserção, veja o excelente vídeo abaixo, feito pelo pessoal do site Algo-Rythmics:
O algoritmo de ordenação por inserção possui algumas nuances não mostradas acima:
-
O pior caso do algoritmo de ordenação por inserção (complexidade quadrática), ocorre quando o vetor de entrada está ordenado em ordem decrescente.
-
Se o vetor de entrada já estiver ordenado, o algoritmo de ordenação por inserção fará $n$ comparações e zero trocas de elementos.
-
O algoritmo de ordenação por inserção funciona muito bem para arranjos pequenos.
-
É possível reduzir o número de trocas feitas pelo algoritmo de ordenação por inserção. Para isso, podemos usar um algoritmo de busca binária para encontrar a posição em que um elemento deve ficar (isso é feito usando sucessivas trocas no algoritmo original), e após isso inserimos o elemento na posição correta com somente uma troca. Essa otimização reduz o número de trocas feitas pelo algoritmo, o que melhora seu desempenho, mas o número de comparações permanece quadrático.
Playground
# Use este espaço para praticar o que você aprendeu nesta seção.
# Basta digitar o código no espaço abaixo e clicar 'run'.