Algorytmy w akcji
Algorytmy w akcji to darmowa interaktywna symulacja ze StudyFi Lab. Działa bezpośrednio w przeglądarce, bez rejestracji i bez instalacji.
Sortowanie i wyszukiwanie krok po kroku
Eksperymenty
Sortowanie bąbelkowe
Sortowanie bąbelkowe porównuje sąsiednie elementy i zamienia je, gdy stoją w złej kolejności. Po każdym przebiegu największy element „wypływa” na koniec, więc nieposortowana część się skraca. Jeśli przebieg nie wykona żadnej zamiany, tablica jest posortowana. W najgorszym przypadku potrzeba n(n−1)/2 porównań, czyli O(n²).
Spróbuj: Wybierz odwróconą kolejność i porównaj liczbę porównań z n(n−1)/2. Potem spróbuj prawie posortowanej tablicy — skończy po kilku przebiegach.
Sortowanie przez wstawianie
Sortowanie przez wstawianie działa jak układanie kart w ręce: lewa część jest już posortowana, a każdy kolejny element (key) przesuwa się w lewo, aż trafi na mniejszy. Większe elementy przesuwają się po drodze o jedno miejsce w prawo. Dla losowych danych to O(n²), ale dla prawie posortowanych niemal O(n) — posortowana tablica wymaga tylko n−1 porównań.
Spróbuj: Uruchom je na prawie posortowanej tablicy, a potem na odwróconej. Ile razy więcej przesunięć potrzebuje odwrócona?
Sortowanie przez scalanie
Sortowanie przez scalanie dzieli tablicę na połowy, sortuje każdą w ten sam sposób (rekurencja), a potem scala dwie posortowane połowy: zawsze bierze mniejszy z dwóch pierwszych elementów. Dzielenie na pół daje log₂ n poziomów, a każdy poziom przetwarza wszystkie n elementów, więc złożoność czasowa to zawsze O(n log n). Przy remisie bierze element z lewej, dlatego jest stabilne.
Spróbuj: Spróbuj odwróconej, a potem prawie posortowanej tablicy tej samej wielkości. Liczba porównań prawie się nie zmienia — kolejność danych ma niewielkie znaczenie.
Sortowanie szybkie
Sortowanie szybkie wybiera pivot — tutaj ostatni element fragmentu (podział Lomuto) — i przestawia fragment tak, by mniejsze elementy były po lewej, a pozostałe po prawej. Pivot trafia wtedy na swoje ostateczne miejsce, a obie części sortuje się tak samo. Średnio to O(n log n), ale gdy pivot dzieli źle (np. dla tablicy już posortowanej lub odwróconej), spada do O(n²).
Spróbuj: Porównaj losowe dane z odwróconymi. W odwróconej tablicy pivot jest zawsze największy albo najmniejszy — zobacz, jak skacze liczba porównań.
Wyszukiwanie liniowe a binarne
Wyszukiwanie liniowe sprawdza elementy po kolei, więc w najgorszym przypadku potrzebuje n kroków — O(n). Wyszukiwanie binarne działa tylko na posortowanej tablicy: patrzy na środek i zależnie od wyniku odrzuca całą połowę. Po każdym kroku zostaje najwyżej połowa, dlatego wystarczy najwyżej ⌈log₂(n+1)⌉ kroków — O(log n). Dla 40 elementów to 6 kroków zamiast 40.
Spróbuj: Ustaw 40 elementów i szukaj ostatniej wartości. Potem wybierz liczbę, której nie ma w tablicy — ile kroków potrzebuje każde wyszukiwanie, żeby to stwierdzić?
Wyścig algorytmów sortowania
Wszystkie cztery algorytmy sortują te same dane, a w każdym torze jeden krok to jedno porównanie albo jedno przesunięcie. Algorytmy O(n²) (bąbelkowe i przez wstawianie) rosną wraz z rozmiarem tablicy dużo szybciej niż O(n log n) (przez scalanie i szybkie). Kolejność zależy jednak też od danych: dla prawie posortowanej tablicy często wygrywa sortowanie przez wstawianie.
Spróbuj: Uruchom wyścig na losowej tablicy 40 elementów, a potem przełącz na prawie posortowaną. Czy zmienia się zwycięzca?
Najczęstsze pytania
Czym jest Algorytmy w akcji?
Algorytmy w akcji to darmowa interaktywna symulacja ze StudyFi Lab. Działa bezpośrednio w przeglądarce, bez rejestracji i bez instalacji. Sortowanie i wyszukiwanie krok po kroku
Czy aplikacja Algorytmy w akcji jest darmowa?
Tak. Aplikacja Algorytmy w akcji jest całkowicie darmowa. Działa w przeglądarce na komputerze, tablecie i telefonie, a konto nie jest potrzebne.
Co mogę odkryć w aplikacji Algorytmy w akcji?
Sortowanie bąbelkowe, Sortowanie przez wstawianie, Sortowanie przez scalanie, Sortowanie szybkie, Wyszukiwanie liniowe a binarne, Wyścig algorytmów sortowania.
Co pokazuje eksperyment „Sortowanie bąbelkowe”?
Sortowanie bąbelkowe porównuje sąsiednie elementy i zamienia je, gdy stoją w złej kolejności. Po każdym przebiegu największy element „wypływa” na koniec, więc nieposortowana część się skraca. Jeśli przebieg nie wykona żadnej zamiany, tablica jest posortowana. W najgorszym przypadku potrzeba n(n−1)/2 porównań, czyli O(n²).
Co pokazuje eksperyment „Sortowanie przez wstawianie”?
Sortowanie przez wstawianie działa jak układanie kart w ręce: lewa część jest już posortowana, a każdy kolejny element (key) przesuwa się w lewo, aż trafi na mniejszy. Większe elementy przesuwają się po drodze o jedno miejsce w prawo. Dla losowych danych to O(n²), ale dla prawie posortowanych niemal O(n) — posortowana tablica wymaga tylko n−1 porównań.
Uczysz się do sprawdzianu?
Wgraj swoje notatki, a StudyFi zrobi z nich fiszki, testy i podcasty.