Ordenação por Seleção (Selection Sort): A Estratégia de Menor Elemento

1. O Conceito de Selecionar o Menor Elemento

Na Aula 23, você conheceu o Bubble Sort (Ordenação por Flutuação), cujo princípio se baseia em comparar pares vizinhos e borbulhar os maiores valores para o final da coleção. Embora o Bubble Sort seja fácil de visualizar mentalmente, ele sofre de um defeito grave: realiza uma quantidade exorbitante de trocas na memória RAM.

O Selection Sort (Ordenação por Seleção) adota uma postura muito mais paciente, metódica e cirúrgica. Em vez de trocar elementos apressadamente toda vez que encontra um número fora de ordem, o algoritmo divide conceitualmente o vetor em duas regiões contíguas bem delimitadas:

• Subvetor Ordenado (à esquerda): Cresce de 0 até (N-1), contendo os menores elementos definitivos já assentados em seus lugares finais irreversíveis.
• Subvetor Não-Ordenado (à direita): Contém os elementos remanescentes que ainda precisam ser examinados e classificados.

A cada rodada do processo, o algoritmo varre todo o subvetor desordenado à procura de um único objetivo: o índice do menor valor absoluto. Ao terminar a varredura, e apenas uma única vez por rodada, ele realiza uma troca entre o elemento da posição inicial da rodada e o menor elemento descoberto.

2. A Mecânica dos Dois Laços Aninhados

Para implementar a seleção de forma determinística, a lógica algorítmica exige dois laços aninhados:

1. Laço Externo (ponteiro i): Percorre as posições de 0 até N - 2. A posição i representa o "slot" que estamos tentando preencher nesta rodada com o próximo menor elemento do vetor.
2. Laço Interno (ponteiro j): Percorre de i + 1 até o final do vetor (N - 1). Sua única missão é comparar lista[j] com o menor valor registrado até o momento. Se encontrar alguém ainda menor, atualiza o índice indiceMenor = j.

Quando o laço interno termina, o índice indiceMenor aponta com 100% de certeza matemática para o menor elemento restante no subvetor não-ordenado. Se esse menor elemento já estiver na posição i, nenhuma troca é necessária; caso contrário, realizamos a operação de swap entre i e indiceMenor.

3. A Troca O(N) com Variável Auxiliar (Swap)

Como exploramos profundamente na Aula 26 sobre depuração e memória, computadores não conseguem trocar o conteúdo de dois endereços de memória RAM sem uma variável temporária de apoio. Se você executar simplesmente arr[i] = arr[indiceMenor], o valor original de arr[i] será sobrescrito e destruído para sempre.

No logicabr.dev, a rotina padrão de troca segura utiliza uma variável temporária do tipo apropriado:

// Troca segura entre as posicoes i e indiceMenor
numero temporario = arr[i];
arr[i] = arr[indiceMenor];
arr[indiceMenor] = temporario;

4. Implementação Completa no logicabr.dev

Vejamos o algoritmo completo do Selection Sort construído no padrão nativo do logicabr.dev, com contadores de comparações e trocas para auditoria de desempenho:

// Ordena um vetor numerico em ordem crescente usando Selection Sort
funcao ordenarPorSelecao(vetor arr) {
  numero n = tamanho(arr);
  numero totalComparacoes = 0;
  numero totalTrocas = 0;

  saida("=== INICIO DA ORDENACAO POR SELECAO ===");

  para (numero i = 0; i < n - 1; i++) {
    // Assume inicialmente que o menor elemento e o primeiro da rodada
    numero indiceMenor = i;

    // Varre o restante da lista para encontrar o menor elemento absoluto
    para (numero j = i + 1; j < n; j++) {
      totalComparacoes = totalComparacoes + 1;
      se (arr[j] < arr[indiceMenor]) {
        indiceMenor = j;
      }
    }

    // Realiza a troca apenas se o menor nao for o proprio elemento atual
    se (indiceMenor != i) {
      numero aux = arr[i];
      arr[i] = arr[indiceMenor];
      arr[indiceMenor] = aux;
      totalTrocas = totalTrocas + 1;

      saida("Rodada " + (i + 1) + ": Trocou valor " + arr[indiceMenor] + " com " + arr[i]);
    } senao {
      saida("Rodada " + (i + 1) + ": O elemento " + arr[i] + " ja estava na posicao correta.");
    }
  }

  saida("=======================================");
  saida("Total de comparacoes realizadas: " + totalComparacoes);
  saida("Total de trocas na memoria RAM: " + totalTrocas);
  saida("=======================================");
}

