Math
Wyścig sortowań
Trzy sortowania biegną po tej samej tablicy z tą samą szybkością w PORÓWNANIACH, i pierwszy kończy ten, kto zapytał mniej. Decyduje nieporządek, nie rozmiar: na posortowanym wejściu wstawianie bierze 63 porównania, a szybkie 2016.
Co się dzieje
Trzy tory, jedna tablica i jeden wspólny budżet pracy: wszystkie trzy sortowania posuwają się o tyle samo porównań - albo przesunięć, jeśli przełączysz jednostkę - więc pierwsze kończy to, które potrzebowało najmniej tej jednostki, a nie to, które szybciej się rysuje. Każdy tor mówi tym samym językiem: dwa porównywane klucze mają złotą obwódkę, właśnie zapisany klucz błyska na zielono, pivot ma czerwony znacznik, przetwarzany odcinek jest w nawiasie, elementy na ostatecznym miejscu dostają zieloną stopkę, a klucz trzymany przez sortowanie przez wstawianie wisi nad luką, do której spadnie. Przewidź zwycięzcę przed «Start» albo prowadź wyścig po jednej jednostce. Wypróbuj wejścia: na posortowanej tablicy wstawianie kończy niemal od razu, a quicksort z ostatnim elementem jako pivotem trafia na swój najgorszy przypadek; odwrotny porządek to najgorszy przypadek wstawiania; przy powtarzających się kluczach kolor to pozycja na wejściu, a scalanie zachowuje kolejność równych kluczy, podczas gdy quicksort je miesza. Każdy tor pokazuje też rzeczywisty czas przebiegu na tym komputerze - trzecią wielkość, nigdy jednostkę wyścigu.
Równania modułu
Równania n elementów, a wyścig toczy się w PORÓWNANIACH - wielkości, o której mówią wzory sortowanie przez wstawianie PRZENOSI element dokładnie tyle razy, ile tablica ma inwersji: tożsamość dla KAŻDEJ permutacji, sprawdzona dla wszystkich n! przy n <= 8 porównania przy wstawianiu = inwersje + (n − 1) − (minima prefiksowe przy i >= 1); średnia = n(n−1)/4 + n − H_n DOKŁADNIE: n = 8 -> 19.282142857142858; n = 64 -> 1067.2561090962943 sortowanie szybkie (Lomuto, ostatni element jako element osiowy) średnia = 2(n+1)H_n − 4n DOKŁADNIE: n = 8 -> 16.921428571428571; n = 64 -> 360.70581748175005 sortowanie przez scalanie, przypadek najgorszy = n·ceil(lg n) − 2^ceil(lg n) + 1 - wzór, a nie ograniczenie: 321 przy n = 64, wobec ceil(lg n!) = 296, dolnej granicy DOWOLNEGO sortowania przez porównania obie wartości są równe dla n <= 4 i potem się rozchodzą; sortowanie przez scalanie zapisuje też n·lg n elementów niezależnie od wejścia - 384 przy n = 64 64 elementy, każde miejsce wymieszane: 1001 inwersji; wstawianie 1057 porównań / 1001 przesunięć, scalanie 307 / 384, sortowanie szybkie 352 / 306 64 elementy, wejście posortowane: wstawianie 63, scalanie 192, sortowanie szybkie 2016 - a 2016 to n(n−1)/2, przypadek NAJGORSZY sortowania szybkiego scalanie wyprzedza wstawianie przy 15 wymieszanych miejscach z 64 (269 wobec 246): próg wyznacza nieporządek, a nie rozmiar - na losowym wejściu scalanie jest lepsze od n = 4 równe klucze, 64 elementy o 8 wartościach: pary pozostawione w odwrotnej kolejności - wstawianie 0, scalanie 0, sortowanie szybkie 77
