Entendendo Selection Sort · MrPunkDaSilva

O que é Selection Sort?

O Selection Sort é um algoritmo de ordenação simples e intuitivo que funciona dividindo o array em duas partes:

Parte ordenada: Localizada no início do array (inicialmente vazia)
Parte não ordenada: Localizada no final do array (inicialmente todo o array)

Como funciona?

O algoritmo funciona da seguinte forma:

Encontra o menor elemento da parte não ordenada
Troca esse elemento com o primeiro elemento da parte não ordenada
Expande a parte ordenada em uma posição
Repete o processo até que todo o array esteja ordenado

Diagramação

Exemplo Visual

Considerando o array: [64, 25, 12, 22, 11]

Iteração 1:

Parte ordenada: []
Parte não ordenada: [64, 25, 12, 22, 11]
Menor elemento: 11 (posição 4)
Troca: 11 ↔ 64
Resultado: [11, 25, 12, 22, 64]

Iteração 2:

Parte ordenada: [11]
Parte não ordenada: [25, 12, 22, 64]
Menor elemento: 12 (posição 2)
Troca: 12 ↔ 25
Resultado: [11, 12, 25, 22, 64]

Iteração 3:

Parte ordenada: [11, 12]
Parte não ordenada: [25, 22, 64]
Menor elemento: 22 (posição 3)
Troca: 22 ↔ 25
Resultado: [11, 12, 22, 25, 64]

Iteração 4:

Parte ordenada: [11, 12, 22]
Parte não ordenada: [25, 64]
Menor elemento: 25 (já na posição correta)
Sem troca necessária
Resultado: [11, 12, 22, 25, 64]

Implementação

Nossa implementação educativa inclui saídas detalhadas para ajudar no aprendizado.

Você pode encontrar uma implementação completa e educativa do Selection Sort em:

📁 Domus/Domus-1/selectionSort.cpp

Função Principal - Selection Sort Algorithm

void selectionSortAlgorithm(int dataArray[], int arraySize)
{
    cout << "========================================" << endl;
    cout << "STARTING SELECTION SORT ALGORITHM" << endl;
    cout << "========================================" << endl;
    cout << "Initial array: ";
    for(int displayIndex = 0; displayIndex < arraySize; displayIndex++) {
        cout << dataArray[displayIndex] << " ";
    }
    cout << endl << endl;

    int totalNumberOfSwaps = 0;

    for (int currentPosition = 0; currentPosition < arraySize - 1; currentPosition++)
    {
        cout << ">>> ITERATION " << (currentPosition + 1) << " <<<" << endl;
        cout << "Looking for smallest element for position " << currentPosition << endl;
        
        int smallestElementIndex = findSmallestElementIndex(dataArray, currentPosition, arraySize - 1);

        if (currentPosition != smallestElementIndex) {
            cout << "Smallest element is at position " << smallestElementIndex << ", need to swap with position " << currentPosition << endl;
            swapElements(dataArray, currentPosition, smallestElementIndex);
            totalNumberOfSwaps++;
        } else {
            cout << "Smallest element is already in correct position (" << currentPosition << "), no swap needed" << endl;
        }

        cout << "Array state after iteration " << (currentPosition + 1) << ": ";
        for(int displayIndex = 0; displayIndex < arraySize; displayIndex++) {
            if (displayIndex <= currentPosition) {
                cout << "[" << dataArray[displayIndex] << "] "; // Already sorted elements
            } else {
                cout << dataArray[displayIndex] << " ";        // Not yet sorted elements
            }
        }
        cout << endl;
        cout << "Elements sorted: " << (currentPosition + 1) << "/" << arraySize << endl;
        cout << "--------------------------------" << endl;
    }

    cout << "========================================" << endl;
    cout << "SELECTION SORT ALGORITHM COMPLETED!" << endl;
    cout << "Total number of swaps performed: " << totalNumberOfSwaps << endl;
    cout << "========================================" << endl;
}

Função para Encontrar o Menor Elemento

int findSmallestElementIndex(int dataArray[], int startIndex, int endIndex)
{
    cout << "--- Searching for smallest element in range [" << startIndex << ", " << endIndex << "] ---" << endl;
    int currentIndex = startIndex;
    int smallestIndex = currentIndex;
    int numberOfComparisons = 0;

    cout << "Initial element for comparison: dataArray[" << smallestIndex << "] = " << dataArray[smallestIndex] << endl;

    while (currentIndex <= endIndex)
    {
        cout << "Comparing dataArray[" << currentIndex << "] = " << dataArray[currentIndex] << " with current smallest dataArray[" << smallestIndex << "] = " << dataArray[smallestIndex];
        numberOfComparisons++;
        
        if (dataArray[currentIndex] < dataArray[smallestIndex])
        {
            cout << " -> " << dataArray[currentIndex] << " is smaller! New smallest element found at position " << currentIndex << endl;
            smallestIndex = currentIndex;
        }
        else
        {
            cout << " -> " << dataArray[currentIndex] << " >= " << dataArray[smallestIndex] << ", keeping current smallest" << endl;
        }

        currentIndex++;
    }

    cout << "Smallest element found: " << dataArray[smallestIndex] << " at position " << smallestIndex << " (after " << numberOfComparisons << " comparisons)" << endl;
    return smallestIndex;
}

