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

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

REKLAMA

Zobacz też

Sortowanie – zagadnienie polegające na uporządkowaniu elementów zbioru rosnąco lub malejąco według pewnego klucza. Zagadnienie to, ze względu na częstość występowania, jest bardzo istotne dla informatyki. Istnieje wiele różnych algorytmów realizujących sortowanie.

→ Czytaj całość

Algorytm Edmondsa-Karpa – algorytm wyszukiwania maksymalnego przepływu w sieci przepływowej. Jest to przypadek szczególny algorytmu Forda-Fulkersona.

W algorytmie Edmondsa-Karpa ścieżka powiększająca wyznaczana jest za pomocą przeszukiwania grafu wszerz. Dzięki temu w każdej iteracji algorytmu dołączana jest zawsze najkrótsza (pod względem liczby krawędzi) ścieżka powiększająca. W metodzie Forda-Fulkersona sposób wyznaczania ścieżki powiększającej jest dowolny.

→ Czytaj całość

Wyznaczanie maksymalnego przepływu – problem obliczeniowy polegający na wyznaczeniu maksymalnego przepływu w sieci przepływowej.

Sieć przepływowa jest skierowanym grafem prostym. Każdy łuk (krawędź skierowana w grafie) ma swoją nieujemną wagę, która oznacza maksymalny dopuszczalny przepływ w tym łuku. Na potrzeby tego artykułu nazwijmy rzeczy przepływające przez sieć danymi. Jeden z wierzchołków sieci jest źródłem, z którego wypływają przesyłane dane. Inny z wierzchołków to ujście, do którego te dane wpływają. Zakłada się ponadto, że dla każdego z pozostałych wierzchołków istnieje ścieżka ze źródła do ujścia przechodząca przez ten wierzchołek.

Przepływem w sieci nazywamy przyporządkowanie każdemu łukowi pewnej wartości, która oznacza liczbę danych aktualnie przesyłanych przez ten łuk. Wartości te muszą spełniać następujące warunki:

  • Wartość przyporządkowana krawędzi musi być mniejsza lub równa jej wadze (warunek przepustowości).
  • Do każdego wierzchołka (poza źródłem i ujściem) musi wpływać tyle samo danych, ile z niego wypływa (warunek zachowania przepływu).

Omawiany problem polega na dobraniu takiego przepływu, aby liczba danych wypływających ze źródła (i zarazem wpływających do ujścia) była jak największa.

→ Czytaj całość
Polityka prywatnościKontakt