Nesta aula iniciamos o estudo dos algoritmos de ordenação, um dos temas mais clássicos de Estruturas de Dados. Começamos com uma revisão geral do assunto e um panorama de todos os algoritmos que veremos ao longo da disciplina, e então estudamos os dois primeiros em detalhe: Insertion Sort e Shell Sort.

1. O que é ordenação?

Ordenar é rearranjar os elementos de uma coleção (um vetor, uma lista) segundo uma relação de ordem (crescente ou decrescente), com base em uma chave — o campo usado para comparar dois elementos (por exemplo, o cod ou o preco de um Produto).

Alguns critérios usados para comparar algoritmos de ordenação entre si:

• Complexidade: quantas comparações/trocas o algoritmo realiza, em função do tamanho n da entrada — o critério mais importante para decidir qual algoritmo usar em cada situação.
• In-place: um algoritmo é in-place quando ordena usando apenas O(1) de memória extra (rearranjando os elementos no próprio vetor), em vez de construir uma cópia auxiliar.
• Estabilidade: um algoritmo é estável quando preserva a ordem relativa de elementos com chaves iguais. Isso importa, por exemplo, ao ordenar uma lista de alunos por nota: se dois alunos empatam, um algoritmo estável mantém a ordem em que eles apareciam antes (por exemplo, alfabética, se a lista já estivesse assim).
• Baseado em comparação, ou não: a maioria dos algoritmos decide a ordem comparando pares de elementos (a < b); alguns poucos (Counting Sort, Radix Sort) ordenam sem comparar diretamente os elementos entre si, explorando a natureza dos valores das chaves.

2. Panorama: principais algoritmos de ordenação

A tabela abaixo resume todos os algoritmos de ordenação que vocês já viram (em Algoritmos e Programação) ou que ainda serão vistos ao longo desta disciplina, com a complexidade temporal de cada um nos três cenários possíveis:

Onde n é o número de elementos, k é a faixa de valores possíveis das chaves (usada por Counting e Radix Sort), e d é o número de dígitos/caracteres de cada chave (usado por Radix Sort).

3. Insertion Sort

A ideia do Insertion Sort é a mesma usada para organizar cartas de baralho na mão: pega-se uma carta por vez e insere-se na posição correta entre as cartas já organizadas à esquerda. A "parte já ordenada" do vetor começa com um único elemento (vetor[0], trivialmente ordenado) e cresce uma posição a cada passo, até cobrir o vetor inteiro.

void insertionSort(int vetor[], int n) {
    int i, j, chave;

    // vetor[0..0] já está "ordenado" (um único elemento sempre está);
    // por isso começamos em i = 1, tentando inserir vetor[1] em relação a ele.
    for (i = 1; i < n; i++) {
        chave = vetor[i]; // guarda o elemento antes de sobrescrever sua posição
        j = i - 1;         // j percorre a parte já ordenada, da direita para a esquerda

        // enquanto houver alguém à esquerda maior que "chave", abre espaço
        // deslocando esse alguém uma posição para a direita
        while (j >= 0 && vetor[j] > chave) {
            vetor[j + 1] = vetor[j]; // desloca vetor[j] para a direita
            j--;                      // continua olhando mais à esquerda
        }

        // o laço parou porque achou alguém <= chave (ou chegou ao início do vetor);
        // "chave" pertence logo depois dessa posição
        vetor[j + 1] = chave;
    }
}

Note que o laço interno (while) só percorre a parte já ordenada do vetor (vetor[0..i-1]) — nunca a parte ainda não visitada. É por isso que dizemos que, "a cada passo, mais uma posição do vetor passa a fazer parte da região ordenada".

Acompanhando a execução, passo a passo

Vamos ordenar o vetor [50, 20, 40, 10] (n = 4), acompanhando o valor de i, chave, e como o while desloca elementos. Usamos valores como 50, 20, ... (em vez de 5, 2, ...) para não confundi-los com os índices (i, j) usados para percorrer o vetor:

Vetor inicial:  [50, 20, 40, 10]
                 ^ordenado(sozinho)

