Sortowanie pozycyjne

Sortowanie pozycyjne jest wyjątkowo nieintuicyjnym algorytmem sortowania, do który sam w rzeczywistości niewiele potrafi zdziałać. Wykorzystuje on w złośliwy sposób inne algorytmy sortujące stabilnie - wspomniane wcześniej sortowania przez zliczanie, bąbelkowe, czy też przez scalanie.
Do naszych celów najlepsze będzie sortowanie przez zliczanie (ponieważ jest z nich najszybsze - złożoność O(n) dla k=O(n) gdzie k jest maksymalną wielkością danych.

Radix Sort polega na sortowaniu liczb kolejno według wartości liczb jedności, dziesiątek, setek, tysiecy itd.

329		720		720		329
457		355		329		355
657		436		436		436
839		457		839		457
436		657		355		657
720		329		457		720
355		839		657		839

Implementacja

Implementacja sortowania pozycyjnego jest bardzo prymitywna

Pseudokod:

Radix-Sort(A, n)
     for i = 1 to d
          [wywołaj sortowanie stabilne po pozycji i]

C++

void Radix-Sort(int A[], int n)
{
     for(int i=1;i<=n;i++)
          Counting-Sort(i);
}

Żeby nie było za prosto każdy będzie musiał sam sobie odpowiednio przerobić algorytm sortowania przez zliczanie na potrzeby tego zadania.