Jak to działa?

Sortowanie pozycyjne przetwarza po jednej pozycji cyfry, od najmniej znaczącej (jedności) do najbardziej znaczącej. Każde przejście wykorzystuje stabilne sortowanie, dzięki czemu zachowuje rezultaty wcześniejszych przejść.

Proces krok po kroku:

1. Sortuj według cyfry jedności za pomocą stabilnego sortowania przez zliczanie.
2. Sortuj według cyfry dziesiątek, zachowując wcześniejszą kolejność w przypadku remisów.
3. Kontynuuj dla setek, tysięcy i kolejnych pozycji, aż przetworzysz pozycję cyfry największej liczby.

Przykład dla [170, 45, 75, 90, 2, 802, 24, 66]:

• Według cyfry jedności: [170, 90, 2, 802, 24, 45, 75, 66]
• Według cyfry dziesiątek: [2, 802, 24, 45, 66, 170, 75, 90]
• Według cyfry setek: [2, 24, 45, 66, 75, 90, 170, 802]

Po przetworzeniu ostatniej cyfry tablica jest w pełni posortowana. Cała magia polega na tym, że stabilność zachowuje kolejność według mniej znaczących cyfr, gdy zaczynają decydować bardziej znaczące cyfry.