Sorting Race — obstaw szybszy algorytm
Dwa algorytmy sortowania ścigają się na tej samej tablicy. Obstaw zwycięzcę: lepsza złożoność przegrywa częściej, niż myślisz.
Sześć wyścigów. Ta sama tablica, dwa algorytmy — wybierz ten, który twoim zdaniem skończy pierwszy.
Jak grać
- Dwa sortowania, jedna tablica. Obstaw to, które skończy pierwsze, i patrz.
- Wygrywa to, które zużyło mniej operacji — porównań plus przesunięć — a nie to o lepszej podręcznikowej złożoności.
- Czytaj rozmiar i kształt. Poniżej mniej więcej dwudziestu słupków wygrywają proste; na prawie posortowanej tablicy wstawianie bije wszystko.
- Za trafienie dostajesz 50, za pudło tracisz 50. Sześć wyścigów, zaczynasz ze 100.
Jak to działa
Dwa algorytmy sortowania ścigają się na identycznej tablicy narysowanej jako słupki, a ty obstawiasz, który skończy pierwszy. Każda runda zestawia sortowanie O(n log n) z sortowaniem O(n²), więc oczywisty faworyt jest zawsze — i oczywisty faworyt myli się mniej więcej w połowie przypadków. Naprawdę decydują rozmiar tablicy i jej kształt: sortowanie przez wstawianie kończy prawie posortowaną tablicę przy dwudziestej części operacji potrzebnych naiwnemu quicksortowi, a poniżej mniej więcej dwudziestu elementów stałe ważą więcej niż asymptotyka — i właśnie dlatego prawdziwe biblioteki sortowania przełączają się tam na wstawianie. Zwycięzcę rozstrzyga liczba operacji, a nie stoper, więc wynik jest ten sam na każdej maszynie. Wszystko działa na twoim urządzeniu, nic nigdzie nie jest wysyłane i nie ma się gdzie rejestrować.
Operacje to porównania plus przesunięcia danych, gdzie zamiana liczy się raz, liczone na podręcznikowych implementacjach. Prawdziwe biblioteczne sortowania są hybrydami i wygrywałyby niemal każdy wyścig — i o to właśnie chodzi.
Najczęstsze pytania
Czy lepszy algorytm nie jest zawsze szybszy?
Przy tych rozmiarach nie. Notacja O opisuje, jak rośnie koszt, a nie ile wynosi, i całkowicie ukrywa stałą. Zmierzone na 400 rozgrywkach: obstawianie lepszej złożoności teoretycznej trafia 3,19 na 6, wobec 3,00 przy obstawianiu wciąż tej samej strony. Dwie reguły — prawie posortowana tablica i mała tablica obie sprzyjają prostemu sortowaniu — trafiają około 4,8 na 6.
Jak wyłaniany jest zwycięzca?
Przez zliczanie porównań i przesunięć, obliczone zanim cokolwiek zostanie narysowane. Animacja odtwarza ten wynik w tym samym tempie po obu stronach, więc strona potrzebująca mniej operacji kończy pierwsza na ekranie dokładnie z tego powodu, dla którego wygrywa. Wizualizator odpalający dwie pętle w czasie rzeczywistym dawałby inną odpowiedź na szybkiej maszynie niż na wolnej.
Dlaczego quicksort czasem wypada tak źle?
Bierze ostatni element jako oś — to wersja naiwna. Na tablicy już lub prawie posortowanej to najgorszy możliwy wybór: podziały degenerują się i wykonuje pracę kwadratową dokładnie na tych danych, z którymi sortowanie przez wstawianie radzi sobie najszybciej. Prawdziwe implementacje biorą medianę z trzech albo losową oś właśnie po to, żeby tego uniknąć.
Co oznaczają kształty tablicy?
Losowa jest potasowana. Prawie posortowana jest w kolejności poza kilkoma sąsiednimi zamianami. Odwrócona jest dokładnie na odwrót. Mało wartości ma tylko cztery różne wartości i tam podział naiwnego quicksorta się rozsypuje. Piła powtarza ten sam narastający ciąg kilka razy.