Sortowanie przez zliczanie
COUNTING-SORT(A, B, n, k)
W algorytmie sortowanie przez zliczanie zakładamy, że każdy
1. begin
element ciągu wejściowego jest liczbą całkowitą z przedziału od 0
2. for i := 0 to k do
do k dla pewnego ustalonego k.
3. C[i] := 0;
4. for j := 1 to n do
Główny pomysł polega na obliczeniu dla każdego elementu x ciągu
5. C[A[j]] := C[A[j]] + 1;
wejściowego, liczby elementów mniejszych od x.
// C[i] zawiera teraz liczbę elementów równych i.
Znając tą liczbę, znamy pozycję x w ciągu posortowanym: jeśli jest
6. for i := 1 to k do
i liczb mniejszych od x, to w ciągu posortowanym x powinien
7. C[i] := C[i] + C[i - 1];
znajdować się na pozycji i + 1.
// C[i] zawiera teraz liczbę elementów nie większych od i.
To postępowanie należy nieco zmodyfikować w sytuacji, kiedy 8. for j := n downto 1 do
dozwolonych jest kilka elementów o tej samej wartości, ponieważ 9. begin
nie chcemy, by wszystkie takie elementy trafiły na tę samą pozycję. 10. B[C[A[j]]] := A[j];
11. C[A[j]] := C[A[j]] - 1;
Przyjmujemy, że dane wejściowe znajdują się w tablicy A[1..n]. W
12. end;
tablicy B[1..n] zostanie umieszczony wynik algorytmu (czyli
13. end;
posortowane dane wejściowe), a w tablicy C[0..k] przechowywane
będą tymczasowe dane pomocnicze.
Przykład
Tablica wejściowa: A = [3, 5, 2, 0, 4, 2, 3, 0, 3], n = 9, k = 5,
Po wykonaniu wierszy 1-7, w C[i] znajduje się liczba elementów
Tablica C po wykonaniu pętli for w wierszach 6,7:
ciągu wejściowego nie większych od i, dla każdego i = 0, 1, . . . , k.
W pętli for w wierszach 8-12 wszystkie elementy A[j] zostają
C[0] = 2, C[1] = 2, C[2] = 4, C[3] = 7, C[4] = 8, C[5] = 9.
umieszczane na właściwych pozycjach w tablicy B.
Działanie pętli for w wierszach 8-12:
Jeśli wszystkie elementy są parami różne, to przy pierwszym
j A[j] C[A[j]] B po wykonaniu 10 C po wykonaniu 11
wykonaniu wiersza 10, dla każdego A[j] wartość C[A[j]] jest
9 3 7 [0, 0, 2, 2, 3, 3, 3, 4, 5] [2, 2, 4, 6, 8, 9]
właściwą pozycją dla A[j] w tablicy wyjściowej B.
8 0 2 [0, 0, 2, 2, 3, 3, 3, 4, 5] [1, 2, 4, 6, 8, 9]
Ponieważ jednak elementy nie muszą być parami różne, więc
7 3 6 [0, 0, 2, 2, 3, 3, 3, 4, 5] [1, 2, 4, 5, 8, 9]
C[A[j]] jest zmniejszane o jeden za każdym razem, gdy liczba A[j]
6 2 4 [0, 0, 2, 2, 3, 3, 3, 4, 5] [1, 2, 3, 5, 8, 9]
jest wstawiana do B. Dzięki temu następny element równy A[j]
5 4 8 [0, 0, 2, 2, 3, 3, 3, 4, 5] [1, 2, 3, 5, 7, 9]
(jeśli taki istnieje) zostanie wstawiony do B na pozycję o numerze
4 0 1 [0, 0, 2, 2, 3, 3, 3, 4, 5] [0, 2, 3, 5, 7, 9]
o jeden mniejszym.
3 2 3 [0, 0, 2, 2, 3, 3, 3, 4, 5] [0, 2, 2, 5, 7, 9]
2 5 9 [0, 0, 2, 2, 3, 3, 3, 4, 5] [0, 2, 2, 5, 7, 8]
1 3 5 [0, 0, 2, 2, 3, 3, 3, 4, 5] [0, 2, 2, 4, 7, 8]
Czas sortowania przez zliczanie. Stabilność.
Ważną cechą sortowania przez zliczanie jest stabilność: elementy
o tych samych wartościach występują w tablicy wynikowej w takiej
Pętla for w wierszach 2-3 działa w czasie Ś(k),
samej kolejności jak w tablicy wejściowej.
pętla for w wierszach 4-5 działa w czasie Ś(n),
Istotnie, jeśli i < j i A[i] = A[j] = x, to ponieważ w pętli for w
pętla for w wierszach 6-7 działa w czasie Ś(k),
wierszach 8-12 elementy tablicy A są odwiedzane w kolejności
pętla for w wierszach 8-12 działa w czasie Ś(n).
malejących indeksów, A[j] zostanie umieszczone w tablicy B
Całkowity czas działania procedury wynosi wiec Ś(n + k).
wcześniej niż A[i]. Po umieszczeniu A[j] w tablicy B na pozycji
równej aktualnej wartości C[x], wartość ta zostaje zmniejszona o
W praktyce warto używać sortowania przez zliczanie jeśli
jeden w wierszu 11. W momencie wpisywania A[i] do tablicy B
k = O(n); wtedy czas sortowania wynosi Ś(n).
aktualna wartość C[x] będzie niższa niż była w momencie
Sortowanie przez zliczanie ma czas działania lepszy niż dolna
wpisywania A[j].
granica &!(n log n) z Twierdzenia 9.1, jednak nie jest to sortowanie
Stabilność zazwyczaj jest istotna tylko wtedy, gdy z sortowanymi
za pomocą porównań. Istotnie, w procedurze COUNTING-SORT
elementami są związane dodatkowe dane.
elementy tablicy wejściowej nie są miedzy sobą porównywane.
Ćwiczenie.
Zamiast tego wykorzystujemy wartości elementów jako indeksy w
Które z omówionych na wykładzie algorytmów sortujących za
tablicy.
pomocą porównań są stabilne?
Sortowanie pozycyjne.
W następującej procedurze zakładamy, że każdy element tablicy A
Sortowanie pozycyjne stosuje się do sortowania zbioru rekordów, w
ma d cyfr, gdzie cyfra na pozycji 1 jest najbardziej znacząca, a
których na klucz składa się wiele pól.
cyfra na pozycji d jest najmniej znacząca.
Na przykład sortowanie według daty oznacza sortowanie względem
RADIX-SORT(A, d);
trzech pól: roku, miesiąca i dnia.
1. begin
Sortowanie pozycyjne zbioru dat polega na trzykrotnym
2. for i := d downto 1 do
zastosowaniu pewnego (dowolnego) stabilnego algorytmu
3. posortuj stabilnie tablicę A według pozycji i;
sortującego: najpierw według dni, potem według miesięcy i w
4. end;
końcu według lat.
14.01.2009 06.01.1955 06.01.1955 24.01.1954
Lemat 10.1
26.07.1978 12.08.1978 13.01.2009 06.01.1955
Po wykonaniu k pierwszych iteracji pętli for w wierszach 2,3, liczby
17.02.1988 13.01.2009 14.01.2009 26.07.1978
w tablicy A są posortowane według k najmniej znaczących cyfr.
06.01.1955  > 14.01.2009  > 24.01.1954  > 12.08.1978
Dowód przeprowadzimy indukcyjnie względem k.
24.01.1954 17.02.1988 17.02.1988 17.02.1988
12.08.1978 24.01.1954 26.07.1978 13.01.2009
13.01.2009 26.07.1978 12.08.1978 14.01.2009
Przykłady
Pierwsza iteracja pętli sortuje tablicę według pozycji i = d, czyli
najmniej znaczącej.
329 720 720 329
Załóżmy, że po wykonaniu k - 1 pierwszych iteracji pętli for liczby 457 355 329 355
w tablicy A są posortowane według k - 1 najmniej znaczących cyfr. 657 436 436 436
839  > 457  > 839  > 457
Po k-tej iteracji tablica jest posortowana według k-tej najmniej
436 657 355 657
znaczącej cyfry, a gdy dwie liczby mają takie same k-te najmniej
720 329 457 720
znaczące cyfry, to ponieważ sortowanie wykonywane w wierszu 3
355 839 657 839
jest stabilne, to liczby te znajdują się w tablicy w takiej samej
kolejności, co przed k-tą iteracją.
kot sok bak bak
Stąd i z założenia indukcyjnego wynika, że tablica jest sok bak mak bar
posortowana według k najmniej znaczących cyfr. kos mak bar kos
bar  > mol  > sok  > kot
Stosując Lemat 10.1 dla k = d otrzymujemy:
mol bar mol mak
Lemat 10.2
bak kos kos mol
Procedura RADIX-SORT poprawnie sortuje ciąg liczb d-cyfrowych.
mak kot kot sok
Czas sortowania pozycyjnego.
Załóżmy, że tablica wejściowa A składa się z n liczb d-cyfrowych, a
każda z cyfr należy do przedziału 0..k - 1 (lub ogólniej, do
pewnego ustalonego zbioru k-elementowego).
Wtedy w wierszu 3 procedury RADIX-SORT możemy użyć
sortowania przez zliczanie.
Każda z d iteracji pętli for zajmuje wtedy czas Ś(n + k), a
całkowity czas działania sortowania pozycyjnego wynosi
Ś(d(n + k)).
Gdy d jest stałą, a k = O(n), to sortowanie pozycyjne działa w
czasie Ś(n).