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

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

REKLAMA

Zobacz też

Metoda Forda-Fulkersona – algorytm służący do wyznaczania maksymalnego przepływu. Jest to algorytm bardzo ogólny, dlatego często nie jest nazywany algorytmem, a metodą. Popularną implementacją tej metody jest algorytm Edmondsa-Karpa. Algorytm można opisać następująco:

  1. Wyznacz sieć residualną (opis sieci residualnej znajduje się w dalszej części artykułu).
  2. Znajdź w sieci residualnej dowolną ścieżkę powiększającą.
  3. Jeśli nie udało się wyznaczyć żadnej ścieżki powiększającej, zakończ działanie algorytmu.
  4. W przeciwnym razie zwiększ przepływ w sieci (w sposób opisany w dalszej części artukułu) i wróć do punktu 1.
→ Czytaj całość

Sortowanie przez wstawianie (ang. insertion sort) – prosty algorytm sortowania polegający na wstawianiu kolejnych elementów ciągu we właściwe miejsca. Złożoności czasowa algorytmu wynosi O(n2). Jest to algorytm realizujący metodę przyrostową.

→ Czytaj całość

Bogosort – bardzo słaby algorytm sortowania oparty na metodzie prób i błędów. Polega na ustawianiu elementów w losowej kolejności i sprawdzaniu, czy są posortowane. Średnia złożoność tego algorytmu jest rzędu silnia, a w przypadku pesymistycznym algorytm będzie działał w nieskończoność.

Algorytm występuje też w nieco ulepszonej wersji, w której nie sprawdza się wielokrotnie tego samego ustawienia. Wówczas algorytm daje gwarancję znalezienia rozwiązania, jednak jego złożoność czasowa nadal jest rzędu silnia (w przypadku pesymistycznym trzeba sprawdzić wszystkie permutacje zbioru).

Ze względu na bardzo dużą złożoność czasową bogosort nie nadaje się do praktycznych zastosowań. Istnieją proste w implementacji, a znacznie wydajniejsze algorytmy sortujące, np. sortowanie przez wstawianie.

→ Czytaj całość
Polityka prywatnościKontakt