// Vetor de teste desordenado
vetor notasTurma = [64, 25, 12, 22, 11];

saida("Vetor Original: [64, 25, 12, 22, 11]");
ordenarPorSelecao(notasTurma);

saida("Vetor Ordenado Final:");
para (numero k = 0; k < tamanho(notasTurma); k++) {
  saida("[" + k + "] = " + notasTurma[k]);
}

5. Teste de Mesa e Rastreamento de Memória

Vamos acompanhar passo a passo a evolução do vetor [64, 25, 12, 22, 11] durante as 4 rodadas do algoritmo:

Perceba que em apenas 3 trocas de memória o vetor de 5 elementos ficou perfeitamente ordenado. No Bubble Sort tradicional sem otimizações, esse mesmo vetor exigiria mais de 7 a 10 trocas sucessivas!

6. Demonstração Matemática das Comparações

Por que o Selection Sort sempre realiza a mesma quantidade exata de comparações? Vamos somar os passos executados pelo laço interno j para um vetor de tamanho (N):

• Na primeira rodada ((i = 0)), o laço interno percorre (N - 1) elementos.
• Na segunda rodada ((i = 1)), ele percorre (N - 2) elementos.
• Na terceira rodada ((i = 2)), ele percorre (N - 3) elementos.
• ...
• Na penúltima rodada ((i = N - 2)), ele percorre apenas 1 elemento.

Essa sequência constitui a clássica Progressão Aritmética (Soma de Gauss):

Total = (N - 1) + (N - 2) + ... + 2 + 1 = rac{N(N - 1)}{2} = rac{N^2 - N}{2}

Desprezando os termos de menor ordem e coeficientes conforme estudamos na Aula 28 (Big-O), obtemos assintoticamente a ordem de grandeza O(N²). Isso significa que para (N = 1.000), o Selection Sort realiza exatamente (rac{1000 imes 999}{2} = 499.500) comparações, independente de os dados já estarem ordenados ou não.

7. Selection Sort vs Bubble Sort: O Custo de Escrita

Muitos desenvolvedores novatos acreditam que todos os algoritmos quadráticos (O(N^2)) são equivalentes. No entanto, o custo de uma operação computacional depende da arquitetura física do computador:

• Leitura e Comparação: Operação rápida que ocorre principalmente nos registradores da CPU e memória cache L1/L2.
• Escrita na RAM (Troca / Swap): Operação mais lenta que invalida linhas de cache e escreve fisicamente novos valores nos barramentos de memória.

O Bubble Sort realiza no pior caso até (rac{N(N-1)}{2}) trocas na memória RAM. Para um vetor de 1.000 itens invertidos, são quase 500.000 operações de escrita! O Selection Sort, por outro lado, realiza no máximo (N - 1) trocas (no máximo 999 escritas para 1.000 itens). Esse número de trocas estritamente linear (O(N)) torna o Selection Sort muito superior ao Bubble Sort quando o custo de gravação na memória é alto.

8. Análise Formal de Complexidade Big-O

Vamos avaliar as grandezas formais do Selection Sort:

• Melhor Caso de Tempo: (O(N^2)). Mesmo que a lista já venha ordenada, o algoritmo não possui um mecanismo de interrupção antecipada nativo; ele sempre examinará todos os pares para confirmar o menor valor.
• Caso Médio de Tempo: (O(N^2)). Em entradas aleatórias, a quantidade de comparações é sempre rigorosamente (rac{N(N-1)}{2}).
• Pior Caso de Tempo: (O(N^2)). Quando a lista está em ordem inversa, o número de comparações permanece o mesmo.
• Complexidade de Espaço (Memória Auxiliar): (O(1)). O algoritmo é puramente in-place (opera no próprio vetor original), utilizando apenas variáveis simples (indiceMenor, aux).

9. O Fenômeno da Instabilidade de Chaves (Unstable Sort)

Uma propriedade crucial que diferencia algoritmos de ordenação profissionais é a Estabilidade (Stability). Um algoritmo é estável se ele garante preservar a ordem relativa original de elementos que possuem chaves de ordenação idênticas.

O Selection Sort é INSTÁVEL. Para entender o motivo, considere o seguinte vetor de objetos com duas pessoas de mesma idade:

vetor = [ { id: 1, idade: 25 }, { id: 2, idade: 25 }, { id: 3, idade: 10 } ]

