Ordenação por Inserção

A ideia por trás do algoritmo de ordenação por inserção é simples. Para um vetor de números, execute os seguintes passos:

Seguindo a regra acima, a cada iteração do algoritmo, todos os elementos à esquerda do índice estarão ordenados, e elementos à direita do elemento no índice ainda não foram processados (podem ser menores, iguais, ou maiores que o elemento em .

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
        # Inserve 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 () 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: