Bubble Algoritmo de classificação em Java: Programa e exemplo de classificação de array

O que é a Bubble Classificar?

BubblO eSort é um algoritmo de ordenação simples baseado em comparação, que compara o primeiro elemento do array com o próximo. Se o elemento atual do array for numericamente maior que o próximo, os elementos são trocados. Da mesma forma, o algoritmo percorrerá todos os elementos do array.

O algoritmo recebe esse nome devido à maneira como o maior valor na região não ordenada sobe gradualmente até sua posição final, de forma semelhante a uma bolha subindo à superfície da água. Após a primeira passagem completa, o maior elemento ocupa o último índice. Após a segunda passagem, o segundo maior elemento é fixado em sua posição, e o processo se repete até que o array esteja totalmente ordenado.

Neste artigo, criaremos um Java programa para implementar Bubble Classifique. Verifique a saída do código, que ajudará você a entender a lógica do programa, e depois revise a versão otimizada e a análise de complexidade que se seguem.

Como é que BubblO algoritmo de ordenação funciona?

BubblO algoritmo eSort funciona percorrendo repetidamente o array. Cada passagem vai do primeiro índice até o final da região atualmente não ordenada, comparando os valores vizinhos e trocando-os.ping eles sempre que aparecem na ordem errada. Como o maior valor restante sempre se desloca para a extrema direita da região não ordenada, a região diminui exatamente uma posição após cada passagem.

O processo completo pode ser dividido em quatro etapas repetíveis:

1. Comparar: Examine o elemento no índice j-1 em relação ao elemento no índice j.
2. Swap: Se o elemento da esquerda for maior que o elemento da direita, troque os dois valores usando uma variável temporária.
3. Avançar: Mova-se uma posição para a direita e repita até chegar ao final da região não classificada.
4. Repetir: Inicie uma nova passagem sobre uma região que tenha um elemento a menos e pare após n-1 passagens ou quando uma passagem não realizar nenhuma troca.

A mesa abaixo tracEste é o array de exemplo {860, 8, 200, 9} usado no programa mais adiante nesta página. Ele mostra exatamente qual valor se estabiliza em sua posição final ao final de cada iteração.

Note que a terceira passagem realiza uma comparação, mas não uma troca. Uma implementação otimizada detecta essa condição e para imediatamente, o que representa a melhoria mais valiosa que você pode aplicar a este algoritmo.

BubblPseudocódigo do algoritmo de ordenação e

Antes de escrever Java Em termos de sintaxe, isso ajuda a expressar a lógica em pseudocódigo independente da linguagem. A versão abaixo inclui o sinalizador de saída antecipada, abrangendo assim o comportamento clássico e o otimizado.

procedure bubbleSort(array A, integer n)
    for i from 0 to n - 2 do
        swapped := false
        for j from 1 to n - i - 1 do
            // compare the adjacent pair
            if A[j - 1] > A[j] then
                swap A[j - 1] and A[j]
                swapped := true
            end if
        end for
        // no swap in a full pass means the array is sorted
        if swapped = false then
            break
        end if
    end for
end procedure

O laço externo controla o número de iterações, e o laço interno controla as comparações dentro de uma única iteração. O limite superior do laço interno é n – i – 1, pois as últimas i posições já contêm seus valores finais.

Java Programa para Implementação Bubble Classificar

O programa a seguir ordena um vetor de inteiros em ordem crescente. Instruções de impressão adicionais foram mantidas dentro dos laços propositalmente, pois a leitura passo a passo seria complexa. tracÉ a maneira mais rápida para um iniciante entender como os swaps se acumulam.

package com.guru99;

public class BubbleSort {

    public static void main(String[] args)
    {
        int arr[] = {860, 8, 200, 9};

        System.out.println("---Array BEFORE Bubble Sort---");

        printArray(arr);

        bubbleSort(arr); //sorting array elements using bubble sort

        System.out.println("---Array AFTER Bubble Sort---");

        printArray(arr);

    }

    static void bubbleSort(int[] array)
    {
        int n = array.length;
        int temp = 0;
        for(int i = 0; i < n; i++) // Looping through the array length
        {   System.out.println("Sort Pass Number " + (i + 1));
            for(int j = 1; j < (n - i); j++)
            {
                System.out.println("Comparing " + array[j - 1] + " and " + array[j]);
                if(array[j - 1] > array[j])
                {
                    //swap elements
                    temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                    System.out.println(array[j] + " is greater than " + array[j - 1]);
                    System.out.println("Swapping Elements: New Array After Swap");
                    printArray(array);
                }

            }
        }

    }

    static void printArray(int[] array){

        for(int i = 0; i < array.length; i++)
        {
            System.out.print(array[i] + " ");
        }
        System.out.println();

    }
}

Saída:

