- Porównywane
- Zaznaczone (minimum, element osiowy lub klucz)
- Zamienione lub przesunięte
- Na miejscu
| Miejsce | Sortowanie | Porównania lub odczyty | Zamiany lub przesunięcia | Operacje |
|---|
Wyścig sortowań
Który algorytm sortowania jest najszybszy? To zależy od listy. Wyścig sortowań uruchamia wszystkie osiem algorytmów sortowania jednocześnie na tej samej liście, każdy na własnym torze, i liczy każde porównanie, odczyt, zamianę i przesunięcie jako jedną operację. Tory posuwają się naprzód wraz ze wzrostem liczników, więc możesz zobaczyć, jak wydajne sortowania kończą, gdy wolne wciąż zamieniają, i jak zmienia się kolejność, gdy lista jest prawie posortowana lub odwrócona. Naciśnij Odtwórz, aby obejrzeć wyścig wszystkich ośmiu algorytmów sortowania na tej samej liście, albo Krok i Wstecz, aby przechodzić po jednej operacji. Przeciągnij suwak, aby przeskoczyć w dowolne miejsce. Każde porównanie, odczyt, zamiana lub przesunięcie to jedna operacja, a każdy tor posuwa się naprzód wraz ze wzrostem własnego licznika, więc sortowanie, które potrzebuje najmniej operacji, kończy pierwsze. Wybierz liczbę słupków i ich początkowy układ albo wpisz własne liczby. Gdy plansza jest zaznaczona, strzałki przechodzą o krok, spacja uruchamia i wstrzymuje, a Home i End przenoszą na początek i na koniec.
Jak to działa
- Wybierz liczbę słupków i ich początkowy układ: losowy, prawie posortowany, odwrócony lub z kilkoma różnymi wartościami. Możesz też wpisać własne liczby.
- Naciśnij Odtwórz i obserwuj osiem torów. Krok i Wstecz przechodzą po jednej operacji; suwak przeskakuje w dowolne miejsce wyścigu.
- Porównaj tabelę wyników, a potem wypróbuj listę prawie posortowaną i odwróconą, aby zobaczyć, jak zmienia się ranking.
Jak działa wyścig
Każde z ośmiu sortowań dostaje tę samą listę. Każde porównanie dwóch wartości, każda cyfra lub wartość odczytana przez sortowanie pozycyjne i przez zliczanie oraz każda zamiana lub przesunięcie to jedna operacja. W każdej chwili wyścigu każdy tor pokazuje, jak daleko jego sortowanie doszło przy takiej liczbie operacji. Sortowanie, które potrzebuje mniej operacji, wcześniej dociera do końca. Tabela wyników podaje dla każdego sortowania porównania, zamiany lub przesunięcia oraz sumę.
Co pokazują wyniki
Przy 40 losowych wartościach sortowanie przez zliczanie potrzebuje około 120 operacji, sortowanie pozycyjne około 240, sortowanie szybkie około 260, a sortowanie przez scalanie około 380. Dalej jest sortowanie przez kopcowanie z około 490, sortowanie przez wybieranie i przez wstawianie potrzebują około 820, a sortowanie bąbelkowe ponad 1100. Na prawie posortowanej liście wygrywa sortowanie przez wstawianie z około 50, a drugie jest sortowanie bąbelkowe. Na odwróconej liście sortowanie bąbelkowe i przez wstawianie potrzebują po 1560. Sortowanie przez zliczanie i pozycyjne wygrywają tak często, bo te wartości to małe liczby całkowite; dla innych danych w ogóle nie da się ich użyć.
Często zadawane pytania
Który algorytm sortowania jest najszybszy?
To zależy od danych. Dla małych liczb całkowitych najmniej operacji potrzebują sortowanie przez zliczanie i pozycyjne. Dla ogólnych danych na losowych listach najszybsze są sortowanie szybkie i przez scalanie, a na listach prawie posortowanych sortowanie przez wstawianie. Sortowanie bąbelkowe i przez wybieranie są wolne na wszystkich listach poza najmniejszymi.
Co liczy się jako operacja?
Każde porównanie dwóch wartości, każda cyfra lub wartość odczytana przez sortowanie pozycyjne i przez zliczanie oraz każda zamiana lub przesunięcie wartości. To prosty model: rzeczywisty czas działania zależy też od dostępu do pamięci i kosztu każdej operacji.
Dlaczego sortowanie przez zliczanie i pozycyjne wygrywają tak często?
Bo nigdy nie porównują wartości. Wykorzystują to, że wartości są małymi liczbami całkowitymi, więc ich praca rośnie z n plus zakresem wartości, a nie z n log n. Dla danych, które nie są małymi liczbami całkowitymi, nie mają zastosowania.
Dlaczego sortowanie przez wstawianie wygrywa na prawie posortowanej liście?
Bo jego praca to liczba wartości plus liczba par w złej kolejności. Prawie posortowana lista ma bardzo mało takich par, więc każda wartość przesuwa się tylko o jedno lub dwa miejsca.
Czy moje liczby są gdzieś wysyłane?
Nie. Wyścig działa w twojej przeglądarce, a ostatnie ustawienia zostają w lokalnej pamięci tej przeglądarki.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Przejdź do edytora