Wyścig sortowania
Pięć algorytmów dostaje te same liczby i ma je ułożyć od najmniejszej do największej. Każde porównanie i każde przestawienie to jeden krok zegara. Kto pierwszy na mecie?
Bieżnia
| Miejsce | Algorytm | Porównania | Przestawienia | Kroki razem |
|---|
Naciśnij Start. Potem zmień dane na „prawie posortowane” albo „odwrotnie posortowane” i pościgaj się jeszcze raz. Zwycięzca nie zawsze jest ten sam!
Ty kontra algorytm
Komputer nie „widzi” od razu, która liczba jest większa. Musi porównywać po dwie. Masz 7 paczek o nieznanej wadze. Ułóż je od najlżejszej (z lewej) do najcięższej (z prawej), używając jak najmniej ważeń. Kliknij dwie paczki, a potem „Zważ” albo „Zamień”.
Wybierz dwie paczki.
Twoje ważeniaA gdyby elementów był milion?
Na bieżni różnice są małe. Prawdziwe programy sortują jednak miliony rzeczy: kontakty, filmy, wyniki wyszukiwania. Policz, ile trwałoby sortowanie na komputerze, który wykonuje miliard porównań na sekundę.
Jak działają zawodnicy?
Sprawdź się
Punkty 0 · Seria 0 · Rekord 0Czym jest sortowanie?
Sortowanie to układanie danych w określonej kolejności: liczb od najmniejszej do największej, nazwisk alfabetycznie, filmów od najnowszego. Komputer sortuje bez przerwy: listę plików, wiadomości, wyniki wyszukiwania, oceny w dzienniku. Posortowane dane da się też dużo szybciej przeszukiwać, np. metodą dzielenia na pół.
Algorytm sortowania to przepis, krok po kroku, jak to zrobić. Jest ich wiele, bo różnią się szybkością, zużyciem pamięci i tym, jak radzą sobie z różnymi danymi. Sortowanie bąbelkowe, przez wybór i przez wstawianie są proste, ale wolne dla dużych danych. Sortowanie przez scalanie i szybkie dzielą problem na mniejsze części i dla dużych danych są nieporównanie szybsze.
Porównanie algorytmów
| Algorytm | Najlepiej | Średnio | Najgorzej | Dodatkowa pamięć | Stabilny |
|---|---|---|---|---|---|
| bąbelkowe | n | n² | n² | nie | tak |
| przez wybór | n² | n² | n² | nie | nie |
| przez wstawianie | n | n² | n² | nie | tak |
| przez scalanie | n log n | n log n | n log n | tak, n | tak |
| szybkie (quicksort) | n log n | n log n | n² | trochę | nie |
Zapis n² oznacza, że przy dwa razy większej liczbie danych pracy jest cztery razy więcej. Przy n log n pracy przybywa niewiele więcej niż danych. Stabilny algorytm zostawia równe elementy w tej samej kolejności, w jakiej były, co ważne np. przy sortowaniu uczniów najpierw po imieniu, a potem po klasie.
Historia w pigułce
- 1890Herman Hollerith sortuje karty perforowane spisu ludności USA na elektrycznej maszynie. Z jego firmy wyrośnie później IBM.
- 1945John von Neumann opisuje sortowanie przez scalanie, jeden z pierwszych programów dla komputera z pamięcią programu.
- 1959Tony Hoare wymyśla sortowanie szybkie (quicksort), pracując nad tłumaczeniem maszynowym w Moskwie. Publikuje je w 1961 roku.
- 1973Donald Knuth poświęca sortowaniu i wyszukiwaniu cały trzeci tom „Sztuki programowania”.
- 2002Tim Peters tworzy Timsort, połączenie scalania i wstawiania. Używa go Python, a później także Java i Android.
Najczęstsze pytania o sortowanie
Który algorytm sortowania jest najszybszy?
Nie ma jednego zwycięzcy. Dla dużych, losowych danych zwykle wygrywają sortowanie szybkie i przez scalanie. Dla danych prawie posortowanych bardzo dobre jest sortowanie przez wstawianie. Dlatego języki programowania używają algorytmów mieszanych, np. Timsort.
Jak działa sortowanie bąbelkowe?
Algorytm przechodzi przez listę i porównuje sąsiednie elementy. Jeśli są w złej kolejności, zamienia je. Po każdym przejściu największy element „wypływa” na koniec jak bąbelek powietrza. Powtarza to, aż w całym przejściu nie będzie żadnej zamiany.
Na czym polega sortowanie szybkie (quicksort)?
Wybiera jeden element, tzw. piwot, i dzieli resztę na mniejsze od niego i większe od niego. Piwot trafia między te grupy, na swoje ostateczne miejsce. Potem tak samo sortuje każdą z grup. Gdy piwot jest wybierany źle, np. zawsze ostatni element w posortowanych danych, algorytm bardzo zwalnia.
Co oznacza O(n²) i O(n log n)?
To notacja dużego O, która mówi, jak szybko rośnie liczba operacji, gdy rośnie liczba danych n. Przy O(n²) dwa razy więcej danych to cztery razy więcej pracy. Przy O(n log n) dwa razy więcej danych to tylko trochę ponad dwa razy więcej pracy.
Co to jest sortowanie stabilne?
Sortowanie jest stabilne, jeśli elementy o równej wartości zostają w tej samej kolejności, w jakiej były przed sortowaniem. Stabilne są np. sortowanie bąbelkowe, przez wstawianie i przez scalanie.
Jakiego sortowania używa komputer na co dzień?
Najczęściej algorytmów mieszanych. Python używa Timsorta, czyli połączenia scalania i wstawiania. Biblioteka C++ zwykle używa introsorta, czyli sortowania szybkiego, które w razie kłopotów przełącza się na inną metodę, a małe kawałki sortuje przez wstawianie.