Sortowanie przez zliczanie (countingsort)
Sortowanie przez zliczanie ma jedną potężną zaletę i jedną równie potężną wadę:
" Zaleta: działa w czasie liniowym (jest szybki)
" Wada: może sortować wyłącznie liczby całkowite
Obydwie te cechy wynikają ze sposobu sortowania. Polega ono na liczeniu, ile razy
dana liczba występuje w ciągu, który mamy posortować. Następnie wystarczy
utworzyć nowy ciąg, korzystając z danych zebranych wcześniej. Np. mamy
posortować ciąg: 3,6,3,2,7,1,7,1. Po zliczeniu (w jednym korku) operujemy danymi na
temat liczności poszczególnych liczb:
" Liczba 1 występuje 2 razy
" Liczba 2 występuje 1 raz
" Liczba 3 występuje 2 razy
" Liczba 4 występuje 0 razy
" Liczba 5 występuje 0 razy
" Liczba 6 występuje 1 raz
" Liczba 7 występuje 2 razy
Na podstawie tych danych tworzymy ciąg: 1,1,2,3,3,6,7,7. Jest to ciąg wejściowy, ale
posortowany. Należy zauważyć trzy ważne rzeczy:
1. Proces zliczania odbył się w jednym kroku
2. Nie doszło do ani jednej zamiany elementów
3. Proces tworzenia tablicy wynikowej odbył się w jednym kroku
Algorytmy ten posiada jednak również wady:
1. Do przechowywania liczby wyrazów ciągu musimy użyć tablicy, o liczbie
elementów równej największemu elementowi ciągu
2. Sortować można jedynie liczby całkowite
Specyfikacja problemu
Dane wejściowe
d[ ] - zbiór elementów do posortowania. Każdy element posiada pole klucz, wg którego dokonuje się
sortowania. Pole klucz jest liczbą całkowitą. Indeksy elementów rozpoczynają się od 1.
n - ilość elementów w zbiorze d[ ]. n " N
kmin - minimalna wartość klucza, kmin " C
kmax - maksymalna wartość klucza, kmax " C
Dane wyjściowe
b[ ] - zbiór z posortowanymi elementami ze zbioru d[ ]. Indeksy elementów rozpoczynają się od 1.
Zmienne pomocnicze
i - zmienna dla pętli iteracyjnych, i " C
L[ ] - tablica liczników wartości kluczy. Elementy są liczbami całkowitymi. Indeksy przebiegają kolejne
wartości od kmin do kmax.
Lista kroków
K01: Dla i = kmin, kmin + 1,...,kmax: wykonuj L[i] �! 0
K02: Dla i = 1,2,...,n: wykonuj L[d[i].klucz] �! L[d[i].klucz] + 1
K03: Dla i = kmin + 1, kmin + 2,...,kmax: wykonuj L[i] �! L[i] + L[i - 1]
K04: Dla i = n, n - 1,...,1: wykonuj K05...K06
K05: b[ L[ d[i].klucz ] ] �! d[i]
K06: L[ d[i].klucz ] �! L[ d[i].klucz ] - 1
K07: Zakończ
SCHEMAT BLOKOWY
PASCAL C++
const #include
N = 80; #include
KMIN = 0; #include
KMAX = 26; using namespace std;
// Tutaj definiujemy typ elementu int main()
type {
TElement = record const int N = 80;
klucz : cardinal; const int KMIN = 0;
wyraz : string[3]; const int KMAX = 26;
end;
// Zmienne struct
var {
d,b : array[1..N] of TElement; unsigned klucz;
L : array[KMIN..KMAX] of char wyraz[3];
cardinal;
} d[N],b[N];
i,j,v : integer;
s : string;
unsigned L[KMAX - KMIN + 1];
begin
int i,j,v;
// Generujemy losowe elementy do
//sortowania oraz ich klucze
// Generujemy losowe elementy do
randomize;
//sortowania oraz ich klucze
for i := 1 to N do
begin
srand((unsigned)time(NULL));
s := '';
for j:=1 to 3 do
for(i = 0; i < N; i++)
s:=s+char(65+random(3));
{
d[i].wyraz := s;
for(j = 0; j < 3; j++)
d[i].klucz := 0;
d[i].wyraz[j] = 65 + rand() % 3;
v := 1;
d[i].klucz = 0;
for j := 3 downto 1 do
v = 1;
begin
for(j = 2; j >= 0; j--)
inc(d[i].klucz, v *
{
(ord(d[i].wyraz[j]) - 65));
d[i].klucz += v * (d[i].wyraz[j]
v := 3 * v;
- 65);
end;
v *= 3;
end;
}
}
// Wyświetlamy wygenerowane elementy
// Wyświetlamy wygenerowane elementy
for i := 1 to N do
for(i = 0; i < N; i++)
write(d[i].wyraz:4);
cout << ' ' << d[i].wyraz[0] <<
writeln;
d[i].wyraz[1] << d[i].wyraz[2];
// Zerujemy liczniki
cout << endl;
for i := KMIN to KMAX do L[i] := 0;
// Zerujemy liczniki
// Zliczamy wystąpienia kluczy
for(i = KMIN; i <= KMAX; i++) L[i -
for i := 1 to N do KMIN] = 0;
inc(L[d[i].klucz]);
// Obliczamy pozycje końcowe elementów // Zliczamy wystąpienia kluczy
for i := KMIN + 1 to KMAX do for(i = 0; i < N; i++) L[d[i].klucz -
inc(L[i], L[i - 1]); KMIN]++;
// Przepisujemy elementy z d[ ] do b[ ] // Obliczamy pozycje końcowe elementów
for i := N downto 1 do for(i = KMIN + 1; i <= KMAX; i++) L[i
- KMIN] += L[i - KMIN - 1];
begin
b[L[d[i].klucz]] := d[i];
// Przepisujemy elementy z d[ ] do b[ ]
dec(L[d[i].klucz]);
end;
for(i = N - 1; i >= 0; i--)
b[(L[d[i].klucz - KMIN]--) - 1] = d[i];
// Wyświetlamy wyniki w b[ ]
// Wyświetlamy wyniki w b[ ]
writeln('Po sortowaniu:');
writeln;
cout << "Po sortowaniu:\n\n";
for i := 1 to N do
for(i = 0; i < N; i++)
write(b[i].wyraz:4);
cout << ' ' << b[i].wyraz[0] <<
writeln;
b[i].wyraz[1] << b[i].wyraz[2];
writeln('Koniec. Nacisnij klawisz
cout << endl;
Enter...');
return 0;
readln;
}
end.