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

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

REKLAMA

Zobacz też

Algorytm – przepis, zbiór poleceń, opis ciągu operacji prowadzących do rozwiązania konkretnego problemu. Algorytm możemy również rozumieć jako funkcję przekształcającą dane wejściowe w dane wyjściowe.

Algorytm musi być skończony, czyli jego zapis ma składać się ze skończonej liczby znaków. Musi również być poprawny, czyli dla wszystkich możliwych danych wejściowych powinien zwracać prawidłowy wynik (może być nim informacja o braku rozwiązania). Algorytm musi wykazywać również własność stopu – niezależnie od danych wejściowych obliczenia algorytmu powinny dochodzić do punktu końcowego, czyli po prostu kończyć się (nie mogą np. wpadać w nieskończoną iterację). Zapis algorytmu musi być precyzyjny, bez jakichkolwiek niejasności.

→ Czytaj całość
Algorytm najbliższego sąsiada (ang. nearest neighbour algorithm, w skrócie NN) – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm wykorzystujący strategię zachłanną.
→ 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