Ordenação por inserção

• Conceito
• Gif
• Código
• Passo a passo
• Vamos dançar!
• Análise de complexidade [no futuro]
• Outros algoritmos

Conceito

O algoritmo de ordenação por inserção (insertion sort) compara determinado valor (a partir da segunda posição) com todos os valores anteriores e troca se algum valor anterior for maior que o valor da posição comparada. O laço interno garante que todos os valores anteriores a posição definida (2 – n) serão comparados. Enquanto o laço externo garante que o laço interno se repetirá a quantidade de vezes necessárias para que todos os valores tomem suas respectivas posições.

Vantagens

– Considerado o mais rápido DA CATEGORIA.

– Algoritmo simples.

Indicações

– Valores pré-ordenados.

– Pequena quantidade de valores.

Gif

Código

def insertion_sort(valores):
    n = len(valores)
    for i in range(1, n, +1):
        chave = valores[i]
        j = i - 1
        while (j > -1 and valores[j] > chave):
            valores[j+1] = valores[j]
            j -= 1
        valores[j+1] = chave
    return valores

Disponível em: https://github.com/wschratzenstaller/ordenacao/blob/master/insertion_sort.py

Passo a passo

em construção

vamos dançar