Ordenação por Inserção

6.1 Definição de Ordenação por Inserção

Ordenação por Inserção (Insertion Sort) é um algoritmo de ordenação que constrói um array (ou lista) ordenado um elemento por vez. Ele pega cada elemento da parte não ordenada e insere na posição correta na parte ordenada.

Princípio de funcionamento:

1. Começamos com o segundo elemento do array (o primeiro elemento é considerado ordenado).
2. Comparamos o elemento atual com os anteriores e o movemos para a esquerda até encontrar a posição correta.
3. Repetimos o processo para todos os elementos do array, inserindo cada novo elemento na posição correta na parte já ordenada do array.

Complexidade temporal e espacial da Ordenação por Inserção

Complexidade temporal:

• No pior caso: O(n^2) — ocorre quando os elementos estão inicialmente ordenados em ordem inversa.
• No caso médio: O(n^2) — ocorre para disposição aleatória dos elementos.
• No melhor caso: O(n) — ocorre quando os elementos já estão ordenados.

Complexidade espacial:

O(1) — como o algoritmo usa uma quantidade constante de memória adicional (apenas algumas variáveis para armazenar valores temporários).

6.2 Análise do funcionamento do algoritmo

No passo atual do algoritmo, temos a seguinte situação:

• Temos o elemento atual com índice i.
• Todos os elementos à esquerda dele já estão ordenados do menor para o maior.
• Tentamos inserir nosso elemento atual na parte ordenada do array de forma que a ordem de ordenação não seja quebrada.

Tentar inserir o elemento na parte ordenada do array é assim:

1. A variável j no loop assume valores de i - 1 até 0.
2. Se o elemento atual (i-ésimo) for menor que o j-ésimo, movemos o valor do j-ésimo elemento uma posição para a direita.

Exemplo: situação atual:

• Elementos em verde já estão ordenados.
• Em rosa — elementos que ainda não foram ordenados.
• Elemento atual de índice 5 — marcado em marrom.

Tentamos encontrar a posição correta do nosso elemento atual na parte ordenada do array.

Passo 1 — guardamos o valor do elemento atual na variável key.

Passo 2 — o elemento No4 é maior que key? (10 é maior que 5?) Então movemos o elemento No4 para a direita:

Passo 3 — o elemento No3 é maior que key? (8 é maior que 5?) Então movemos o elemento No3 para a direita:

Passo 4 — o elemento No2 é maior que key? (6 é maior que 5?) Então movemos o elemento No2 para a direita:

Passo 5 — o elemento No1 é maior que key? (4 é maior que 5?) Não. Então guardamos o elemento key onde estava o elemento No2.

Depois de inserir o elemento No5 na posição correta, passamos para o elemento No6 e tentamos encontrar sua posição na parte ordenada do array:

Em seguida, pegamos o sétimo elemento:

Em seguida, o 8º:

6.3 Implementação do algoritmo de Ordenação por Inserção

É assim que esse algoritmo fica em Python:

def insertion_sort(arr):
    # Percorremos todos os elementos do array, começando do segundo
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # Movemos elementos arr[0..i - 1] que são maiores que a key, uma posição para frente
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key  # Inserimos a key na posição correta
    return arr  # Retornamos o array ordenado
        
# Exemplo de uso:
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("Array ordenado:", sorted_arr)
# Saída: Array ordenado: [5, 6, 11, 12, 13]

Explicação:

• Guardamos o elemento atual em key
• Movemos todos os elementos da parte ordenada do array para a direita
• Inserimos nosso elemento na posição adequada

Exemplo de funcionamento do algoritmo

Vamos pegar um exemplo de array: [12, 11, 13, 5, 6]

1. Primeiro passe (i = 1):

• Comparamos 11 e 12, movemos 12 para a direita.
• Array: [11, 12, 13, 5, 6]

2. Segundo passe (i = 2):

• 13 já está no lugar certo.
• Array: [11, 12, 13, 5, 6]

3. Terceiro passe (i = 3):

• Comparamos 5 com 13, 12 e 11, movemos todos para a direita.
• Array: [5, 11, 12, 13, 6]

4. Quarto passe (i = 4):

• Comparamos 6 com 13, 12 e 11, movemos todos para a direita.
• Array: [5, 6, 11, 12, 13]

O algoritmo termina, pois todos os elementos estão ordenados.