O estudo de algoritmos de ordenação é fundamental para qualquer desenvolvedor, mesmo com a existência de bibliotecas padrão. Compreender essas mecânicas permite uma análise profunda de desempenho, fornece ferramentas lógicas aplicáveis em diversos cenários e estabelece a base para a resolução de problemas complexos de processamento de dados.

Estrutura Base para Implementação

Para garantir que os algoritmos sejam genéricos, utilizamos a interface Comparable do Java. Abaixo, definimos uma estrutura utilitária que servirá de base para as implementações subsequentes.

public class OrdenadorBase {

    public static void ordenar(Comparable[] elementos) {
        // Implementação específica do algoritmo
    }

    protected static boolean menor(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    protected static void permutar(Comparable[] a, int i, int j) {
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static boolean estaOrdenado(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {
            if (menor(a[i], a[i - 1])) return false;
        }
        return true;
    }
}

Ordenação por Seleção (Selection Sort)

O Selection Sort opera sob um princípio simples: encontrar o menor item do array e movê-lo para a primeira posição disponível. O processo se repete para o restante da lista até que todos os elementos estejam posicionados.

public class Selecao {
    public static void executar(Comparable[] itens) {
        int tamanho = itens.length;
        for (int i = 0; i < tamanho; i++) {
            int indiceMenor = i;
            for (int j = i + 1; j < tamanho; j++) {
                if (compararMenor(itens[j], itens[indiceMenor])) {
                    indiceMenor = j;
                }
            }
            trocarPosicao(itens, i, indiceMenor);
        }
    }

    private static boolean compararMenor(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    private static void trocarPosicao(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

Análise de Desempenho: Para um array de tamanho N, este algoritmo realiza aproximadamente N²/2 comparações e exatamente N trocas. Uma característica marcante é que seu tempo de execução é independente da ordem inicial dos dados; um array já ordenado levará o mesmo tempo que um array aleatório.

Ordenação por Inserção (Insertion Sort)

Inspirado na forma como organizamos cartas de baralho nas mãos, o Insertion Sort insere cada novo item em sua posição correta em relação aos itens já processados. Para abrir espaço, os elementos maiores são deslocados para a direita.

public class Insercao {
    public static void ordenar(Comparable[] dados) {
        int n = dados.length;
        for (int i = 1; i < n; i++) {
            for (int j = i; j > 0 && verificarMenor(dados[j], dados[j - 1]); j--) {
                permutar(dados, j, j - 1);
            }
        }
    }

    private static boolean verificarMenor(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    private static void permutar(Comparable[] a, int i, int j) {
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

Eficiência: Ao contrário da seleção, a inserção é extremamente eficiente para arrays "quase ordenados" ou de pequeno tamanho. Em um cenário médio com chaves aleatórias, requer cerca de N²/4 comparações e trocas. No melhor caso (array já ordenado), o custo é linear: N-1 comparações e 0 trocas.

Shell Sort

O Shell Sort é uma evolução do algoritmo de inserção que permite a troca de elementos distantes. A ideia central é tornar o array "h-ordenado", ou seja, subgrupos de elementos espaçados por h posições são ordenados de forma independnete. À medida que h diminui, o array torna-se cada vez mais organizdao.

public class ShellSort {
    public static void processar(Comparable[] lista) {
        int total = lista.length;
        int h = 1;

        // Sequência de Knuth: 1, 4, 13, 40, 121, 364...
        while (h < total / 3) {
            h = 3 * h + 1;
        }

        while (h >= 1) {
            for (int i = h; i < total; i++) {
                for (int j = i; j >= h && validarMenor(lista[j], lista[j - h]); j -= h) {
                    intercambiar(lista, j, j - h);
                }
            }
            h /= 3;
        }
    }

    private static boolean validarMenor(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    private static void intercambiar(Comparable[] a, int i, int j) {
        Comparable swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }
}

Impacto: O Shell Sort quebra a barreira do tempo quadrático (N²), sendo uma escolha sólida para arrays de tamanho médio onde algoritmos mais complexos como o QuickSort poderiam ser excessivos. Sua performance exata depende da sequência de incrementos escolhida, mas é comprovadamente superior aos métodos elementares para grandes volumes de dados.