Bubble Sortuj algorytm w Java: Program sortowania tablic i przykład

Czym jest Bubble Sortować?

BubblSortowanie e-mail to prosty algorytm sortowania oparty na porównaniach, który porównuje pierwszy element tablicy z kolejnym. Jeśli bieżący element tablicy jest liczbowo większy od kolejnego, elementy są zamieniane miejscami. Analogicznie, algorytm przeszukuje cały element tablicy.

Nazwa algorytmu wzięła się od sposobu, w jaki największa wartość w niesortowanym obszarze stopniowo wzrasta do pozycji końcowej, niczym bańka unosząca się na powierzchnię wody. Po pierwszym pełnym przejściu największy element zajmuje ostatni indeks. Po drugim przejściu drugi co do wielkości element zostaje zablokowany, a proces powtarza się, aż tablica zostanie w pełni uporządkowana.

W tym artykule utworzymy Java program do wdrożenia BubblSortuj. Sprawdź wynik kodu, który pomoże Ci zrozumieć logikę programu, a następnie przejrzyj zoptymalizowaną wersję i analizę złożoności.

W jaki sposób BubblCzy algorytm sortowania działa?

BubblSortowanie e działa poprzez wielokrotne przejścia przez tablicę. Każde przejście przechodzi od pierwszego indeksu do końca aktualnie niesortowanego obszaru, porównując sąsiednie wartości i zamieniając je.ping je za każdym razem, gdy pojawiają się w niewłaściwej kolejności. Ponieważ największa pozostała wartość zawsze przesuwa się na skrajną prawą stronę niesortowanego obszaru, obszar zmniejsza się o dokładnie jedną pozycję po każdym przejściu.

Cały proces można podzielić na cztery powtarzalne kroki:

1. Porównać: Porównaj element o indeksie j-1 z elementem o indeksie j.
2. Zamiana: Jeżeli lewy element jest większy od prawego, zamień te dwie wartości, używając zmiennej tymczasowej.
3. Postęp: Przesuń się o jedną pozycję w prawo i powtarzaj tę czynność, aż dotrzesz do końca nieposortowanego regionu.
4. Powtarzać: Rozpocznij nowe przejście nad regionem krótszym o jeden element i zakończ po n-1 przejściach lub gdy przejście nie wykona żadnych zamian.

Tabela poniżej tracTo tablica przykładowa {860, 8, 200, 9} używana w programie dalej na tej stronie. Pokazuje ona dokładnie, która wartość ustala się na swojej pozycji końcowej na końcu każdego przebiegu.

Zauważ, że trzecie przejście wykonuje porównanie, ale nie zamianę. Zoptymalizowana implementacja wykrywa ten warunek i natychmiast się zatrzymuje, co jest najcenniejszą poprawą, jaką można zastosować w tym algorytmie.

BubblPseudokod algorytmu sortowania

Przed napisaniem Java Składnia pomaga wyrazić logikę w pseudokodzie neutralnym językowo. Poniższa wersja zawiera flagę wczesnego wyjścia, więc obejmuje zarówno klasyczne, jak i zoptymalizowane zachowanie.

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

Pętla zewnętrzna kontroluje liczbę przebiegów, a pętla wewnętrzna kontroluje porównania w jednym przebiegu. Górna granica pętli wewnętrznej wynosi n – i – 1, ponieważ ostatnie i pozycji zawiera już swoje wartości końcowe.

Java Program do wdrożenia Bubble Sortuj

Poniższy program sortuje tablicę liczb całkowitych w kolejności rosnącej. Dodatkowe instrukcje drukowania zostały celowo umieszczone wewnątrz pętli, ponieważ odczytywanie pętli z pominięciem tracTo najszybszy sposób dla początkującego, aby zrozumieć, w jaki sposób kumulują się swapy.

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();

    }
}

Wyjście:

---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 wyjaśnienie: sortowanie bąbelkowe Metoda otrzymuje tablicę przez referencję, więc osoba wywołująca widzi posortowany wynik bez żadnej wartości zwracanej. Zmienna temp przechowuje jedną wartość podczas zamiany trzech linii, dlatego algorytm potrzebuje tylko O(1) dodatkowej pamięci. Wyrażenie n – i w warunku pętli wewnętrznej zagwarantowane jest, że już posortowane pozycje na ogonie nigdy nie zostaną ponownie odwiedzone.

