Sortowanie pozycyjne – zastosowanie kolejki w JavaScripcie

Kolejki mają jedno bardzo ciekawe, zastosowanie. Mianowicie, można użyć ich do sortowania danych. Dziś pokażę jak za pomocą implementacji kolejki w JavaScripcie, posortować tablicę liczb, od najmniejszej do największej.

Sortowanie, o którym piszę, to sortowanie pozycyjne. Jest ono dość nietypowe, ponieważ w ciągu przebiegu całego algorytmu, ani razu nie porównuje żadnych wartości. W takim razie, jak to działa? Odpowiedź jest prosta – kolejki 🙂

Uproszczę trochę całość, na potrzeby tego posta. Założę, że mamy do czynienia tylko z liczbami w przedziale od zera do 99. Jednak dobre zrozumienie tego co tutaj opiszę wystarczy by bez problemu rozwinąć ten skrypt tak aby sortował znacznie większe liczby.

Tak jak wskazuje nazwa, sortowanie pozycyjne, układa liczby względem cyfr na konkretnych pozycjach. Mój skrypt, będzie przebiegał przez tablicę liczb dwa razy. Najpierw posortuje je według cyfry na miejscu jedności, a przy drugim obiegu według cyfry na miejscu dziesiętnych.

Wyobraźmy sobie, że mamy 10 koszy. Każdy przypisany konkretnej cyfrze:

Przez algorytm sortowania pozycyjnego przepuszczam tablicę zawierająca następujące liczby:

Algorytm umieszcza liczby po kolei w koszach o etykiecie równej cyfrze, którą dana liczba ma w rzędzie jedności. Tak będą wyglądać kosze:

Następnie algorytm łączy te liczby z powrotem w jedną tablicę, używając nowej kolejności:

Nie wyglądaj na posortowane, ale to dopiero połowa działania skryptu. Czas na kolejny przebieg. Tym razem algorytm umieści liczby po kolei w koszach o etykiecie odpowiadających cyfrze na miejscu dziesiętnej pozycji danej liczby.

Oto co dostaniemy po połączeniu:

Sukces. Założenie działa. Teraz czas przetłumaczyć to na JavaScriptowy. W tym miejscu przychodzą mi z pomocą kolejki :). Wykorzystam je jako „kosze”. Ponieważ łatwo wyciągać z kolejki dane „po kolei”, nadadzą się idealnie. Kolejność jest tutaj najważniejsza.

Oto gotowy skrypt a poniżej wytłumaczenie jego działania:

Stworzyłem jedną funkcję radixSort, która jako argument przyjmuje tablicę nieuporządkowanych liczb. Funkcja sortuje liczby przy pomocy algorytmu sortowania pozycyjnego i zwraca uporządkowaną tablicę.

Wewnątrz radixSort najpierw tworzę, tablicę queues i wypełniam ją dziesięcioma instancjami kolejki. To będą moje kosze, do sortowania liczb. Nie muszę ich oznaczać w żaden sposób, indeks każdej z nich w tablicy jest cyfrą między 0 a 9. Idealnie.

Następna jest funkcja sortDigits. Odpowiada ona za wrzucenie liczb do właściwych kolejek. Przyjmuje cztery argumenty. Dwa pierwsze to kolejno: tablica liczb do posortowania, oraz tablica kolejek. Dwa kolejne argumenty to modulo oraz dzielnik, będę ich używał aby wyodrębnić cyfrę na pozycji jedności lud dziesiątek. Wewnątrz funkcji, pętla for przechodzi przez tablice liczb. Każdy element jest najpierw sprowadzany do modulo podanego jako argument, a następnie dzielonego przez dzielnik. W pierwszym obiegu, będzie to odpowiednio 10 oraz 1, w drugim 100 i 10, jeśli potrzebowalibyśmy trzeciego obiegu, użyłbym liczb 1000 i 100. W ten sposób otrzymuję interesującą mnie cyfrę, używam jej jako indeksu tablicy kolejek, aby wrzucić liczbę do odpowiedniego ‚kosza’

Druga funkcja joinQueues jest znacznie mniej skomplikowana. Przy pomocy pętli for przebiega przez wszystkie kolejki, i jeżeli nie są one puste, ściąga z nich dany element i zapisuje na kolejnym miejscu (poczynając od indeksu zero) w oryginalnej tablicy elementów.

I tak to wygląda. Bardzo sprytny pomysł na sortowanie liczb, zaimplementowany w JavaScripcie.