Função para Trocar Elementos

void swapElements(int dataArray[], int firstPosition, int secondPosition)
{
    cout << "  -> Swapping elements: " << dataArray[firstPosition] << " (position " << firstPosition << ") <-> " << dataArray[secondPosition] << " (position " << secondPosition << ")" << endl;
    int temporaryValue = dataArray[firstPosition];
    dataArray[firstPosition] = dataArray[secondPosition];
    dataArray[secondPosition] = temporaryValue;
    cout << "  -> After swap: position " << firstPosition << " = " << dataArray[firstPosition] << ", position " << secondPosition << " = " << dataArray[secondPosition] << endl;
}

Características do Algoritmo

Complexidade de Tempo

Melhor caso: O(n²) - Mesmo que o array já esteja ordenado
Caso médio: O(n²) - Comportamento típico
Pior caso: O(n²) - Array ordenado inversamente

Complexidade de Espaço

O(1) - Algoritmo in-place, usa apenas memória constante adicional

Propriedades Importantes

Propriedade	Valor
Estável	❌ Não
In-place	✅ Sim
Adaptivo	❌ Não
Comparações	O(n²)
Trocas	O(n)

Por que o Selection Sort NÃO é Estável?

O que significa "Estabilidade" em algoritmos de ordenação?

Um algoritmo de ordenação é estável quando mantém a ordem relativa dos elementos que possuem valores iguais. Ou seja, se dois elementos têm o mesmo valor, aquele que aparece primeiro no array original deve aparecer primeiro no array ordenado.

Exemplo Prático de Instabilidade

Considere um array de cartas onde cada carta tem um valor e um naipe:

Array inicial: [5♠, 3♦, 5♥, 2♣, 3♠]

Vamos ordenar por valor numérico apenas, ignorando o naipe:

✅ Ordenação Estável (esperada):

[2♣, 3♦, 3♠, 5♠, 5♥]

Note que 3♦ vem antes de 3♠ (mantém ordem original)
E 5♠ vem antes de 5♥ (mantém ordem original)

❌ Selection Sort (instável):

[2♣, 3♠, 3♦, 5♥, 5♠]

3♠ agora vem antes de 3♦ (ordem alterada!)
5♥ agora vem antes de 5♠ (ordem alterada!)

Por que isso acontece no Selection Sort?

O Selection Sort troca elementos distantes entre si, o que pode "pular" sobre elementos iguais e alterar sua ordem relativa.

Demonstração com números simples:

Array inicial: [4, 2, 4, 1, 3]

Para distinguir, vamos chamar: [4a, 2, 4b, 1, 3]

Execução do Selection Sort:

Iteração 1:

Procura menor elemento: 1 (posição 3)
Troca: 4a ↔ 1
Resultado: [1, 2, 4b, 4a, 3]

Observe: 4b agora vem antes de 4a!

Iteração 2:

Procura menor na parte não ordenada [2, 4b, 4a, 3]: 2 já está correto
Sem troca
Resultado: [1, 2, 4b, 4a, 3]

Iteração 3:

Procura menor na parte não ordenada [4b, 4a, 3]: 3 (posição 4)
Troca: 4b ↔ 3
Resultado: [1, 2, 3, 4a, 4b]

Array final: [1, 2, 3, 4a, 4b]

O Problema da "Troca Distante"

Array: [4a, 2, 4b, 1, 3]
        ↑           ↑
        |___________|
     Troca distante que "pula"
     sobre 4b, alterando a ordem!

Quando o Selection Sort encontra o menor elemento em uma posição distante, ele o troca diretamente com a posição atual, pulando sobre todos os elementos intermediários, incluindo aqueles que têm o mesmo valor.

Impacto Prático da Instabilidade

A instabilidade pode ser problemática em situações reais:

Ordenação de registros de funcionários por salário:
- Se dois funcionários têm o mesmo salário, você pode querer manter a ordem original (ex: por data de contratação)
Classificação de produtos por preço:
- Produtos com mesmo preço podem ter diferentes prioridades de exibição
Ordenação de notas de alunos:
- Alunos com a mesma nota podem estar em ordem alfabética inicialmente

Como tornar o Selection Sort estável?

É possível modificar o Selection Sort para ser estável, mas isso aumenta a complexidade:

// Versão estável (menos eficiente)
void stableSelectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int minIdx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        
        // Em vez de trocar diretamente, 
        // desloca todos os elementos entre i e minIdx
        int key = arr[minIdx];
        while (minIdx > i) {
            arr[minIdx] = arr[minIdx-1];
            minIdx--;
        }
        arr[i] = key;
    }
}

Mas isso aumenta a complexidade de trocas de O(n) para O(n²)!

Visualização da Instabilidade - "Rotatividade"

O conceito de "rotatividade" que você mencionou refere-se à forma como os elementos "giram" ou alteram suas posições relativas durante as trocas distantes:

