Algoritmos de Ordenação em Java: Guia Prático

Bubble Sort

A ideia é percorrer o vetor diversas vezes, a cada passagem fazendo flutuar para o topo o maior elemento da sequência.

public static void bubbleSort(int[] vetor) {
    boolean houveTroca = true;
    while (houveTroca) {
        houveTroca = false;
        for (int i = 0; i < vetor.length - 1; i++) {
            if (vetor[i] > vetor[i + 1]) {
                int variavelAuxiliar = vetor[i + 1];
                vetor[i + 1] = vetor[i];
                vetor[i] = variavelAuxiliar;
                houveTroca = true;
            }
        }
    }
}

Selection Sort

É um algoritmo de ordenação baseado em passar sempre o menor valor do vetor para a primeira posição (ou o maior, dependendo da ordem requerida), depois o segundo menor valor para a segunda posição, e assim sucessivamente com os (n-1) elementos restantes.

public static void selectionSort(int[] v) {
    int index_min, aux;
    for (int i = 0; i < v.length; i++) {
        index_min = i;
        for (int j = i + 1; j < v.length; j++) {
            if (v[j] < v[index_min]) {
                index_min = j;
            }
        }
        if (index_min != i) {
            aux = v[index_min];
            v[index_min] = v[i];
            v[i] = aux;
        }
    }
}

Insertion Sort

O Insertion Sort, ou ordenação por inserção, é um algoritmo de ordenação simples, eficiente quando aplicado a um pequeno número de elementos. Ele percorre um vetor da esquerda para a direita, deixando os elementos à esquerda ordenados.

public static int[] insertionSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int a = array[i];
        int j;
        for (j = i - 1; j >= 0 && array[j] > a; j--) {
            array[j + 1] = array[j];
            array[j] = a;
        }
    }
    return array;
}

Quicksort

O Quicksort adota a estratégia de divisão e conquista. Consiste em rearranjar as chaves de modo que as menores precedam as maiores, ordenando as sublistas recursivamente.

public static void quickSort(int[] v, int ini, int fim) {
    if (ini < fim) {
        int meio = partition(v, ini, fim);
        quickSort(v, ini, meio);
        quickSort(v, meio + 1, fim);
    }
}

public static int partition(int[] v, int ini, int fim) {
    int pivo = v[ini];
    int topo = ini;
    for (int i = ini + 1; i <= fim; i++) {
        if (v[i] < pivo) {
            v[topo] = v[i];
            v[i] = v[topo + 1];
            topo++;
        }
    }
    v[topo] = pivo;
    return topo;
}

Merge Sort

Sua ideia básica é criar uma sequência ordenada a partir de duas outras já ordenadas, dividindo a sequência original recursivamente.

private void mesclar(int inicio, int meio, int fim) {
    int tamanho = fim - inicio + 1;
    int[] temp = new int[tamanho];
    System.arraycopy(vetor, inicio, temp, 0, tamanho);
    int i = 0;
    int j = meio - inicio + 1;
    for (int posicao = 0; posicao < tamanho; posicao++) {
        if (j < tamanho) {
            if (i <= meio - inicio && temp[i] <= temp[j]) {
                vetor[inicio + posicao] = temp[i++];
            } else {
                vetor[inicio + posicao] = temp[j++];
            }
        } else {
            vetor[inicio + posicao] = temp[i++];
        }
    }
}