Algorytm sortowania bąbelkowego w C++: Od teorii do praktyki

Dziś zgłębimy jedną z najprostszych, ale i jednocześnie najbardziej intuicyjnych metod sortowania danych w programowaniu – algorytm sortowania bąbelkowego w C++. Jeśli jesteście początkującymi programistami, to artykuł ten jest dla was idealny, aby poznać podstawy tego kluczowego algorytmu sortowania.

Czym jest algorytm sortowania bąbelkowego?

Algorytm sortowania bąbelkowego jest bardzo prosty. Polega on na wielokrotnym przechodzeniu przez listę danych i zamianie miejscami sąsiednich elementów, jeśli są one w złej kolejności. W ten sposób największe elementy „wypływają” na górę listy, podobnie jak pęcherzyki powietrza w wodzie, stąd nazwa „sortowanie bąbelkowe”.

Jak działa algorytm sortowania bąbelkowego?

1. Iteracja przez listę: Pierwszy krok to wielokrotne przechodzenie przez listę danych.
2. Porównywanie sąsiednich elementów: W każdej iteracji porównujemy każdy element z jego następnikiem.
3. Zamiana miejscami: Jeśli sąsiednie elementy są w złej kolejności, zamieniamy je miejscami.
4. Powtarzanie kroków 1-3: Proces jest powtarzany do momentu, gdy lista zostanie posortowana.

Przyjrzyjmy się algorytmowi sortowania bąbelkowego w działaniu. Poniżej znajduje się lista liczb nieuporządkowanych, które będziemy porządkować przy użyciu sortowania bąbelkowego:

Pierwszym krokiem jest skupienie się tylko na dwóch pierwszych liczbach, którymi w tym przykładzie są 5 i 1. Następnie porównujemy ze sobą tylko dwa elementy 5 i 1, jak pokazano na poniższym obrazku:

Następnie musisz ustalić, czy liczby w okręgu są w dobrym porządku. Jeśli nie są w odpowiedniej kolejności, zamień je miejscami. Cyfry te są ułożone w kolejności malejącej, dlatego zamieniamy je miejscami. 5 jest większe niż 1, więc 1 powinno być przed 5.

Ten sam krok wykonujemy w kolejnej iteracji tablicy. Jednak tym razem 5 jest mniejsze niż 9. Kolejność jest prawidłowa, więc w tym kroku pozostawiamy liczby na tych samych miejscach i przechodzimy do porównywania następnej pary liczb.

Kroki powtarzają się, dopóki ostatnia para liczb w tablicy nie zostanie poddana sprawdzeniu. W wyniku po pierwszym przejściu przez tablicę uszeregowanie liczb będzie wyglądać następująco:

W następnych krokach sortowanie tablicy liczb wygląda następująco:

Iteracja druga:

W rezultacie dokonaliśmy 6 pełnych przejść. Za każdym razem porównywaliśmy kolejne pary liczb ze sobą. W ostatnim przejściu (6) nie dokonaliśmy żadnej zamiany, a więc tablica była już posortowana.

Złożoność algorytmu sortowania bąbelkowego

• Średnia złożoność czasowa: O(n^2)
• Złożoność czasowa w najgorszym przypadku wynosi O(n²)
• Złożoność czasowa w najlepszym przypadku to O(n).

Do czego się przydaje taki algorytm?

Wyobraź sobie na przykład, że próbujesz uporządkować listę kontaktów w telefonie bez możliwości sortowania alfabetycznego lub sortowania produktów w witrynie e-commerce według ceny i kategorii. Jak widać na tym przykładzie, taki algorytm przydaje się w codziennym życiu.

Mimo że większość języków programowania, takich jak Java, Python i C#, ma wbudowane funkcje dla popularnych algorytmów sortowania, to nadal ważne jest zrozumienie, jak działają te algorytmy. Dzięki temu możemy podejmować świadome decyzje dotyczące tego, którego algorytmu użyć, biorąc pod uwagę jego złożoność przestrzenną i czasową, szczególnie podczas pracy z dużymi zbiorami danych. Dlatego nie warto lekceważyć skromnej funkcji sortowania, ponieważ może być kluczowa w rozwiązaniu problemu logicznego.

Przykładowy algorytm sortowania bąbelkowego w C++ wygląda następująco:

#include <iostream>
using namespace std;

// procedura sortujaca tablice
void bubble(int *tabl, int n, bool *zmiana)
{
  int temp; for (int i=0;i<n-1;i++)
    {
      if (tabl[i]>tabl[i+1])
        {
          temp = tabl[i];
            tabl[i] = tabl[i+1];
            tabl[i+1] = temp; *zmiana=true;
        }
    }
}

int main()
{
  int n;
    bool zmiana;
   
    cout << "Ile liczb mam posortowac?\n";
    cin >> n;
    int tabl[n];
   
    // pobieranie danych:
    for (int i=0;i<n;i++)
    {
      cout << "\nPodaj " << i+1 << " liczbe: ";
        cin >> tabl[i];
    }
    cout << "\n\n";
   
    // glowna petla sortujaca
    do
    {
      zmiana = false;
        bubble(tabl,n,&zmiana);
    } while (zmiana==true);
   
    // wypisywanie danych
    for (int i=0;i<n;i++)
    {
      cout << tabl[i] << " ";
    }
}

Wyjaśnienie kluczowych elementów kodu:

1. Funkcja bubble: Jest to funkcja odpowiedzialna za sortowanie tablicy metodą sortowania bąbelkowego. Przyjmuje trzy argumenty: wskaźnik do tablicy, liczbę elementów w tablicy oraz wskaźnik na zmienną typu bool, który sygnalizuje, czy nastąpiła zamiana elementów w tablicy podczas iteracji. Wewnątrz funkcji znajduje się pętla for, która przechodzi przez tablicę i zamienia sąsiadujące ze sobą elementy, jeśli są one w niewłaściwej kolejności.
2. Funkcja main: To główna funkcja programu. Inicjuje ona tablicę, pobiera od użytkownika liczbę elementów do posortowania oraz same liczby, a następnie sortuje je za pomocą funkcji bubble. Po zakończeniu sortowania, funkcja main wypisuje posortowane liczby.
3. Tablica tabl: Jest to dynamiczna tablica przechowująca liczby, które użytkownik chce posortować. Natomiast jej rozmiar jest zdefiniowany przez użytkownika podczas działania programu.
4. Pętla do-while: Jest to główna pętla sortująca, która wywołuje funkcję bubble do momentu, aż nie będzie wymagać więcej zamian elementów, co oznacza, że tablica jest już posortowana.
5. Warunek zmiana == true: Ten warunek sprawdza, czy podczas ostatniej iteracji w funkcji bubble nastąpiła przynajmniej jedna zamiana elementów w tablicy. Jeśli nie, to oznacza, że tablica jest już posortowana i pętla sortująca może być zakończona.
6. Wykorzystanie wskaźnika zmiana: Wskaźnik zmiana jest przekazywany do funkcji bubble i jest używany do monitorowania, czy w trakcie sortowania doszło do jakichkolwiek zmian w tablicy. Jeśli nie, oznacza to, że tablica jest już posortowana i pętla sortująca może zostać zakończona.

Podsumowanie: Algorytm sortowania bąbelkowego w C++

Algorytm sortowania bąbelkowego może być świetnym początkiem dla każdego programisty rozpoczynającego swoją karierę. Mimo swojej prostoty, jest on skuteczny w sortowaniu danych. Mam nadzieję, że ten artykuł pomógł Wam zrozumieć podstawy tego algorytmu i zachęcił do dalszego zgłębiania tematu. Powodzenia w nauce programowania!