Sortowanie danych – przykład na tablicy wielowymiarowej (C++)
Sortowanie to jedna z najczęstszych operacji na danych: chcemy uporządkować rekordy rosnąco/malejąco według wybranego kryterium (np. nazwiska, wyniku, wieku, ceny). W praktyce dane często mają postać „rekordów” z wieloma polami – można je zapisać jako:
tablicę struktur (bardziej „C++-owo”), albo
tablicę wielowymiarową (2D), gdzie każdy wiersz to rekord, a kolumny to pola.
W tym przykładzie użyjemy tablicy 2D int dane[N][M], gdzie:
dane[i][0] = ID
dane[i][1] = wynik (po nim sortujemy)
dane[i][2] = wiek (dodatkowe pole)
Na czym polega sortowanie bąbelkowe?
Sortowanie bąbelkowe (bubble sort) działa tak:
Przechodzi po tablicy i porównuje sąsiadujące elementy.
Jeśli są w złej kolejności, zamienia je miejscami.
Po jednej pełnej rundzie największa wartość „wypływa” na koniec (jak bąbelek).
Powtarza rundy, aż całość będzie posortowana.
To algorytm prosty do nauki i debugowania, ale ma słabą wydajność dla dużych danych (zwykle O(n²)).
#include <iostream>
#include <iomanip>
using namespace std;
const int N = 6; // liczba rekordów (wierszy)
const int M = 3; // liczba pól (kolumn): ID, wynik, wiek
void wypiszTablice(const int t[N][M]) {
cout << " [ID, wynik, wiek]\n";
for (int i = 0; i < N; i++) {
cout << " ";
for (int j = 0; j < M; j++) {
cout << setw(4) << t[i][j] << (j < M - 1 ? " " : "");
}
cout << "\n";
}
}
int main() {
// Tablica wielowymiarowa: każdy wiersz to rekord [ID, wynik, wiek]
int dane[N][M] = {
{101, 72, 17},
{102, 55, 16},
{103, 88, 18},
{104, 55, 17},
{105, 61, 16},
{106, 90, 19}
};
cout << "Dane poczatkowe:\n";
wypiszTablice(dane);
cout << "\nSortowanie bombelkowe po kolumnie 'wynik' (rosnaco).\n\n";
// Bubble sort po kolumnie 1 (wynik)
for (int pass = 0; pass < N - 1; pass++) {
bool swapped = false;
cout << "=== Runda " << pass + 1 << " ===\n";
for (int i = 0; i < N - 1 - pass; i++) {
cout << "Porownuje wiersz " << i << " (wynik=" << dane[i][1]
<< ") z wierszem " << i + 1 << " (wynik=" << dane[i + 1][1] << ")... ";
if (dane[i][1] > dane[i + 1][1]) {
cout << "ZAMIANA!\n";
// zamiana calego rekordu (calego wiersza)
for (int col = 0; col < M; col++) {
int tmp = dane[i][col];
dane[i][col] = dane[i + 1][col];
dane[i + 1][col] = tmp;
}
swapped = true;
cout << "Stan po zamianie:\n";
wypiszTablice(dane);
} else {
cout << "OK (bez zmiany)\n";
}
}
cout << "Koniec rundy " << pass + 1 << ", stan tablicy:\n";
wypiszTablice(dane);
cout << "\n";
if (!swapped) {
cout << "Brak zamian w tej rundzie -> tablica juz posortowana. Koniec.\n";
break;
}
}
cout << "Wynik koncowy (posortowane po 'wynik' rosnaco):\n";
wypiszTablice(dane);
}
Można to też zrobić prościej
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {5, 2, 4, 1, 3};
std::sort(v.begin(), v.end());
for (const auto& x : v) {
std::cout << x << "\n";
}
}
std::vector<std::vector<int>> m = {{5,2,4},{1,3,0},{9,8,7}};
// sortuj każdy wiersz
for (auto& row : m) {
std::sort(row.begin(), row.end());
}
Pytania do artykułu / kodu (z odpowiedziami)
Co oznacza, że użyliśmy tablicy wielowymiarowej 2D int dane[N][M]?
Odp.: To tabela wierszy i kolumn. Każdy wiersz to rekord, a każda kolumna to jedno pole rekordu (np. ID, wynik, wiek).
Która kolumna w przykładzie jest kluczem sortowania i jak to widać w kodzie?
Odp.: Kolumna 1 (wynik). W porównaniu używamy dane[i][1] > dane[i+1][1].
Dlaczego podczas zamiany w bubble sort zamieniamy cały wiersz, a nie tylko wynik?
Odp.: Bo rekord musi pozostać spójny. Jeśli zamienilibyśmy tylko wyniki, to ID i wiek „przykleiłyby się” do złych osób.
Ile rund wykona bubble sort w najgorszym przypadku dla N elementów?
Odp.: Maksymalnie N-1 rund.
Po co jest warunek i < N – 1 – pass w pętli wewnętrznej?
Odp.: Po każdej rundzie największy element trafia na koniec, więc nie trzeba go już porównywać w kolejnych rundach.
Co oznacza zmienna swapped i czemu przyspiesza program?
Odp.: Informuje, czy w danej rundzie była jakakolwiek zamiana. Jeśli nie było zamian, tablica jest już posortowana i można przerwać.
Jak rozpoznać w konsoli, że nastąpiła zamiana?
Odp.: Pojawia się komunikat ZAMIANA! oraz wypisywany jest stan tablicy „Stan po zamianie”.
Jaka jest złożoność czasowa bubble sort i co to oznacza praktycznie?
Odp.: Zwykle O(n²) — dla dużych danych działa wolno, bo liczba porównań rośnie kwadratowo.
Czy bubble sort jest stabilny i co to znaczy w tym kontekście?
Odp.: Tak (w typowej wersji z warunkiem >). Stabilny znaczy, że elementy o takim samym kluczu (np. wynik=55) zachowują swoją kolejność względem siebie.
Jak zrobić sortowanie malejące w tym kodzie?
Odp.: Zmienić warunek na dane[i][1] < dane[i+1][1].
Podsumowanie
W przykładzie dane zostały zapisane jako tablica 2D, gdzie każdy wiersz to jeden rekord (ID, wynik, wiek). Następnie zastosowaliśmy sortowanie bąbelkowe, które porównuje sąsiednie rekordy i w razie potrzeby zamienia całe wiersze, aby nie pomieszać pól rekordu. Dzięki wypisywaniu informacji w konsoli można łatwo śledzić porównania, zamiany oraz stan tablicy po każdej rundzie. Bubble sort jest prosty i świetny do nauki, ale dla dużych zbiorów danych jest mało wydajny (O(n²)).