Introdução à Ordenação de Dados

A ordenação é uma operação fundamental na computação, consistindo no arranjo de elementos em uma sequência lógica, seja numérica ou alfabética. A escolha do algoritmo ideal depende do volume de dados, da memória disponível e da estabilidade desejada.

Algoritmos de Ordenação Simples

1. Selecsion Sort (Ordenação por Seleção)

Este algoritmo baseia-se na busca contínua pelo menor elemento dentro da parte não ordenada do array, posicionando-o no início da sequência. Embora simples, sua eficiência é limitada para grandes conjuntos de dados devido à sua complexidade temporal O(n²).

public void selectionSort(int[] vetor) {
    int n = vetor.length;
    for (int i = 0; i < n - 1; i++) {
        int indiceMinimo = i;
        for (int j = i + 1; j < n; j++) {
            if (vetor[j] < vetor[indiceMinimo]) {
                indiceMinimo = j;
            }
        }
        if (indiceMinimo != i) {
            trocar(vetor, i, indiceMinimo);
        }
    }
}

private void trocar(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

2. Bubble Sort (Ordenação por Bolha)

O Bubble Sort percorre o array múltiplas vezes, comparando elementos adjacentes e trocando-os de lugar caso estejam na ordem errada. O maior elemento "flutua" para o final a cada iteração. Uma otimização comum é interromper a execução se nenhuma troca ocorrer em um ciclo completo.

public void bubbleSort(int[] colecao) {
    int total = colecao.length;
    boolean houveTroca;
    for (int i = 0; i < total - 1; i++) {
        houveTroca = false;
        for (int j = 0; j < total - 1 - i; j++) {
            if (colecao[j] > colecao[j + 1]) {
                trocar(colecao, j, j + 1);
                houveTroca = true;
            }
        }
        if (!houveTroca) break;
    }
}

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

Este método constrói a lista final um item por vez. Ele é eficiente para listas pequenas ou para dados que já estão parcialmente ordenados, movendo os elementos maiores para abrir espaço para o item atual.

public void insertionSort(int[] dados) {
    for (int i = 1; i < dados.length; i++) {
        int valorAtual = dados[i];
        int j = i - 1;
        while (j >= 0 && dados[j] > valorAtual) {
            dados[j + 1] = dados[j];
            j--;
        }
        dados[j + 1] = valorAtual;
    }
}

4. Shell Sort

O Shell Sort é uma extensão do Insertion Sort que permite a troca de elementos distantes. Ele utiliza um intervalo (h) que diminui gradualmente até chegar a 1, reduzindo significativamente o número de movimentações necessárias.

public void shellSort(int[] lista) {
    int tamanho = lista.length;
    int h = 1;
    while (h < tamanho / 3) h = 3 * h + 1;

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

Algoritmos de Ordenação Avançados

1. Merge Sort (Ordenação por Inetrcalação)

Baseado na estratégia "Dividir para Conquistar", o Merge Sort divide o array recursivamente em metades até que cada sub-array tenha apenas um elemento. Em seguida, os sub-arrays são mesclados de forma ordenada.

public void mergeSort(int[] array, int inicio, int fim) {
    if (inicio < fim) {
        int meio = inicio + (fim - inicio) / 2;
        mergeSort(array, inicio, meio);
        mergeSort(array, meio + 1, fim);
        unificar(array, inicio, meio, fim);
    }
}

private void unificar(int[] arr, int esq, int meio, int dir) {
    int[] temp = new int[dir - esq + 1];
    int i = esq, j = meio + 1, k = 0;

    while (i <= meio && j <= dir) {
        temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
    }
    while (i <= meio) temp[k++] = arr[i++];
    while (j <= dir) temp[k++] = arr[j++];

    for (i = 0; i < temp.length; i++) {
        arr[esq + i] = temp[i];
    }
}

2. Quick Sort

O Quick Sort seleciona um elemento como "pivô" e particiona o array em dois: elementos menores que o pivô à esquerda e maiores à direita. A eficiência deste algoritmo depende da escolha do pivô, apresentando um excelente desempenho médio de O(n log n).

public void quickSort(int[] v, int esq, int dir) {
    if (esq < dir) {
        int indicePivo = particionar(v, esq, dir);
        quickSort(v, esq, indicePivo - 1);
        quickSort(v, indicePivo + 1, dir);
    }
}

private int particionar(int[] v, int esq, int dir) {
    int pivo = v[esq];
    int i = esq + 1;
    int j = dir;

    while (i <= j) {
        while (i <= j && v[i] <= pivo) i++;
        while (i <= j && v[j] > pivo) j--;
        if (i < j) trocar(v, i, j);
    }
    trocar(v, esq, j);
    return j;
}

Ordenação com Heaps

Heap Sort

Este algoritmo utiliza uma estrutura de dados de árvore binária chamada Heap para gerenciar os elementos. Ele transforma o array em um "Max-Heap" (onde o pai é maior que os filhos) e extrai repetidamente o maior elemento, movendo-o para o final da estrutura.

public void heapSort(int[] vetor) {
    int n = vetor.length;

    for (int i = n / 2 - 1; i >= 0; i--) {
        reajustarHeap(vetor, n, i);
    }

    for (int i = n - 1; i > 0; i--) {
        trocar(vetor, 0, i);
        reajustarHeap(vetor, i, 0);
    }
}

private void reajustarHeap(int[] arr, int n, int i) {
    int maior = i;
    int esquerda = 2 * i + 1;
    int direita = 2 * i + 2;

    if (esquerda < n && arr[esquerda] > arr[maior]) maior = esquerda;
    if (direita < n && arr[direita] > arr[maior]) maior = direita;

    if (maior != i) {
        trocar(arr, i, maior);
        reajustarHeap(arr, n, maior);
    }
}