- Bieżący kubełek
- Właśnie przeniesiony
- Skopiowane z powrotem
- Na miejscu
Sortowanie pozycyjne
Sortowanie pozycyjne porządkuje liczby całkowite, nigdy nie porównując dwóch z nich. Sortuje listę według cyfry jedności, potem dziesiątek, potem setek, za każdym razem przenosząc wartości do dziesięciu kubełków i kopiując je z powrotem po kolei. Obserwuj, jak kubełki w rzędzie pod listą zapełniają się po jednym przeniesieniu i jak lista staje się posortowana według coraz większej liczby cyfr. 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. Kubełki od 0 do 9 stoją obok siebie w rzędzie pod listą. Kafelki liczą odczytane cyfry, przeniesienia i przebiegi. Wybierz liczbę słupków, ich początkowy układ albo wpisz własne liczby do 999. 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 do 999, aby zobaczyć przebieg dla setek.
- Naciśnij Odtwórz albo używaj przycisków Krok i Wstecz, aby przenosić po jednej wartości. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce sortowania.
- Obserwuj każdy przebieg: zliczanie cyfr, przeniesienie każdej wartości do jej kubełka, a potem kopiowanie kubełków z powrotem.
Jak działa sortowanie pozycyjne
Patrz tylko na ostatnią cyfrę każdej liczby i posortuj listę według niej: wrzuć każdą liczbę do jednego z dziesięciu kubełków, od 0 do 9, w kolejności, w jakiej przychodzą, a potem skopiuj kubełki z powrotem jeden po drugim. To samo zrób z cyfrą dziesiątek, potem setek. Ponieważ każdy przebieg zachowuje kolejność liczb o tej samej cyfrze, wcześniejsze przebiegi nadal decydują o kolejności między nimi, a po ostatnim przebiegu cała lista jest posortowana.
Żadnych porównań
Sortowania przez porównania potrzebują w najgorszym przypadku co najmniej około n log₂ n porównań, bez względu na to, jakiego sprytnego triku używają. Sortowanie pozycyjne omija to ograniczenie, bo zamiast tego czyta cyfry: każdy przebieg odczytuje jedną cyfrę każdej wartości i przenosi każdą wartość dwa razy, więc d cyfr to d przebiegów, a praca rośnie jak n · d. Przy długich listach krótkich kluczy to się opłaca: milion liczb do 999 wymaga trzech przebiegów, a sortowanie przez porównania potrzebuje około 20 milionów porównań. Cena jest taka, że działa ono tylko dla kluczy złożonych z cyfr lub znaków i potrzebuje miejsca na kubełki.
Często zadawane pytania
Jak działa sortowanie pozycyjne?
Sortuje liczby według ostatniej cyfry, potem według cyfry przed nią i tak dalej aż do pierwszej cyfry. Każdy przebieg rozkłada liczby do dziesięciu kubełków według tej cyfry, zachowując ich kolejność, i kopiuje kubełki z powrotem. Po przebiegu dla najbardziej znaczącej cyfry lista jest posortowana.
Dlaczego zaczyna się od ostatniej cyfry?
Bo każdy przebieg jest stabilny: liczby o tej samej cyfrze zachowują kolejność nadaną przez wcześniejsze przebiegi. Ostatni przebieg, po pierwszej cyfrze, decyduje więc o kolejności, a remisy rozstrzygają cyfry już posortowane. Nazywa się to sortowaniem pozycyjnym LSD (least significant digit, od najmniej znaczącej cyfry).
Czy sortowanie pozycyjne jest szybsze od quicksorta?
Może być, przy wielu krótkich kluczach: jego praca rośnie jak liczba wartości razy liczba cyfr, bez n log n. Przy niewielu wartościach, bardzo długich kluczach lub danych, które nie składają się z cyfr, quicksort i sortowanie przez scalanie są zwykle szybsze i prostsze.
Jaki ma związek z sortowaniem przez zliczanie?
Każdy przebieg sortowania pozycyjnego to sortowanie przez zliczanie po jednej cyfrze: zlicz wartości dla każdej cyfry, oblicz, gdzie zaczyna się każdy kubełek, i przenieś tam wartości po kolei.
Czy moje liczby są gdzieś wysyłane?
Nie. Sortowanie działa w 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