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: +5 Tak Nie
Liczba głosów: 7.

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

REKLAMA

Zobacz też

Algorytm Kruskala – algorytm wyznaczający minimalne drzewo rozpinające. Algorytm ten wykorzystuje strategię zachłanną, zawsze zwraca rozwiązanie optymalne.

→ Czytaj całość

Algorytmy zachłanne (ang. greedy algorithms) – algorytmy podejmujące w każdym kroku taką decyzję, która w danej chwili wydaje się najkorzystniejsza. Inaczej mówiąc, algorytmy zachłanne dokonują zawsze wyborów lokalnie optymalnych licząc, że doprowadzi to do znalezienia rozwiązania globalnie optymalnego. W ogólnym przypadku algorytmy zachłanne nie zawsze znajdują rozwiązanie optymalne. Są one zatem podzbiorem algorytmów heurystycznych. Jednocześnie są to algorytmy deterministyczne – nie ma w nich losowości.

Bardzo prostym przykładem algorytmu zachłannego może być szukanie najwyższego punktu na określonym obszarze poprzez przesuwanie się zawsze w kierunku największego nachylenia (nigdy się nie cofając ani nie rozpatrując kilku wariantów drogi). Jak widać, w ten sposób prawdopodobnie dojdziemy do wierzchołka położonego najbliżej od punktu początkowego, który niekoniecznie będzie najwyższym.

→ Czytaj całość

Dziel i zwyciężaj (ang. divide and conquer) – technika projektowania algorytmów polegająca na podejściu rekurencyjnym. W technice tej problem dzielony jest na mniejsze podproblemy, te podproblemy na jeszcze mniejsze podproblemy, aż dojdzie się do przypadków trywialnych (np. posortowanie jednoelementowej tablicy, obliczenie silni z 1).

Jeśli rozpatrywany problem wymaga podzielenia na podproblemy, jest on określany jako przypadek rekurencyjny. Jeśli mamy do czynienia z przypadkiem trywialnym, jest to przypadek bazowy. Tworząc algorytm wykorzystujący metodę dziel i zwyciężaj musimy ustalić:

  • Jak rozwiązać przypadek bazowy (trywialny).
  • Jak wyznaczyć rozwiązanie problemu, mając dostępne rozwiązania podproblemów.

Przykładem algorytmu opartego na tej metodzie jest sortowanie przez scalanie.

→ Czytaj całość
Polityka prywatnościKontakt