Insertion sort

O problema

Ao organizar cartas na mão, você pega uma carta nova e a encaixa entre as que já estão em ordem. As cartas maiores escorregam um pouco para a direita para abrir espaço.

Em um vetor não há espaço livre entre as posições. Como abrir uma vaga sem perder nenhuma carta?

Considere as cartas 2, 5 e 8 já em ordem. Onde entra a carta 4, e quais cartas precisam se mover?

Como funciona

O insertion sort divide o vetor em duas partes: à esquerda, um trecho já ordenado; à direita, os elementos que ainda faltam. No começo, o trecho ordenado tem só o primeiro elemento, porque um elemento sozinho está sempre em ordem. A cada etapa, o próximo elemento é inserido no lugar certo do trecho ordenado, em três passos:

1. Guarde a chave. Copie o próximo elemento para uma variável, a chave. A posição dele no vetor agora pode ser sobrescrita.
2. Desloque os maiores. Da direita para a esquerda, cada elemento maior que a chave é copiado uma posição para a direita. O “buraco” vai andando para a esquerda.
3. Insira. Ao encontrar um elemento que não é maior que a chave, ou ao chegar ao início, escreva a chave no buraco.

Repetindo essa inserção para cada elemento, da esquerda para a direita, o vetor inteiro fica ordenado:

Deslocar, não trocar

O bubble sort e o insertion sort mexem nos mesmos pares de elementos, mas de jeitos diferentes. Para levar o 1 do fim ao início de [2, 4, 5, 1]:

Na prática

Implementação em C

void insertion_sort(int v[], int n) {
    for (int i = 1; i < n; i++) {          // v[0..i-1] já está ordenado
        int chave = v[i];                   // 1) guarda a chave
        int j = i - 1;
        while (j >= 0 && v[j] > chave) {   // j >= 0 PRIMEIRO: evita ler v[-1]
            v[j + 1] = v[j];                // 2) desloca o maior para a direita
            j--;
        }
        v[j + 1] = chave;                   // 3) j+1 é o buraco livre
    }
}

Para usar: declare int v[] = {5, 2, 4, 1}; e chame insertion_sort(v, 4);. O resultado é [1, 2, 4, 5], com os 5 deslocamentos da figura.

Exemplo real: a fila do pronto-socorro

Em um pronto-socorro, os pacientes são atendidos por gravidade (de 1, leve, a 5, crítico). Com gravidade igual, quem chegou antes é atendido antes. Os pacientes não chegam todos de uma vez: a fila precisa estar correta a cada chegada.

Não é preciso reordenar a fila inteira a cada paciente. A fila já está ordenada, então basta fazer uma única inserção, exatamente um passo do insertion sort:

#include <stdio.h>

typedef struct {
    char nome[20];
    int gravidade;              // 1 (leve) a 5 (crítico)
} Paciente;

// Insere p na fila já ordenada: mais grave primeiro; empate, quem chegou antes.
// Pré-condição: a fila tem espaço para mais um paciente.
void chegar(Paciente fila[], int *n, Paciente p) {
    int j = *n - 1;
    while (j >= 0 && fila[j].gravidade < p.gravidade) {   // < estrito: estável
        fila[j + 1] = fila[j];                              // abre espaço
        j--;
    }
    fila[j + 1] = p;
    (*n)++;
}

int main(void) {
    Paciente fila[10];
    int n = 0;
    Paciente chegadas[] = {{"Ana", 2}, {"Bruno", 4}, {"Carla", 2}, {"Davi", 5}, {"Eva", 4}};

    for (int i = 0; i < 5; i++) {
        chegar(fila, &n, chegadas[i]);
        printf("Chegou %-5s (%d): ", chegadas[i].nome, chegadas[i].gravidade);
        for (int k = 0; k < n; k++) {
            printf("%s%s", fila[k].nome, k < n - 1 ? ", " : "\n");
        }
    }
    return 0;
}

