UFLA

🎓 Aula 12

Ordenação de Vetores: Métodos Básicos

Prof. Paulo Rettore

Universidade Federal de Lavras

GAC124 — Introdução aos Algoritmos

🎯 Por que ordenar?

Ordenar é reorganizar um conjunto em ordem crescente ou decrescente. Isso facilita a leitura, a comparação e a recuperação posterior dos dados.

Notas

Menor para maior.

Nomes

Ordem alfabética.

Busca

Vetor ordenado permite busca binária.

🔄 A ideia comum

Os métodos simples percorrem o vetor, comparam elementos e fazem trocas ou deslocamentos até que a ordem desejada seja alcançada.

Comparar

Encontre elementos fora de ordem.

Reorganizar

Troque ou desloque valores.

Repetir

Continue até ordenar.

🔎 Selection Sort

Em cada posição, procure o menor elemento do trecho ainda não ordenado e coloque-o na posição correta.

for (int i = 0; i < n - 1; i++) {
    int menor = i;
    for (int j = i + 1; j < n; j++) {
        if (v[j] < v[menor])
            menor = j;
    }
    swap(v[i], v[menor]);
}

🧩 Selection Sort em ação

v = {7, 3, 5, 1}

i = 0: menor é 1  → {1, 3, 5, 7}
i = 1: menor é 3  → permanece
i = 2: menor é 5  → permanece

Após cada passagem externa, uma nova posição inicial fica correta.

🃏 Insertion Sort

Constrói uma parte ordenada do vetor, inserindo cada novo elemento no lugar adequado.

for (int i = 1; i < n; i++) {
    int chave = v[i];
    int j = i - 1;
    while (j >= 0 and v[j] > chave) {
        v[j + 1] = v[j];
        j--;
    }
    v[j + 1] = chave;
}

📌 Insertion Sort: por que deslocar?

parte ordenada: {2, 6, 9}
novo valor: 5

desloque 9 e 6 uma posição
insira 5: {2, 5, 6, 9}

Ele funciona bem quando o vetor já está quase ordenado ou é pequeno.

🐚 Shell Sort: saltos maiores

O Shell Sort aplica a ideia de inserção em elementos separados por um intervalo (gap) e reduz esse intervalo ao longo do processo.

Gap grande

Move elementos distantes.

Gap menor

Refina a ordem.

Gap 1

Termina como Insertion Sort.

O resultado depende da sequência de gaps escolhida; por isso, a análise é mais complexa.

⚖️ Comparando os métodos

MétodoIdeia centralUso didático
SelectionSeleciona o menor do trecho.Fácil de visualizar.
InsertionInsere no trecho ordenado.Bom para vetor pequeno/quase ordenado.
ShellInsertion com gaps.Melhora movimentos distantes.

Os métodos simples têm custo quadrático no caso geral, mas ensinam muito sobre vetores, índices e laços aninhados.

🧩 Prática em aula

Implemente Selection Sort para ordenar cinco inteiros e mostre o vetor antes e depois.

Gabarito orientador: Use dois for aninhados, guarde o índice do menor valor e faça uma troca por passagem externa.

📚 Referências e materiais

Use estas fontes para consultas pontuais depois da aula:

Os slides completos, o Campus Virtual e o DREDD continuam sendo as fontes principais da disciplina.

🎯 Selection Sort: fixar o menor

Em cada rodada, localizar o menor elemento do trecho restante e colocá-lo na próxima posição.

for (int i = 0; i < n - 1; i++) {
    int p = i;
    for (int j = i + 1; j < n; j++)
        if (v[j] < v[p]) p = j;
    swap(v[i], v[p]);
}

🃏 Insertion Sort: deslocar e inserir

A parte à esquerda já está ordenada. A chave é deslocada até encontrar sua posição.

for (int i = 1; i < n; i++) {
    int chave = v[i], j = i - 1;
    while (j >= 0 && v[j] > chave) {
        v[j + 1] = v[j];
        j--;
    }
    v[j + 1] = chave;
}

🐚 Shell Sort: trabalhar com gaps

O vetor é refinado com intervalos maiores antes da última passagem com gap 1.

🔗 Complementos online

📌 Resumo da aula

  • Selection Sort escolhe o menor elemento do trecho.
  • Insertion Sort insere cada elemento no trecho ordenado.
  • Shell Sort usa gaps para mover elementos distantes.
  • Índices e limites dos laços determinam a correção.

PRÓXIMA AULA

⏭️ Próxima aula

Arquivos binários e arquivos tipados

Prof. Paulo Rettore

GAC124 — Introdução aos Algoritmos