Zoptymalizowana Bubble Sortuj programy w Java

Powyższy program zawsze wykonuje n-1 przebiegów, nawet gdy tablica zostanie posortowana zbyt wcześnie. Dodanie jednej flagi boolowskiej rozwiązuje ten problem. Jeśli pełne przejście zakończy się bez ani jednej zamiany, tablica z pewnością zostanie posortowana, a pętla zewnętrzna może zostać natychmiast zatrzymana.

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);
    }
}

Wyjście:

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

Tablica wejściowa była już posortowana, więc zoptymalizowana wersja zakończyła się po jednym przejściu zamiast czterech. W przypadku danych niemal posortowanych ta zmiana przekształca obciążenie kwadratowe w niemal liniowe, co jest głównym powodem Bubble Sort od czasu do czasu pojawia się w prawdziwym kodzie.

Złożoność czasowa i przestrzenna Bubble Sortuj

Złożoność opisuje, jak czas wykonania rośnie wraz ze wzrostem rozmiaru danych wejściowych. BubblLiczba porównań w wersji niezoptymalizowanej jest ustalona na n(n-1)/2, co umiejscawia ją zdecydowanie w klasie kwadratowej.

Ponieważ każda wymiana odbywa się wewnątrz oryginalnej tablicy i używana jest tylko jedna zmienna tymczasowa, BubblSortowanie to algorytm „in-place” z przestrzenią pomocniczą O(1). Jest to również sortowanie stabilne, co oznacza, że ​​dwa rekordy zawierające ten sam klucz zachowują swoją pierwotną kolejność względną po sortowaniu.

Zalety i wady Bubble Sortuj

Zrozumienie obu stron pomoże Ci podjąć decyzję, kiedy algorytm jest akceptowalnym wyborem, a kiedy należy go zastąpić.

Zalety

• Prostota: Logika tekstu mieści się w około dziesięciu linijkach, co ułatwia jego poprawne napisanie w warunkach wywiadu.
• Operacje na miejscu: Nie przydzielono żadnej tablicy pomocniczej, więc użycie pamięci nie rośnie wraz z rozmiarem danych wejściowych.
• Stabilność: Jednakowe klucze zachowują swoją oryginalną kolejność, co ma znaczenie przy sortowaniu rekordów według pola pomocniczego.
• Wczesne wykrywanie wyjścia: Flaga „swapped” identyfikuje tablicę, która została już posortowana w jednym przejściu.

Wady

• Wzrost kwadratowy: Posortowanie 10 000 elementów w najgorszym przypadku wymagałoby wykonania blisko 50 milionów porównań.
• Nadmierny pisze: Algorytm ten wykonuje o wiele więcej zamian niż sortowanie przez wybór, które jest kosztowne pod względem wykorzystania pamięci i ma powolne operacje zapisu.
• Słaba skalowalność: W przypadku obciążeń produkcyjnych prawie zawsze preferowane są metody Quicksort, Merge Sort lub wbudowana metoda Arrays.sort.

BubblSortowanie e-mailem a inne sortowanie Algorithms

Poniższa tabela porównuje Bubble Sortuj za pomocą technik sortowania, z którymi początkujący zetkną się później, dzięki czemu dokładnie zobaczysz, gdzie każda z nich wygrywa.

BubblSortowanie i sortowanie przez wstawianie mają ten sam najlepszy liniowy przypadek, ale sortowanie przez wstawianie wykonuje mniej zamian na częściowo posortowanych danych. Sortowanie przez wybieranie zawsze wykonuje dokładnie n-1 zamian, co oznacza, żetractywny, gdy zapisy są kosztowne, choć kosztem stabilności. W przypadku tablic większych niż kilkaset elementów, właściwym wyborem jest sortowanie szybkie (Quicksort) lub sortowanie kopcowe (Heap Sort).

Gdy już oswoisz się ze wzorcami przechodzenia przez tablicę używanymi tutaj, ta sama struktura pętli pojawia się w wielu klasycznych ćwiczeniach, takich jak Ciąg Fibonacciego w Java i Java program palindromowy. Revpatrzenie Java tablice i szerszy Java Tutorial wzmocni podstawy, na których opiera się ten algorytm.

FAQ