Na primeira rodada ((i = 0)), o menor elemento é a pessoa 3 (idade 10). O algoritmo troca a posição 0 com a posição 2. Ao fazer isso, a pessoa 1 (idade 25) é arremessada para o final do vetor, ficando depois da pessoa 2! A ordem relativa original entre a pessoa 1 e a pessoa 2 foi quebrada. Em sistemas que realizam ordenação secundária (como ordenar por sobrenome e depois por cidade), um algoritmo instável pode corromper a ordenação anterior.

10. Os 5 Erros Clássicos de Implementação

Ao implementar o Selection Sort, atente-se para evitar as seguintes falhas recorrentes:

11. Variante Avançada: Double Selection Sort (Min-Max Sort)

É possível otimizar a ordenação por seleção inspecionando o vetor nas duas pontas simultaneamente! Na variante Double Selection Sort (também conhecida como Min-Max Selection Sort), cada passagem do laço interno identifica simultaneamente o menor valor e o maior valor do intervalo.

O menor elemento é posicionado na extremidade esquerda (índice inicio) e o maior elemento é posicionado na extremidade direita (índice fim). A cada rodada completa, o tamanho da janela diminui em 2 elementos (um em cada borda), reduzindo a quantidade de iterações do laço externo pela metade!

funcao doubleSelectionSort(vetor arr) {
  numero inicio = 0;
  numero fim = tamanho(arr) - 1;

  enquanto (inicio < fim) {
    numero idxMin = inicio;
    numero idxMax = inicio;

    para (numero i = inicio + 1; i <= fim; i++) {
      se (arr[i] < arr[idxMin]) {
        idxMin = i;
      }
      se (arr[i] > arr[idxMax]) {
        idxMax = i;
      }
    }

    // Posiciona o menor na ponta esquerda
    numero auxMin = arr[inicio];
    arr[inicio] = arr[idxMin];
    arr[idxMin] = auxMin;

    // CUIDADO DE BORDA: Se o maior elemento estava na posicao inicio, ele foi movido para idxMin!
    se (idxMax == inicio) {
      idxMax = idxMin;
    }

    // Posiciona o maior na ponta direita
    numero auxMax = arr[fim];
    arr[fim] = arr[idxMax];
    arr[idxMax] = auxMax;

    inicio = inicio + 1;
    fim = fim - 1;
  }
}

vetor teste = [29, 10, 14, 37, 13, 88, 5];
doubleSelectionSort(teste);
saida("Resultado do Double Selection Sort: [5, 10, 13, 14, 29, 37, 88]");

12. Projeto Prático: Ranking de Classificação de Jogadores

Vamos aplicar o Selection Sort para organizar o placar de uma partida de e-sports. O objetivo é classificar os jogadores do maior número de pontos para o menor (ordem decrescente), mantendo a menor quantidade possível de alterações no placar ao vivo:

// Vetor de objetos estruturados de jogadores
vetor placar = [];
placar[0] = { nome: "CyberViper", pontos: 3200 };
placar[1] = { nome: "ShadowFox", pontos: 5800 };
placar[2] = { nome: "PixelHero", pontos: 1900 };
placar[3] = { nome: "GhostRunner", pontos: 7400 };
placar[4] = { nome: "NeonKnight", pontos: 4500 };

funcao classificarPlacar(vetor lista) {
  numero total = tamanho(lista);

  para (numero i = 0; i < total - 1; i++) {
    // Para ordem decrescente, procuramos o MAIOR elemento
    numero indiceMaior = i;

    para (numero j = i + 1; j < total; j++) {
      se (lista[j].pontos > lista[indiceMaior].pontos) {
        indiceMaior = j;
      }
    }

    se (indiceMaior != i) {
      registro aux = lista[i];
      lista[i] = lista[indiceMaior];
      lista[indiceMaior] = aux;
    }
  }
}

saida("==================================================");
saida("           CLASSIFICACAO GERAL DO TORNEIO         ");
saida("==================================================");

classificarPlacar(placar);

para (numero pos = 0; pos < tamanho(placar); pos++) {
  saida((pos + 1) + "º Lugar: " + placar[pos].nome + " (" + placar[pos].pontos + " pts)");
}
saida("==================================================");

O Selection Sort nos ensinou a lição de que minimizar operações de escrita é um objetivo arquitetural legítimo. Na próxima aula, conheceremos o Insertion Sort, o mais eficiente e inteligente de todos os algoritmos quadráticos quando confrontado com dados do mundo real.