Estado inicial: [4a, 2, 4b, 1, 3]
                 ▲              ▲
                 └──────────────┘ Troca distante na iteração 1

Após troca:     [1, 2, 4b, 4a, 3]
                        ▲   ▲
                     4b "rotacionou" para frente de 4a

Estado inicial: [A, B, C, D] (onde A = D em valor)
Após Selection: [D, B, C, A] (A e D trocaram posições!)
                 ▲        ▲
                 └────────┘ "Rotatividade" - ordem relativa invertida

Comparação Visual: Estável vs Instável

Algoritmo Estável (ex: Insertion Sort):

[3a, 1, 3b, 2] → [1, 2, 3a, 3b] ✅ Ordem mantida
 ▲      ▲                ▲   ▲
 └──────┘                └───┘ 3a ainda vem antes de 3b

Selection Sort (Instável)

[3a, 1, 3b, 2] → [1, 2, 3b, 3a] ❌ Ordem alterada!
 ▲      ▲               ▲   ▲
 └──────┘               └───┘ 3b agora vem antes de 3a

Resumo: Por que Selection Sort é Instável

Trocas distantes: Elementos são trocados através de grandes distâncias
Pula elementos: Ignora elementos iguais no meio do caminho
Foco apenas no valor: Não considera a posição original dos elementos iguais
Prioriza eficiência: A versão estável seria muito menos eficiente
Rotatividade: Elementos iguais podem "rotacionar" suas posições relativas

Vantagens vs. Disvantagens

Vantagens

✅ Simples de implementar e entender
✅ Poucas trocas: Máximo de n-1 trocas
✅ In-place: Não requer memória adicional
✅ Funciona bem com arrays pequenos
✅ Eficiente quando operações de escrita são caras

Desvantagens

❌ Complexidade O(n²): Ineficiente para arrays grandes
❌ Não é estável: Pode alterar a ordem relativa de elementos iguais
❌ Não é adaptivo: Não aproveita arrays parcialmente ordenados
❌ Sempre faz n-1 passadas: Mesmo que o array já esteja ordenado

Quando Usar?

O Selection Sort é adequado quando:

Arrays pequenos (< 50 elementos)
Operações de escrita são caras (ex: memória flash)
Simplicidade é mais importante que eficiência
Memória é limitada (algoritmo in-place)

Comparação com Outros Algoritmos

Algoritmo	Melhor Caso	Caso Médio	Pior Caso	Estável	Trocas
Selection Sort	O(n²)	O(n²)	O(n²)	❌	O(n)
Bubble Sort	O(n)	O(n²)	O(n²)	✅	O(n²)
Insertion Sort	O(n)	O(n²)	O(n²)	✅	O(n²)
Merge Sort	O(n log n)	O(n log n)	O(n log n)	✅	-
Quick Sort	O(n log n)	O(n log n)	O(n²)	❌	O(n log n)

Variações do Selection Sort

1. Selection Sort Bidirecional

Encontra simultaneamente o menor e maior elemento em cada passada, colocando-os nas extremidades.

2. Selection Sort Recursivo

Implementação recursiva que ordena recursivamente subarray após colocar o menor elemento na primeira posição.

3. Selection Sort Estável

Modificação que mantém a estabilidade trocando elementos apenas quando necessário.

Exercícios Práticos

Exercício 1: Implementação Básica

Implemente o Selection Sort para ordenar um array de strings por ordem alfabética.

💡 Solução do Exercício 1

Código completo

Pontos importantes:

Usamos o operador < para comparação lexicográfica de strings
A lógica é a mesma do Selection Sort para números
Strings são ordenadas alfabeticamente (A-Z)

Exercício 2: Contagem de Operações

Modifique o algoritmo para contar o número de comparações e trocas realizadas.

💡 Solução do Exercício 2

Código completo

Análise das Estatísticas:

Comparações: Sempre n(n-1)/2 independente da entrada
Trocas: No máximo n-1, pode ser menor se alguns elementos já estão no lugar
Eficiência: Mostra quantas trocas foram realmente necessárias

Exercício 3: Versão Estável

Implemente uma versão estável do Selection Sort.

💡 Solução do Exercício 3

Código completo

Como funciona a versão estável:

Rotação em vez de troca: Em vez de trocar o menor elemento com o primeiro, rotacionamos todos os elementos
Preserva ordem relativa: Elementos iguais mantêm sua ordem original
Complexidade: O(n²) tempo, mas O(n) operações de movimento por iteração
Trade-off: Mais operações de movimento, mas mantém estabilidade

Diferença visual:

Selection Sort normal: [2a, 2b] → [2b, 2a] (não estável)
Selection Sort estável: [2a, 2b] → [2a, 2b] (estável)

Conclusão

O Selection Sort é um excelente algoritmo para aprender os conceitos de ordenação devido à sua simplicidade e lógica intuitiva. Embora não seja eficiente para arrays grandes, tem seu lugar em situações específicas onde a simplicidade e o baixo número de trocas são importantes.

O algoritmo demonstra claramente os conceitos de:

Divisão de problema em subproblemas
Invariantes de loop
Análise de complexidade
Trade-offs entre diferentes métricas de performance