Sortowanie pozycyjne

Sortowanie pozycyjne wyróżnia się wśród algorytmów sortowania: nigdy nie pyta, która z dwóch wartości jest większa. Czyta liczby cyfra po cyfrze i sortuje je według jednej cyfry naraz, używając dziesięciu kubełków. Pomysł jest starszy niż komputery: tak działały sortery kart perforowanych.

Słupki listy nad rzędem dziesięciu kubełków oznaczonych od 0 do 9; wartość wpada do kubełka swojej ostatniej cyfry
Słupki listy nad rzędem dziesięciu kubełków oznaczonych od 0 do 9; wartość wpada do kubełka swojej ostatniej cyfry

Pomysł

Posortuj liczby tylko według cyfry jedności. Potem posortuj je według cyfry dziesiątek, ale tak, aby liczby o tej samej cyfrze dziesiątek zachowały kolejność z pierwszego przebiegu. Potem według setek, w ten sam sposób. Po ostatnim przebiegu lista jest posortowana: najpierw decydują setki, liczby o tych samych setkach są już uporządkowane według dziesiątek, a te o tych samych dziesiątkach według jedności.

Jeden przebieg z kubełkami

Każdy przebieg używa dziesięciu kubełków, po jednym na każdą cyfrę od 0 do 9. Przejdź listę od początku do końca i przenieś każdą liczbę do kubełka jej cyfry, za liczby, które już tam są. Potem opróżnij kubełki z powrotem do listy po kolei, zaczynając od kubełka 0. To, że liczby są przenoszone w kolejności listy i dokładane na koniec kubełka, sprawia, że przebieg jest stabilny. Aplikacja najpierw zlicza liczby dla każdej cyfry, aby kubełki mogły stać obok siebie w jednym rzędzie, każdy zaraz za poprzednim: to sortowanie przez zliczanie po jednej cyfrze.

Przykład

Weź 170, 45, 75, 90, 802, 24, 2, 66. Według cyfry jedności: 170, 90, 802, 2, 24, 45, 75, 66. Według cyfry dziesiątek: 802, 2, 24, 45, 66, 170, 75, 90; zwróć uwagę, że 802 i 2, obie z cyfrą dziesiątek 0, zachowują kolejność z pierwszego przebiegu. Według cyfry setek: 2, 24, 45, 66, 75, 90, 170, 802. Trzy przebiegi po ośmiu liczbach: 24 odczytane cyfry i 48 przeniesień, a ani jednego porównania.

Jak szybko działa?

Każdy przebieg odczytuje jedną cyfrę każdej liczby i przenosi każdą liczbę dwa razy, więc dla n liczb o d cyfrach praca rośnie jak n · d. Sortowanie przez porównania potrzebuje w najgorszym przypadku co najmniej około n log₂ n porównań, bo musi odróżnić n! możliwych kolejności, zadając po jednym pytaniu typu tak/nie. Sortowania pozycyjnego to nie ogranicza, bo nigdy nie zadaje takich pytań. Przy wielu krótkich kluczach, na przykład milionie liczb poniżej 1000, trzy przebiegi to znacznie mniej pracy niż około 20 milionów porównań, których potrzebowałoby sortowanie przez porównania. Przy długich kluczach lub niewielu wartościach ta przewaga znika.

LSD i MSD oraz historia

Pokazana tu wersja zaczyna od najmniej znaczącej cyfry (LSD). Odwrotne podejście, od najbardziej znaczącej cyfry (MSD), dzieli listę na kubełki według pierwszej cyfry i sortuje każdy kubełek osobno, co pasuje do napisów o różnej długości. Sortowanie pozycyjne wywodzi się z sorterów kart perforowanych, które pojawiły się po maszynach tabulacyjnych, które Herman Hollerith zbudował na spis ludności USA z 1890 roku: sorter wrzucał każdą kartę do jednej z dziesięciu przegródek według otworu w jednej kolumnie, a operatorzy przepuszczali talię raz na każdą kolumnę, zaczynając od ostatniej.

Tabulator kart dziurkowanych Holleritha w Computer History Museum, takiego typu jak przy spisie powszechnym USA w 1890. Operatorzy przepuszczali talię przez sortownik raz na kolumnę — protoplasta sortowania pozycyjnego.
Tabulator kart dziurkowanych Holleritha w Computer History Museum, takiego typu jak przy spisie powszechnym USA w 1890. Operatorzy przepuszczali talię przez sortownik raz na kolumnę — protoplasta sortowania pozycyjnego.

Wypróbuj

Otwórz aplikację i naciśnij Krok. Każdy przebieg najpierw zlicza cyfry, co wyznacza kubełki od 0 do 9 w rzędzie pod listą. Potem liczby po kolei wpadają do swoich kubełków (aktywny kubełek jest podświetlony) i są kopiowane z powrotem. Wpisz własne liczby do 999, na przykład te z przykładu powyżej, aby zobaczyć wszystkie trzy przebiegi.

Często zadawane pytania

Jaka jest złożoność czasowa sortowania pozycyjnego?

O(n · d) dla n kluczy o d cyfrach w stałej podstawie, plus koszt kubełków w każdym przebiegu. Potrzebuje O(n) dodatkowej pamięci na bufor, w którym mieszczą się kubełki.

Czy sortowanie pozycyjne jest stabilne?

Sortowanie pozycyjne LSD musi takie być: działa tylko dlatego, że każdy przebieg zachowuje wartości o tej samej cyfrze w kolejności, w jakiej przyszły. Wynik końcowy jest więc również stabilny.

Czy sortowanie pozycyjne radzi sobie z liczbami ujemnymi lub ułamkami dziesiętnymi?

Nie bezpośrednio, ale z pewnym trikiem tak: przesuń liczby ujemne, aby wszystkie były dodatnie, albo posortuj je osobno i odwróć. Liczby zmiennoprzecinkowe można sortować według ich wzorców bitowych po niewielkim przekształceniu.

Dlaczego podstawa 10?

Bo łatwo ją śledzić. Komputery zwykle sortują po 8 lub 16 bitów naraz, więc liczba 32-bitowa wymaga czterech lub dwóch przebiegów, z 256 lub 65 536 kubełkami.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Wypróbuj sortowanie pozycyjne