Sortowanie bąbelkowe w C++ — śledzenie algorytmu i liczenie zamian

Sortowanie bąbelkowe porównuje sąsiednie elementy i zamienia je, jeśli stoją w złej kolejności; po każdym przebiegu największy element „wypływa” na koniec. Jest powolne, ale doskonale pokazuje, jak działa algorytm krok po kroku. Na lekcji uczniowie śledzą kolejne przebiegi, liczą porównania i zamiany i sprawdzają przypadki skrajne.

Scenariusz jest przeznaczony na 45 minut dla klasy po lekcjach o wyszukiwaniu w C++ i funkcjach. Ten sam algorytm w Pythonie omawia lekcja o sortowaniu bąbelkowym. Dane są wpisane w kodzie.

Przygotowanie stanowisk

Potrzebny jest kompilator C++ (na przykład g++ z MinGW-w64, Code::Blocks lub Dev-C++) i edytor tekstu. Rozpakuj pakiet z sekcji materiałów do osobnego folderu. W folderze projektu skompiluj program poleceniem g++ -std=c++17 -Wall start.cpp -o program, a potem uruchom go: ./program (Linux, macOS) albo program.exe (Windows). W środowisku z przyciskiem Build and Run (Code::Blocks) wystarczy otworzyć plik .cpp i je użyć. Rozwiązanie jest w pliku rozwiazanie.cpp, zadanie dla chętnych — w rozszerzenie.cpp.

Cele i plan lekcji

Po zajęciach uczeń potrafi:

• zapisać dwie zagnieżdżone pętle sortowania bąbelkowego i swap;
• prześledzić zawartość tablicy po każdym przebiegu;
• policzyć porównania i zamiany;
• dodać wczesne zakończenie, gdy w przebiegu nie było zamian;
• wskazać przypadek najgorszy (dane odwrócone) i najlepszy (posortowane).

Jak to działa

W jednym przebiegu porównujemy pary sąsiednie v[i] i v[i + 1] i zamieniamy je (swap), jeśli v[i] > v[i + 1]. Po pierwszym przebiegu największy element jest na końcu, po drugim — dwa największe, więc w kolejnych przebiegach pętla wewnętrzna może być coraz krótsza (i < n - 1 - przebieg).

Wczesne zakończenie

Jeśli w całym przebiegu nie było żadnej zamiany, tablica jest już posortowana i można przerwać. Dla danych posortowanych wystarczy jeden przebieg.

Koszt

Bez wczesnego zakończenia liczba porównań to zawsze n(n−1)/2 (dla 5 elementów 10). Liczba zamian zależy od danych: dla posortowanych 0, dla ułożonych odwrotnie — również n(n−1)/2. Dlatego sortowanie bąbelkowe stosuje się głównie w nauce.

Zadania

Zadanie 1. Śledzenie. Dla {5, 1, 4, 2, 8} wypisz tablicę po każdym przebiegu oraz liczbę zamian, porównań i przebiegów.

Zadanie 2. Wczesne zakończenie. Posortuj te same dane bez wczesnego zakończenia i z nim; porównaj liczby porównań i przebiegów.

Zadanie 3. Przypadki skrajne. Sprawdź dane posortowane {1, 2, 3, 4, 5} i odwrócone {5, 4, 3, 2, 1}: ile zamian, porównań i przebiegów?

Dla chętnych: posortuj alfabetycznie pięć imion (string można porównywać operatorem >; plik rozszerzenie.cpp).

Rozwiązanie i wyniki

#include <iostream>
#include <vector>
using namespace std;

void wypisz(const vector<int>& v) {
    for (int x : v) {
        cout << x << " ";
    }
    cout << endl;
}

// Zwraca liczbe zamian; porownania i przebiegi przekazuje przez referencje.
int babelkowe(vector<int> v, int& porownania, int& przebiegi, bool pokaz, bool wczesnyKoniec) {
    int zamiany = 0;
    porownania = 0;
    przebiegi = 0;
    int n = static_cast<int>(v.size());
    for (int przebieg = 0; przebieg < n - 1; przebieg++) {
        bool bylaZamiana = false;
        przebiegi++;
        for (int i = 0; i < n - 1 - przebieg; i++) {
            porownania++;
            if (v[i] > v[i + 1]) {
                swap(v[i], v[i + 1]);
                zamiany++;
                bylaZamiana = true;
            }
        }
        if (pokaz) {
            cout << "po przebiegu " << przebiegi << ": ";
            wypisz(v);
        }
        if (wczesnyKoniec && !bylaZamiana) {
            break;
        }
    }
    return zamiany;
}