Esse programa junta duas aulas anteriores com esta: struct para o paciente, ponteiro para que chegar atualize o tamanho n do chamador, e a inserção ordenada desta aula. Repare em Eva: ela tem a mesma gravidade de Bruno, mas chegou depois e ficou atrás dele. É o < estrito garantindo a estabilidade. Por que <, e não > como no insertion_sort? Porque aqui a fila vai do mais grave para o menos grave: o laço continua deslocando enquanto o paciente da fila for menos grave que o novo.

Cada chegada custa no máximo um deslocamento por paciente já na fila, e normalmente bem menos. Reordenar tudo a cada chegada seria muito mais caro. Sempre que os dados chegam aos poucos e a lista precisa estar sempre pronta, a inserção ordenada é a ferramenta certa.

Quanto custa na prática?

Medimos o insertion sort com quatro tipos de entrada e comparamos com o bubble sort da aula anterior nas mesmas listas:

1. Quase ordenada é o ponto forte. Cada elemento só anda algumas casas, e o trabalho fica proporcional ao tamanho da lista. Nos testes, 1 milhão de elementos quase ordenados foram ordenados em cerca de 9 ms.
2. Na lista aleatória, cerca de 14 vezes mais rápido que o bubble sort, com o mesmo número de “consertos”. As escritas pela metade e um laço interno que para assim que encontra o lugar da chave explicam umas 2 a 4 vezes. O resto vem do efeito visto na aula de bubble sort: em dados aleatórios, o processador erra muito ao tentar adivinhar o if da troca do bubble sort. Por isso, no bubble, a lista aleatória é mais lenta até que a decrescente.
3. Na lista bagunçada e grande, continua lento. O custo cresce com o quadrado do tamanho, como no bubble sort. Nos testes, 1 milhão de elementos aleatórios levou cerca de 1 minuto e 53 segundos, contra uns 9 milissegundos para 1 milhão quase ordenado.

E se a busca do lugar fosse binária? Aprofundamento

O trecho à esquerda está ordenado, então dá para achar o lugar da chave com busca binária (aula de recursão), em vez de andar casa por casa. Mas atenção ao que ela economiza:

void insertion_binaria(int v[], int n) {
    for (int i = 1; i < n; i++) {
        int chave = v[i];
        int ini = 0, fim = i;               // procura em v[0..i-1]
        while (ini < fim) {
            int meio = ini + (fim - ini) / 2;
            if (v[meio] <= chave) ini = meio + 1;
            else fim = meio;
        }                                   // ini: primeira posição com valor > chave
        for (int j = i; j > ini; j--) v[j] = v[j - 1];   // deslocamentos: os mesmos!
        v[ini] = chave;
    }
}

A busca binária reduz muito as comparações em listas bagunçadas, mas os deslocamentos continuam os mesmos, então o tempo continua crescendo com o quadrado. Em listas quase ordenadas, ela até piora: a busca casa a casa encontra o lugar, em média, em uns 3 ou 4 passos (2 ou 3 deslocamentos), enquanto a binária faz cerca de log₂ i comparações para um trecho de i elementos. Lembre: log₂ i é quantas vezes dá para dividir i ao meio até chegar a 1, ou seja, uns 16 para 50 mil e uns 20 para 1 milhão. Isso acontece mesmo com a chave já perto do lugar. As primeiras inserções são baratas, mas perto do fim de uma lista de 50 mil são umas 16 por elemento. Ela vale a pena quando comparar é caro, como ao comparar textos longos, e mover é barato.

Comparação com as outras ordenações da revisão

Exercícios progressivos

Use as figuras da aula como modelo: desenhe o vetor, a chave guardada ao lado e o buraco andando. A dica não entrega a resposta: ela indica a pergunta certa a fazer.

#include <string.h>

void ordenar_nomes(const char *nomes[], int n) {
    for (int i = 1; i < n; i++) {
        const char *chave = nomes[i];                  // guarda o ENDEREÇO do nome
        int j = i - 1;
        while (j >= 0 && strcmp(nomes[j], chave) > 0) {   // nomes[j] vem depois?
            nomes[j + 1] = nomes[j];                   // desloca só o ponteiro
            j--;
        }
        nomes[j + 1] = chave;
    }
}