i=1, chave=20:
  j=0: vetor[0]=50 > 20  -> desloca: [50, 50, 40, 10], j=-1
  laço para (j < 0)      -> vetor[j+1] = vetor[0] = chave
  vetor:          [20, 50, 40, 10]
                   ^------^ ordenado

i=2, chave=40:
  j=1: vetor[1]=50 > 40  -> desloca: [20, 50, 50, 10], j=0
  j=0: vetor[0]=20 > 40? não -> laço para
  vetor[j+1] = vetor[1] = chave
  vetor:          [20, 40, 50, 10]
                   ^----------^ ordenado

i=3, chave=10:
  j=2: vetor[2]=50 > 10  -> desloca: [20, 40, 50, 50], j=1
  j=1: vetor[1]=40 > 10  -> desloca: [20, 40, 40, 50], j=0
  j=0: vetor[0]=20 > 10  -> desloca: [20, 20, 40, 50], j=-1
  laço para (j < 0)      -> vetor[j+1] = vetor[0] = chave
  vetor:          [10, 20, 40, 50]
                   ^--------------^ ordenado (vetor inteiro)

Repare como chave = 10 (o menor valor do vetor) precisou ser deslocada por todas as três posições já ordenadas — esse é justamente o cenário que deixa o Insertion Sort lento: um elemento pequeno "preso" muito à direita.

Análise de complexidade

O laço externo (for) sempre executa n - 1 vezes, independente da entrada — o que varia é quantas vezes o laço interno (while) desloca elementos a cada iteração:

• Melhor caso — vetor já ordenado: para cada i, a condição vetor[j] > chave já é falsa na primeira verificação (o elemento à esquerda nunca é maior), então o while não desloca nada. Só sobra o custo do for, então o algoritmo é O(n).
• Pior caso — vetor em ordem decrescente: para cada i, a chave é sempre a menor já vista, então o while desloca todos os i elementos já ordenados antes de encontrar seu lugar (no início). O total de deslocamentos é 1 + 2 + ... + (n-1), uma soma de progressão aritmética que resulta em O(n²).
• Caso médio: em uma entrada aleatória, espera-se que, em média, cada elemento precise ser deslocado por metade da parte já ordenada — ainda uma fração de n, então a complexidade média continua sendo O(n²) (a constante multiplicativa é menor, mas a ordem de grandeza não muda).

4. Shell Sort

O Shell Sort ataca a principal fraqueza do Insertion Sort: quando um elemento pequeno está muito à direita no vetor, ele precisa ser deslocado uma posição de cada vez até chegar ao início, o que é lento. A solução é comparar elementos distantes entre si primeiro, usando um gap (intervalo) que vai diminuindo a cada passagem, até terminar com um gap de 1 — nesse ponto, o vetor já está "quase ordenado", e essa última passagem (um Insertion Sort comum) é bem mais rápida do que seria sobre o vetor original.

void shellSort(int vetor[], int n) {
    int gap, i, j, chave;

    // a cada passagem, o gap diminui pela metade: n/2, n/4, ..., até chegar em 1
    for (gap = n / 2; gap > 0; gap /= 2) {

        // este "for" é o mesmo Insertion Sort de antes, só que comparando
        // elementos a "gap" posições de distância, em vez de posições vizinhas
        for (i = gap; i < n; i++) {
            chave = vetor[i];
            j = i - gap; // j "pula" de gap em gap para trás, não de 1 em 1

            while (j >= 0 && vetor[j] > chave) {
                vetor[j + gap] = vetor[j]; // desloca a um "gap" de distância
                j -= gap;
            }

            vetor[j + gap] = chave;
        }
    }
}

Compare com o Insertion Sort: a única diferença real é trocar 1 por gap em três lugares (i = gap em vez de i = 1; j = i - gap em vez de j = i - 1; j -= gap em vez de j--). Quando gap chega a 1, o código se torna idêntico ao Insertion Sort — a última passagem do Shell Sort é sempre um Insertion Sort comum, só que sobre um vetor já quase ordenado pelas passagens anteriores.

Acompanhando a execução, passo a passo

Vamos ordenar [50, 20, 40, 10, 60, 30] (n = 6), com gap começando em 3 (n/2). Novamente, usamos valores terminados em 0 só para não confundi-los com os índices:

Vetor inicial:        [50, 20, 40, 10, 60, 30]
                         0   1   2   3   4   5   (índices)

--- gap = 3 ---
Compara/ordena os "subvetores" formados a cada 3 posições:
  índices {0,3}: [50,10] -> fora de ordem -> vira [10,50]
  índices {1,4}: [20,60] -> já em ordem   -> continua [20,60]
  índices {2,5}: [40,30] -> fora de ordem -> vira [30,40]
Vetor apos gap=3:      [10, 20, 30, 50, 60, 40]

--- gap = 1 (Insertion Sort comum) ---
i=1, chave=20: 10 > 20? não          -> [10, 20, 30, 50, 60, 40]
i=2, chave=30: 20 > 30? não          -> [10, 20, 30, 50, 60, 40]
i=3, chave=50: 30 > 50? não          -> [10, 20, 30, 50, 60, 40]
i=4, chave=60: 50 > 60? não          -> [10, 20, 30, 50, 60, 40]
i=5, chave=40: 60>40 desloca, 50>40 desloca, 30>40? não
                                     -> [10, 20, 30, 40, 50, 60]

Vetor final:           [10, 20, 30, 40, 50, 60]

Note como, depois da passagem com gap = 3, o vetor já estava bem mais próximo do ordenado — a passagem final com gap = 1 precisou deslocar elementos só uma vez (para o 40), em vez de repetidamente a cada posição, como aconteceria num Insertion Sort "do zero" sobre o vetor original.

Análise de complexidade

A análise exata do Shell Sort é mais delicada que a do Insertion Sort, porque depende da sequência de gaps escolhida — mas a ideia central é sempre a mesma: quanto mais "pré-ordenado" o vetor fica nas passagens com gap grande, mais barata fica a passagem final com gap = 1.

• Melhor caso: vetor já ordenado — cada passagem, para qualquer gap, não desloca nada (assim como no Insertion Sort), resultando em O(n log n) (uma passagem por valor de gap, e há O(log n) valores de gap até chegar em 1).
• Pior caso: com a sequência de gaps n/2, n/4, ..., 1 usada aqui, o pior caso continua sendo O(n²) — mas, na prática, isso raramente se aproxima do comportamento real observado, que é bem mais rápido.
• Caso médio (na prática): para essa mesma sequência de gaps, o comportamento observado empiricamente fica próximo de O(n¹·³) — sequências de gaps diferentes (existem várias propostas na literatura) podem alcançar limites teóricos ainda melhores, mas o importante aqui é entender por quê o Shell Sort tende a ser mais rápido que o Insertion Sort puro na prática, não decorar uma fórmula exata.

Resumo

Exercícios

1. Explique a diferença entre um algoritmo de ordenação estável e um instável. Dê um exemplo prático de quando essa diferença importa.
2. O que significa um algoritmo de ordenação ser in-place? O Insertion Sort apresentado nesta aula é in-place? Justifique observando o código.
3. Por que nenhum algoritmo de ordenação baseado em comparação consegue ser mais rápido que O(n log n) no pior caso, enquanto Counting Sort consegue O(n + k)?
4. Simule manualmente o Insertion Sort sobre o vetor [8, 3, 7, 4, 2], mostrando o estado do vetor após cada iteração do laço externo (variável i).
5. Explique por que o Insertion Sort é O(n) no melhor caso, mas O(n²) no pior caso. Que tipo de entrada gera cada um desses casos?
6. No Shell Sort, por que a última passagem (com gap == 1) tende a ser muito mais rápida do que executar um Insertion Sort comum diretamente sobre o vetor original?
7. O Shell Sort apresentado nesta aula é estável? Dê um exemplo com dois elementos de chaves iguais em que a ordem relativa entre eles se inverte durante a execução.

Sugestões de Respostas dos Exercícios

Vetor inicial:      [8, 3, 7, 4, 2]
Apos i=1 (chave=3):  [3, 8, 7, 4, 2]
Apos i=2 (chave=7):  [3, 7, 8, 4, 2]
Apos i=3 (chave=4):  [3, 4, 7, 8, 2]
Apos i=4 (chave=2):  [2, 3, 4, 7, 8]