int main() {
    int por;
    int prz;

    // Zadanie 1: sledzenie algorytmu
    vector<int> dane = {5, 1, 4, 2, 8};
    cout << "start: ";
    wypisz(dane);
    int z = babelkowe(dane, por, prz, true, true);
    cout << "zamian: " << z << ", porownan: " << por << ", przebiegow: " << prz << endl;

    // Zadanie 2: z wczesnym zakonczeniem i bez
    z = babelkowe(dane, por, prz, false, false);
    cout << "bez wczesnego konca: zamian " << z << ", porownan " << por << ", przebiegow " << prz << endl;
    z = babelkowe(dane, por, prz, false, true);
    cout << "z wczesnym koncem: zamian " << z << ", porownan " << por << ", przebiegow " << prz << endl;

    // Zadanie 3: przypadki skrajne
    vector<int> posortowane = {1, 2, 3, 4, 5};
    z = babelkowe(posortowane, por, prz, false, true);
    cout << "posortowane: zamian " << z << ", porownan " << por << ", przebiegow " << prz << endl;
    vector<int> odwrotne = {5, 4, 3, 2, 1};
    z = babelkowe(odwrotne, por, prz, false, true);
    cout << "odwrotne: zamian " << z << ", porownan " << por << ", przebiegow " << prz << endl;
    return 0;
}

Program wypisze:

start: 5 1 4 2 8 
po przebiegu 1: 1 4 2 5 8 
po przebiegu 2: 1 2 4 5 8 
po przebiegu 3: 1 2 4 5 8 
zamian: 4, porownan: 9, przebiegow: 3
bez wczesnego konca: zamian 4, porownan 10, przebiegow 4
z wczesnym koncem: zamian 4, porownan 9, przebiegow 3
posortowane: zamian 0, porownan 4, przebiegow 1
odwrotne: zamian 10, porownan 10, przebiegow 4

Zadanie dla chętnych (rozszerzenie.cpp):

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    vector<string> imiona = {"Zofia", "Adam", "Marek", "Ola", "Ewa"};
    int n = static_cast<int>(imiona.size());
    for (int przebieg = 0; przebieg < n - 1; przebieg++) {
        for (int i = 0; i < n - 1 - przebieg; i++) {
            if (imiona[i] > imiona[i + 1]) {
                swap(imiona[i], imiona[i + 1]);
            }
        }
    }
    for (const string& s : imiona) {
        cout << s << " ";
    }
    cout << endl;
    return 0;
}

Wynik:

Adam Ewa Marek Ola Zofia 

Programy kompilowano kompilatorem g++ 15.2 z opcjami -std=c++17 -Wall -Wextra, bez ostrzeżeń.

Typowe błędy

Pytania kontrolne i punktacja

1. Co jest na końcu tablicy po pierwszym przebiegu?
2. Ile porównań wykona sortowanie bąbelkowe bez wczesnego zakończenia dla 5 elementów?
3. Kiedy sortowanie wykona najwięcej zamian?

Odpowiedzi: Największy element. Dziesięć, bo n(n−1)/2 = 5·4/2. Gdy dane są ułożone odwrotnie (malejąco) — wtedy zamian jest tyle samo co porównań.

Proponowana punktacja (razem 10 punktów): zadanie 1 — przebiegi i liczniki 3 pkt; zadanie 2 — porównanie dwóch wersji 2 pkt; zadanie 3 — przypadki skrajne 3 pkt; pytania kontrolne 2 pkt. Zadanie dla chętnych nie jest wymagane do pełnej oceny.

Materiały do pobrania

• Pakiet C++: materiały do lekcji, rozwiązanie i karta pracy
• Karta pracy ucznia — otwórz i wydrukuj

Rozpakuj ZIP przed otwarciem plików. Materiały są dostępne bez logowania; publiczne rozwiązanie służy nauce i samodzielnemu sprawdzeniu, a nie poufnemu sprawdzianowi.

Co dalej?

Następny krok to liczby pierwsze i sito Eratostenesa. Ten materiał rozwija dział o algorytmach w kursie C++ w TablicaPro, gdzie znajdziesz prezentacje, ćwiczenia i testy do prowadzenia lekcji.

Źródła techniczne: Sortowanie bąbelkowe w Wikipedii oraz std::swap w cppreference.com. Zobacz też lekcję o wyszukiwaniu w C++.