---Array BEFORE Bubble Sort---
860 8 200 9
Sort Pass Number 1
Comparing 860 and 8
860 is greater than 8
Swapping Elements: New Array After Swap
8 860 200 9
Comparing 860 and 200
860 is greater than 200
Swapping Elements: New Array After Swap
8 200 860 9
Comparing 860 and 9
860 is greater than 9
Swapping Elements: New Array After Swap
8 200 9 860
Sort Pass Number 2
Comparing 8 and 200
Comparing 200 and 9
200 is greater than 9
Swapping Elements: New Array After Swap
8 9 200 860
Sort Pass Number 3
Comparing 8 and 9
Sort Pass Number 4
---Array AFTER Bubble Sort---
8 9 200 860

Code explicação: O Classificação por bolhas O método recebe o array por referência, portanto, quem o chama vê o resultado ordenado sem nenhum valor de retorno. A variável temperatura mantém um valor durante a troca de três linhas, razão pela qual o algoritmo precisa apenas de O(1) de memória extra. A expressão n – i Na condição do laço interno, garante-se que as posições já ordenadas na cauda nunca sejam revisitadas.

Estratégias Bubble Classificar programa em Java

O programa acima sempre realiza n-1 iterações, mesmo quando o array é ordenado antecipadamente. Adicionar um único parâmetro booleano corrige essa ineficiência. Se uma iteração completa terminar sem nenhuma troca, o array estará garantido como ordenado e o loop externo poderá ser interrompido imediatamente.

package com.guru99;

public class OptimizedBubbleSort {

    public static void main(String[] args) {
        int arr[] = {5, 12, 33, 47, 58};
        bubbleSort(arr);
        System.out.println(java.util.Arrays.toString(arr));
    }

    static void bubbleSort(int[] array) {
        int n = array.length;
        int passes = 0;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 1; j < n - i; j++) {
                if (array[j - 1] > array[j]) {
                    int temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                    swapped = true;
                }
            }
            passes++;
            // Early exit: the array is already sorted
            if (!swapped) {
                break;
            }
        }
        System.out.println("Passes executed: " + passes);
    }
}

Saída:

Passes executed: 1
[5, 12, 33, 47, 58]

Como o array de entrada já estava ordenado, a versão otimizada terminou após uma única passagem em vez de quatro. Em dados quase ordenados, essa mudança transforma uma carga de trabalho quadrática em uma quase linear, que é o principal motivo. BubblO operador e Sort ainda aparece em código real de tempos em tempos.

Complexidade de tempo e complexidade de espaço de Bubble Classificar

A complexidade descreve como o tempo de execução aumenta à medida que o tamanho da entrada aumenta. Bubble A contagem de comparações na versão não otimizada é fixa em n(n-1)/2, o que a coloca firmemente na classe quadrática.

Como cada troca ocorre dentro do array original e apenas uma variável temporária é utilizada, Bubble Sort é um algoritmo in-place com espaço auxiliar O(1). É também uma ordenação estável, o que significa que dois registros que possuem a mesma chave mantêm sua ordem relativa original após a ordenação.

Vantagens e desvantagens de Bubble Classificar

Compreender os dois lados da questão ajuda a decidir quando o algoritmo é uma escolha aceitável e quando deve ser substituído.

Vantagens

• Simplicidade: A lógica cabe em aproximadamente dez linhas, o que facilita a escrita correta em situações de entrevista.
• Operação no local: Nenhuma matriz auxiliar é alocada, portanto o uso de memória não aumenta com o tamanho da entrada.
• Estabilidade: Chaves iguais mantêm sua ordem original, o que é importante ao classificar registros por um campo secundário.
• Detecção antecipada de saída: O indicador "swipped" identifica um array já ordenado em uma única passagem.

Desvantagens

• Crescimento quadrático: Ordenar 10,000 elementos requer quase 50 milhões de comparações no pior caso.
• Excessivo escreve: O algoritmo realiza muito mais trocas do que o Selection Sort, que é custoso em termos de memória e possui operações de escrita lentas.
• Baixa escalabilidade: Em cargas de trabalho de produção, quase sempre se prefere o Quicksort, o Merge Sort ou o método Arrays.sort integrado.

BubblClassificação e versus outras formas de classificação Algorithms

A tabela abaixo compara BubblClassifique com as técnicas de classificação que os iniciantes conhecerão a seguir, para que você possa ver exatamente onde cada uma se destaca.

BubblO e Sort e o Insertion Sort compartilham o mesmo melhor caso linear, mas o Insertion Sort realiza menos trocas em dados parcialmente ordenados. O Selection Sort sempre realiza exatamente n-1 trocas, o que o torna...tracO Quicksort é eficaz quando as operações de escrita são custosas, embora sacrifique a estabilidade. Para qualquer matriz com mais de algumas centenas de elementos, o Quicksort ou o Heap Sort são as escolhas corretas.

Uma vez que você esteja familiarizado com os padrões de percurso em arrays usados ​​aqui, a mesma estrutura de loop aparece em muitos exercícios clássicos, como o Série de Fibonacci em Java e Java programa palíndromo. Revvendo Java matrizes e quanto maior Java tutorial fortalecerá os fundamentos dos quais este algoritmo depende.

Perguntas Frequentes