- Zliczane
- Właśnie przeniesione
- Na miejscu
Sortowanie przez zliczanie
Sortowanie przez zliczanie działa, gdy wartości są liczbami całkowitymi z małego zakresu. Ma jeden licznik dla każdej możliwej wartości, zlicza, ile razy każda występuje, i na tej podstawie wie dokładnie, gdzie należy każda wartość. Obserwuj, jak liczniki rosną podczas czytania listy, a potem maleją, gdy kolejne wartości trafiają do swoich bloków, po jednym przeniesieniu. Naciśnij Odtwórz, aby obejrzeć sortowanie, albo Krok i Wstecz, aby przechodzić po jednym przeniesieniu. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce. Pasek między listą a wierszem bufora ma jeden licznik dla każdej wartości. Kafelki liczą zliczone wartości, przeniesienia i liczniki. Wybierz liczbę słupków, 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 albo wpisz własne liczby całkowite. Wypróbuj listę z małą liczbą różnych wartości.
- Naciśnij Odtwórz albo używaj przycisków Krok i Wstecz, aby przechodzić po jednej wartości. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce sortowania.
- Obserwuj liczniki: rosną podczas czytania listy, a potem odliczają w dół, gdy kolejne wartości trafiają na miejsca.
Jak działa sortowanie przez zliczanie
Utwórz licznik dla każdej wartości od najmniejszej do największej. Przeczytaj listę raz i dodaj jeden do licznika każdej napotkanej wartości. Potem zsumuj zliczenia od najmniejszej wartości: blok danej wartości zaczyna się tuż po wszystkich mniejszych wartościach. Na koniec przejdź listę jeszcze raz, przenieś każdą wartość na następne wolne miejsce w jej bloku i skopiuj wynik z powrotem.
Szybkie dla małego zakresu
Sortowanie przez zliczanie czyta listę dwa razy i raz przechodzi przez liczniki, więc jego praca rośnie z n + k: liczbą wartości plus liczbą liczników. Dla wielu wartości z małego zakresu, takich jak wyniki egzaminu od 0 do 100 albo wiek, bije to każde sortowanie przez porównania. Przy szerokim zakresie marnuje czas i pamięć na liczniki, których nikt nie używa: trzy wartości rozrzucone od 1 do 1 000 000 wymagałyby miliona liczników. To także krok, który sortowanie pozycyjne powtarza dla każdej cyfry.
Często zadawane pytania
Jak działa sortowanie przez zliczanie?
Zlicza, ile razy występuje każda wartość, sumuje zliczenia, aby ustalić, gdzie zaczyna się blok każdej wartości, a potem przenosi każdą wartość prosto na następne wolne miejsce w jej bloku. Nigdy nie porównuje dwóch wartości.
Kiedy używać sortowania przez zliczanie?
Gdy wartości są liczbami całkowitymi albo da się je na nie zamienić, a zakres od najmniejszej do największej nie jest dużo większy niż liczba wartości: oceny, wiek, krótkie kody. Wtedy zajmuje czas proporcjonalny do n + k.
Czy sortowanie przez zliczanie jest stabilne?
Tak, gdy wartości są przenoszone w kolejności z listy na następne wolne miejsce w swoim bloku, jak tutaj. Dlatego sortowanie pozycyjne może go używać dla każdej cyfry.
Dlaczego po prostu nie wypisać każdej wartości tyle razy, ile ją zliczono?
Dla samych liczb to działa i jest nawet prostsze. Ale prawdziwe dane zwykle zawierają więcej niż klucz, na przykład imię przy każdym wyniku, a wypisanie zliczonych kluczy by je zgubiło. Przenoszenie samych elementów zachowuje wszystko, co jest z nimi związane.
Czy moje liczby są gdzieś wysyłane?
Nie. Sortowanie działa w Twojej przeglądarce, a ostatnie ustawienia zostają w pamięci lokalnej 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