Wizualizator Algorytmów Sortowania
Animacja krok po kroku dla algorytmów: Bąbelkowe, Wstawianie, Wybór, Scalanie (MergeSort) i QuickSort z analizą złożoności O(n).
Wizualizator i Symulator Algorytmów Sortowania
Złożoność Obliczeniowa i Właściwości: Sortowanie Bąbelkowe (Bubble Sort)
Zadanie praktyczne INF.04 / INF.03 (Standard)
Porównuje kolejne pary sąsiednich elementów i zamienia je, jeśli są w niewłaściwej kolejności. W każdym pełnym przejściu największy element wędruje na koniec jak bąbelek powietrza w wodzie. Zewnętrzna pętla wykonuje się (n - 1) razy. Wewnętrzna pętla porównuje indeksy j oraz j+1, zmniejszając zasięg o liczbę ustalonych już elementów z prawej strony.
Tabela Śledzenia Przebiegów Pętli (Trace Table CKE)
Stan tablicy po kolejnych iteracjach zewnętrznej pętli – dokładnie tak, jak wymaga tego klucz odpowiedzi CKE.
| Faza / Przebieg | Zawartość tablicy po przebiegu | Porównania łączne | Zamiany / Przesunięcia | Elementy ustalone na pozycjach |
|---|---|---|---|---|
| Iteracja #1 | [20, 45, 12, 75, 35, 60, 28, 82, 18, 90] | 9 | 7 | [9]=90 |
| Iteracja #2 | [20, 12, 45, 35, 60, 28, 75, 18, 82, 90] | 17 | 12 | [9]=90, [8]=82 |
| Iteracja #3 | [12, 20, 35, 45, 28, 60, 18, 75, 82, 90] | 24 | 16 | [9]=90, [8]=82, [7]=75 |
| Iteracja #4 | [12, 20, 35, 28, 45, 18, 60, 75, 82, 90] | 30 | 18 | [9]=90, [8]=82, [7]=75, [6]=60 |
| Iteracja #5 | [12, 20, 28, 35, 18, 45, 60, 75, 82, 90] | 35 | 20 | [9]=90, [8]=82, [7]=75, [6]=60, [5]=45 |
| Iteracja #6 | [12, 20, 28, 18, 35, 45, 60, 75, 82, 90] | 39 | 21 | [9]=90, [8]=82, [7]=75, [6]=60, [5]=45, [4]=35 |
| Iteracja #7 | [12, 20, 18, 28, 35, 45, 60, 75, 82, 90] | 42 | 22 | [9]=90, [8]=82, [7]=75, [6]=60, [5]=45, [4]=35, [3]=28 |
| Iteracja #8 | [12, 18, 20, 28, 35, 45, 60, 75, 82, 90] | 44 | 23 | [9]=90, [8]=82, [7]=75, [6]=60, [5]=45, [4]=35, [3]=28, [2]=20 |
| Iteracja #9 | [12, 18, 20, 28, 35, 45, 60, 75, 82, 90] | 45 | 23 | [9]=90, [8]=82, [7]=75, [6]=60, [5]=45, [4]=35, [3]=28, [2]=20, [1]=18 |
| Faza #10 | [12, 18, 20, 28, 35, 45, 60, 75, 82, 90] | 45 | 23 | [9]=90, [8]=82, [7]=75, [6]=60, [5]=45, [4]=35, [3]=28, [2]=20, [1]=18, [0]=12 |
Wzorcowy Kod Egzaminacyjny CKE (Bąbelkowe)
Format wymagany w zadaniach praktycznych kwalifikacji INF.04 i INF.03.
// CKE INF.04 / INF.03 - Sortowanie bąbelkowe z flagą optymalizacji
#include <iostream>
#include <algorithm>
void bubbleSort(int tab[], int n) {
for (int i = 0; i < n - 1; i++) {
bool swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (tab[j] > tab[j + 1]) {
std::swap(tab[j], tab[j + 1]);
swapped = true;
}
}
if (!swapped) break; // Optymalizacja: tablica już posortowana
}
}Vademecum Egzaminacyjne CKE (INF.04 / INF.03 / INF.02)
Kluczowe pułapki w testach pisemnych, pytania o stabilność i sposoby liczenia bez komputera.
- •Bubble Sort bez flagi `swapped`: W podręcznikach często podaje się pętlę bez flagi logicznej. Wtedy Bubble Sort ZAWSZE wykonuje dokładnie n(n - 1) / 2 porównań, nawet gdy tablica od razu była posortowana (O(n²) zamiast O(n))! W arkuszach CKE sprawdzaj, czy w kodzie występuje instrukcja przerywająca pętlę.
- •Pesymistyczny przypadek QuickSort: Gdy pivotem jest zawsze element skrajny (np. ostatni lub pierwszy), a tablica jest już posortowana lub posortowana odwrotnie, drzewo rekurencji degeneruje się do zwykłej listy o głębokości n. Złożoność spada wówczas do O(n²), co grozi błędem przepełnienia stosu (Stack Overflow).
- •Indeksowanie tablicy w pseudokodzie: W zadaniach teoretycznych CKE pseudokod czasami indeksuje tablice od 1 do n (np. w notacji pseudokodu CKE/maturalnej), podczas gdy w C++ i Pythonie indeksujemy od 0 do n-1. Zwróć uwagę na warunek zakończenia pętli wewnętrznej (n - i - 1 vs n - i).
Algorytm stabilny to taki, który zachowuje pierwotną kolejność elementów o tej samej wartości (równych kluczach).
Złota reguła CKE:
- STABILNE: Bąbelkowe (Bubble), Wstawianie (Insertion), Przez scalanie (MergeSort).
- NIESTABILNE: Przez wybór (Selection Sort), Szybkie (QuickSort), Przez kopcowanie (HeapSort).
Wzór sumy ciągu arytmetycznego do liczenia porównań na kartce: dla tablicy n-elementowej w algorytmach bąbelkowym i przez wybór wykonujemy: (n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2 porównań. Dla n = 10 jest to dokładnie 45 porównań.
Chcesz poćwiczyć pytania egzaminacyjne?
Rozwiązuj pytania z oficjalnych arkuszy CKE dla kwalifikacji INF.03, INF.04 — egzamin próbny na czas, nauka działami albo losowe pytanie. Bez konta i bez opłat.