Sortowanie bąbelkowe

Tutorial
Na ten temat mamy również tutorial „Sortowanie bąbelkowe”, który ilustruje działanie algorytmu krok po kroku. Zapraszamy do zapoznania się z nim!
Sortowanie bąbelkowe (1) Przykład sortowania bąbelkowego
Sortowanie bąbelkowe (ang. bubble sort) – prosty algorytm sortowania polegający na porównywaniu za sobą sąsiednich elementów. Złożoności czasowa algorytmu wynosi O(n2).

Działanie algorytmu

W pierwszym kroku algorytm porównuje pierwszy element ciągu z drugim i zamienia je ze sobą miejscami, jeśli są w nieprawidłowej kolejności. Następnie w analogiczny sposób porównywany jest drugi element z trzecim, trzeci z czwartym itd. Po dojściu w ten sposób do końca ciągu mamy pewność, że największy (lub najmniejszy, jeśli sortujemy malejąco) element znajduje się na końcu ciągu. W kolejnych krokach ponownie porównujemy ze sobą element pierwszy z drugim, drugi z trzecim itd., tym razem kończąc jednak na przedostatnim elemencie. Przeglądanie ciągu powtarzamy wielokrotnie, za każdym razem wykonując o jedno porównanie mniej. Algorytm kończy się, gdy w trakcie ostatniego przeglądania wykonane zostanie tylko jedno porównanie – wówczas wszystkie elementy na pewno są na swoich miejscach.

Przykładowy kod źródłowy w języku C jest umieszczony poniżej. Kod ten realizuje sortowanie rosnące.

void sortowanie_babelkowe(int* tab, int n)
{
    int i, j, t;

    for (i = n-1; i > 0; --i)
    {
        for (j = 0; j < i; ++j) 
        {
            if (tab[j] > tab[j+1])
            {
                t = tab[j];
                tab[j] = tab[j+1];
                tab[j+1] = t;
            }
        } 
    } 
}

Złożoność czasowa

W trakcie pierwszego przeglądania ciągu zostaje wykonanych n-1 porównań, gdzie n jest liczbą elementów do posortowania. W każdym kolejnym przeglądaniu wykonuje się o jedno porównanie mniej. Łączna liczba porównań wynosi zatem (n-1)+(n-2)+…+1, czyli (n-1)*n/2. Złożoność czasowa algorytmu jest więc kwadratowa.

Warto zauważyć, że ilość wymaganych porównań nie zależy od stopnia początkowego ułożenia elementów w ciągu. Nawet jeśli będziemy sortowali ciąg posortowany już na początku, to algorytm i tak będzie musiał wykonać wszystkie porównania. Średnia złożoność czasowa tego algorytmu jest zatem równa pesymistycznej.

Aby nieco przyspieszyć algorytm, można zapamiętywać, czy w trakcie ostatniego przeglądania ciągu wystąpiła choć jedna zamiana elementów. Jeśli nie, wszystkie elementy na pewno są już na swoich miejscach i można przerwać wykonywanie algorytmu.

Algorytm sortowania bąbelkowego jest intuicyjny (i w związku z tym jest dość popularny), ale stosunkowo mało wydajny. Jeśli zamierzamy zastosować jakiś prosty i szybki w implementacji algorytm, warto rozważyć zastosowanie równie prostego sortowania przez wstawianie.

Ocena: +2 Tak Nie
Liczba głosów: 2.

Dodano: 26 września 2016 16:15, ostatnia edycja: 24 marca 2017 10:37.

REKLAMA

Zobacz też

Metoda przyrostowa – technika projektowania algorytmów polegająca na dodawaniu do rozwiązania kolejnych elementów z danych wejściowych. Przykładem algorytmu opartego na tej metodzie jest sortowanie przez wstawianie, gdzie kolejne elementy są wstawiane do posortowanej części tablicy.

Jest to metoda prosta, jednak sprawdza się tylko dla niektórych problemów obliczeniowych.

→ Czytaj całość

Algorytm memetyczny – algorytm będący połączeniem algorytmu genetycznego i metod lokalnej optymalizacji. Czasami określany również jako hybrydowy algorytm ewolucyjny.

→ Czytaj całość

Problem wydawania reszty (ang. change-making problem) – problem obliczeniowy polegający na tym, aby mając określony zbiór nominałów wyrazić daną kwotę za pomocą jak najmniejszej liczby monet. Jest to szczególny przypadek problemu plecakowego.

→ Czytaj całość
Polityka prywatnościKontakt