Cap. 8 Estrutura de Dados · Ordenação Interna

Algoritmos de ordenação em movimento.

Cinco famílias clássicas. Aperte ▶ para animar ou use ⏭ Passo para avançar manualmente e entender cada operação.

8.1 · Métodos por Distribuição

Counting Sort

"Não compara — apenas conta."

O Counting Sort não realiza comparações. Ele conta a frequência de cada valor e usa essa contagem para posicionar cada elemento diretamente em sua posição final.

Funciona em três fases: contar, acumular e distribuir. Exige que os valores estejam em um intervalo conhecido.

Melhor/Pior
O(n + k)
Espaço
O(n + k)
Comparações
Nenhuma
Estável
Sim
função countingSort(A, k):
  C ← zeros[0..k]
  para cada x em A:
    C[x] ← C[x] + 1      // contar
  para i de 1 até k:
    C[i] ← C[i] + C[i-1]   // acumular
  para j de n-1 até 0:
    B[C[A[j]]-1] ← A[j]   // distribuir
    C[A[j]] ← C[A[j]] - 1
  retorna B
MODO PASSO
Pronto. ▶ para animar ou ⏭ para avançar passo a passo.
Normal Contando Ordenado
8.2 · Métodos por Inserção

Insertion Sort

"Como organizar cartas na mão."

A cada passo, o elemento atual é inserido na posição correta dentro da parte já ordenada à sua esquerda, deslocando os maiores para a direita.

Muito eficiente para vetores pequenos ou já parcialmente ordenados. É a base de algoritmos híbridos como o Timsort.

Melhor caso
O(n)
Pior caso
O(n²)
Espaço
O(1)
Estável
Sim
função insertionSort(A):
  para i de 1 até n-1:
    chave ← A[i]
    j ← i - 1
    enquanto j ≥ 0 e A[j] > chave:
      A[j+1] ← A[j]
      j ← j - 1
    A[j+1] ← chave
MODO PASSO
Pronto. ▶ para animar ou ⏭ para avançar passo a passo.
Normal Comparando Inserindo Ordenado
8.3 · Métodos por Intercalação

Merge Sort

"Dividir, conquistar, intercalar."

O vetor é dividido recursivamente ao meio até restar subarranjos de tamanho 1. Em seguida, pares de subarranjos são intercalados em ordem crescente.

Garante O(n log n) em todos os casos. A contrapartida é a memória auxiliar proporcional a n.

Melhor/Pior
O(n log n)
Espaço
O(n)
Médio
O(n log n)
Estável
Sim
função mergeSort(A, ini, fim):
  se ini < fim:
    meio ← (ini+fim) / 2
    mergeSort(A, ini, meio)
    mergeSort(A, meio+1, fim)
    merge(A, ini, meio, fim)

função merge(A, ini, meio, fim):
  // intercala usando vetor auxiliar
MODO PASSO
Pronto. ▶ para animar ou ⏭ para avançar passo a passo.
Normal Intercalando Comparando Ordenado
8.4 · Métodos por Seleção

Selection Sort

"Encontre o menor. Depois o próximo menor."

A cada iteração, percorre a região não ordenada procurando o menor elemento e o troca com o primeiro elemento dessa região.

Faz no máximo n−1 trocas — útil quando trocas são caras. Porém sempre executa O(n²) comparações.

Melhor/Pior
O(n²)
Espaço
O(1)
Trocas
O(n)
Estável
Não
função selectionSort(A):
  para i de 0 até n-2:
    min ← i
    para j de i+1 até n-1:
      se A[j] < A[min]:
        min ← j
    se min ≠ i:
      trocar A[i] com A[min]
MODO PASSO
Pronto. ▶ para animar ou ⏭ para avançar passo a passo.
Normal Comparando Mínimo atual Ordenado
8.5 · Métodos por Troca

Quick Sort

"O pivô divide o mundo em dois."

Escolhe um pivô e particiona o vetor: menores à esquerda, maiores à direita. Aplica recursivamente nas duas partições.

Na prática é o mais rápido em caso médio. O pior caso O(n²) ocorre com pivôs ruins — mitigado por escolhas inteligentes.

Melhor/Médio
O(n log n)
Pior caso
O(n²)
Espaço
O(log n)
Estável
Não
função quickSort(A, ini, fim):
  se ini < fim:
    p ← particiona(A, ini, fim)
    quickSort(A, ini, p-1)
    quickSort(A, p+1, fim)

função particiona(A, ini, fim):
  pivo ← A[fim]; i ← ini-1
  para j de ini até fim-1:
    se A[j] ≤ pivo:
      i++; trocar A[i] A[j]
  trocar A[i+1] A[fim]
  retorna i+1
MODO PASSO
Pronto. ▶ para animar ou ⏭ para avançar passo a passo.
Normal Pivô Comparando Trocando Ordenado