Algorytmy Sortujące - Sortowanie przez zliczanie

Zasadę pracy algorytmu sortowania przez zliczanie jest najlepiej przedstawić za pomocą przykładu.

Przykład:

Posortować rosnąco zbiór danych:

{ 6 3 6 1 4 9 0 1 8 2 6 4 9 3 7 5 9 2 7 3 2 4 1 8 7 0 8 5 8 3 6 2 5 3 }

Czynności wstępne

Dla każdej wartości w zbiorze przygotowujemy licznik i ustawiamy go na 0.

[0:0] [1:0] [2:0] [3:0] [4:0] [5:0] [6:0] [7:0] [8:0] [9:0]

Obieg zliczający

Przeglądamy kolejne elementy zbioru i zliczamy ich wystąpienia w odpowiednich licznikach. Np. element 6 powoduje zwiększenie o 1 licznika nr 6. Po wykonaniu tego obiegu w poszczególnych licznikach mamy ilość wystąpień każdej wartości. W naszym przykładzie otrzymamy:

[0:2] [1:3] [2:4] [3:5] [4:3] [5:3] [6:4] [7:3] [8:4] [9:3]

Teraz poczynając od drugiego licznika sumujemy zawartość licznika oraz jego poprzednika i otrzymujemy:

[0:2] [1:5] [2:9] [3:14] [4:17] [5:20] [6:24] [7:27] [8:31] [9:34]

W wyniku tej operacji w każdym liczniku otrzymaliśmy ilość wartości mniejszych lub równych numerowi licznika, które występują w zbiorze wejściowym. Na przykład:

[0:2] - w zbiorze wejściowym są dwie wartości 0
[1:5] - w zbiorze wejściowym jest pięć wartości mniejszych lub równych 1
[2:9] - w zbiorze wejściowym jest dziewięć wartość mniejszych lub równych 2, itd.

Zwróć uwagę, iż stan licznika określa teraz ostatnią pozycję w zbiorze uporządkowanym, na której należy umieścić wartość równą numerowi licznika:

Wartość:	0	0	1	1	1	2	2	2	2	3	3	3	3	3	4	4	4	5	5	5	6	6	6	6	7	7	7	8	8	8	8	9	9	9
Pozycja:	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34

Obieg dystrybucyjny

Przeglądamy jeszcze raz zbiór wejściowy idąc od ostatniego elementu do pierwszego (aby zachować stabilność sortowania). Każdy element umieszczamy w zbiorze wynikowym na pozycji równej zawartości licznika dla tego elementu. Po wykonaniu tej operacji licznik zmniejszamy o 1. Dzięki temu następna taka wartość trafi na wcześniejszą pozycję.

W naszym przykładzie rozpoczynamy od ostatniej liczby 3. Jej licznik ma zawartość [3:14]. Zatem liczbę 3 umieszczamy w zbiorze wynikowym na pozycji 14 i zmniejszamy o 1 stan licznika otrzymując [3:13]. Kolejna liczba 3 trafi teraz na pozycję 13, itd.

Dla liczby 5 stan licznika wynosi [5:20]. Umieszczamy ją zatem na 20 pozycji i licznik zmniejszamy o 1 otrzymując [5:19].

Postępujemy w ten sam sposób z pozostałymi elementami zbioru. W efekcie zbiór wynikowy będzie posortowany rosnąco:

{ 0 0 1 1 1 2 2 2 2 3 3 3 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 8 8 8 8 9 9 9 }

Podsumowanie

Przyjrzawszy się dokładnie algorytmowi sortowania przez zliczanie możesz zastanawiać się, dlaczego postępujemy w tak dziwny sposób? Przecież mając zliczone wystąpienia każdej wartości w licznikach, możemy je od razu przepisać do zbioru wyjściowego, jak zrobiliśmy w pierwszej wersji algorytmu sortowania kubełkowego. Miałbyś rację, gdyby chodziło jedynie o posortowanie liczb. Jest jednak inaczej.

Celem nie jest posortowanie jedynie samych wartości elementów. Sortowane wartości są zwykle tzw. kluczami, czyli wartościami skojarzonymi z elementami, które wyliczono na podstawie pewnego kryterium Sortując klucze chcemy posortować zawierające je elementy. Dlatego do zbioru wynikowego musimy przepisać całe elementy ze zbioru wejściowego, gdyż w praktyce klucze stanowią jedynie część (raczej małą) danych zawartych w elementach. Zatem algorytm sortowania przez zliczanie wyznacza docelowe pozycje elementów na podstawie reprezentujących je kluczy, które mogą się wielokrotnie powtarzać. Następnie elementy są umieszczane na właściwym miejscu w zbiorze wyjściowym. Prześledź dokładnie podany poniżej algorytm oraz przykładowe programy, a wszystko powinno się wyjaśnić.

Na początek: podrozdziału strony

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
k_min	-	minimalna wartość klucza, k_min ∈ C
k_max	-	maksymalna wartość klucza, k_max ∈ 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 k_min do k_max.

Lista kroków

K01:	Dla i = k_min, k_min + 1,...,k_max: wykonuj: L[i] ← 0
K02:	Dla i = 1,2,...,n: wykonuj: L[d[i].klucz] ← L[d[i].klucz] + 1
K03:	Dla i = k_min + 1, k_min + 2,...,k_max: wykonuj: L[i] ← L[i] + L[i - 1]
K04:	Dla i = n, n - 1,...,1: wykonuj kroki 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

obrazek

Algorytm sortowania przez zliczanie zbudowany jest z kolejno następujących po sobie pętli iteracyjnych.

W pętli nr 1 przygotowujemy liczniki wystąpień poszczególnych kluczy. Ustawiamy je na 0.
W pętli nr 2 przeglądamy kolejne elementy zbioru zwiększając o 1 licznik o numerze równym wartości klucza w sortowanym elemencie zbioru. Po zakończeniu tej pętli w licznikach mamy ilość wystąpień poszczególnych kluczy.
W pętli numer 3 przekształcamy zliczone wartości wystąpień kluczy na ostatnie pozycje elementów z danym kluczem w zbiorze wyjściowym.
W pętli nr 4 ponownie przeglądamy zbiór wejściowy (idąc od końca do początku, aby zachować kolejność elementów równych - inaczej algorytm nie byłby stabilny) i przesyłamy elementy ze zbioru wejściowego do zbioru wyjściowego na pozycję o numerze zawartym w liczniku skojarzonym z kluczem elementu. Po przesłaniu licznik zmniejszamy o 1, aby kolejny element o tej samej wartości klucza trafił na poprzednią pozycję (idziemy wstecz, zatem kolejność elementów o tym samym kluczu zostanie zachowana). Po zakończeniu tej pętli dane w zbiorze wynikowym są posortowane rosnąco. Kończymy zatem algorytm.

Zwróć uwagę, iż algorytm sortowania przez zliczanie nie porównuje ze sobą żadnych elementów zbioru. Teoretycznie udowodniono, iż algorytmy sortujące, które porównują ze sobą elementy zbioru nie mogą osiągać w przypadku ogólnym lepszej klasy złożoności obliczeniowej O(n logn). Ten algorytm nie porównuje elementów, zatem łamie tę granicę.

Aby wyznaczyć klasę złożoności obliczeniowej algorytmu sortowania przez zliczanie, przyjrzyjmy się mu bliżej.

Pętla nr 1 wykonuje m = k_max - k_min + 1 operacji zerowania liczników. Jej czas wykonania jest proporcjonalny do m (ilość możliwych wartości kluczy), zatem ma klasę O(m).
Pętla nr 2 przegląda n elementów zbioru i dla każdego elementu wykonuje operację zwiększania licznika wg numeru klucza. Klasa złożoności wynosi O(n).
Pętla nr 3 wykonuje m - 1 dodawań - klasa złożoności O(m).
Pętla nr 4 przepisuje elementy ze zbioru wejściowego do wyjściowego i zmniejsza o 1 wartości liczników. Ilość wykonanych operacji wynosi n, zatem jest to klasa złożoności O(n).

Z tego porównania widzimy jasno, iż na czas wykonania algorytmu ma wpływ zarówno m (ilość wartości kluczy) jak i n (ilość sortowanych elementów). Stąd klasa złożoności obliczeniowej wynosi O(m + n).

Na początek: podrozdziału strony

Prezentowane programy generują pseudolosowe ciągi 3-literowych wyrazów zbudowanych z liter A, B oraz C. Dla każdego wygenerowanego wyrazu jest wyliczany klucz określający jego alfabetyczną kolejność:

Wyraz	AAA	AAB	AAC	ABA	ABB	...	CCA	CCB	CCC
Klucz	0	1	2	3	4	...	24	25	26

Wyrazy są rosnąco sortowane wg wartości klucza.

C++

// Sortowanie przez zliczanie
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

#include <iostream>
#include <cstdlib>
#include <time.h>

using namespace std;

int main()
{
  const int N    = 80;
  const int KMIN =  0;
  const int KMAX = 26;

  struct
  {
    unsigned klucz;
    char     wyraz[3];
  } d[N],b[N];

  unsigned L[KMAX - KMIN + 1];
  int i,j,v;
            
  cout << "  Sortowanie Przez Zliczanie\n"
          "------------------------------\n"
          "  (C)2005 mgr Jerzy Walaszek\n\n"
          "Przed sortowaniem:\n\n";

// Generujemy losowe elementy do sortowania oraz ich klucze

  srand((unsigned)time(NULL));

  for(i = 0; i < N; i++)
  {
    for(j = 0; j < 3; j++) d[i].wyraz[j] = 65 + rand() % 3;
    d[i].klucz = 0;
    v = 1;
    for(j = 2; j >= 0; j--)
    {
      d[i].klucz += v * (d[i].wyraz[j] - 65);
      v *= 3;
    }
  }

// Wyświetlamy wygenerowane elementy

  for(i = 0; i < N; i++)
    cout << ' ' << d[i].wyraz[0] << d[i].wyraz[1] << d[i].wyraz[2];
  cout << endl;

// Zerujemy liczniki

  for(i = KMIN; i <= KMAX; i++) L[i - KMIN] = 0;

// Zliczamy wystąpienia kluczy

  for(i = 0; i < N; i++) L[d[i].klucz - KMIN]++;

// Obliczamy pozycje końcowe elementów

  for(i = KMIN + 1; i <= KMAX; i++) L[i - KMIN] += L[i - KMIN - 1];

// Przepisujemy elementy z d[ ] do b[ ]

  for(i = N - 1; i >= 0; i--) b[(L[d[i].klucz - KMIN]--) - 1] = d[i];

// Wyświetlamy wyniki w b[ ]

  cout << "Po sortowaniu:\n\n";
  for(i = 0; i < N; i++)
    cout << ' ' << b[i].wyraz[0] << b[i].wyraz[1] << b[i].wyraz[2];
  cout << endl;
  return 0;
}

Pascal

// Sortowanie przez zliczanie
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

const
  N    = 80;
  KMIN =  0;
  KMAX = 26;

// Tutaj definiujemy typ elementu

type
  TElement = record
    klucz : cardinal;
    wyraz : string[3];
  end;

// Zmienne

var
  d,b   : array[1..N] of TElement;
  L     : array[KMIN..KMAX] of cardinal;
  i,j,v : integer;
  s     : string;
begin
  writeln('  Sortowanie Przez Zliczanie  ');
  writeln('------------------------------');
  writeln('  (C)2005 mgr Jerzy Walaszek  ');
  writeln;
  writeln('Przed sortowaniem:');
  writeln;

// Generujemy losowe elementy do sortowania oraz ich klucze

  randomize;
  for i := 1 to N do
  begin
    s := '';
    for j := 1 to 3 do s := s + char(65 + random(3));
    d[i].wyraz := s;
    d[i].klucz := 0;
    v := 1;
    for j := 3 downto 1 do
    begin
      inc(d[i].klucz, v * (ord(d[i].wyraz[j]) - 65));
      v := 3 * v;
    end;
  end;

// Wyświetlamy wygenerowane elementy

  for i := 1 to N do write(d[i].wyraz:4);
  writeln;

// Zerujemy liczniki

  for i := KMIN to KMAX do L[i] := 0;

// Zliczamy wystąpienia kluczy

  for i := 1 to N do inc(L[d[i].klucz]);

// Obliczamy pozycje końcowe elementów

  for i := KMIN + 1 to KMAX do inc(L[i], L[i - 1]);

// Przepisujemy elementy z d[ ] do b[ ]

  for i := N downto 1 do
  begin
    b[L[d[i].klucz]] := d[i];
    dec(L[d[i].klucz]);
  end;

// Wyświetlamy wyniki w b[ ]

  writeln('Po sortowaniu:');
  writeln;
  for i := 1 to N do write(b[i].wyraz:4);
  writeln;
  writeln('Koniec. Nacisnij klawisz Enter...');
  readln;
end.

Basic

' Sortowanie przez zliczanie
'--------------------------------------------------------
' (C)2012 mgr Jerzy Wałaszek
' I Liceum Ogólnokształcące
' im. K. Brodzińskiego
' w Tarnowie
'--------------------------------------------------------

OPTION EXPLICIT

CONST N    = 80
CONST KMIN =  0
CONST KMAX = 26

' Tutaj definiujemy typ elementu

TYPE TElement
    klucz AS UINTEGER
    wyraz AS STRING * 3
END TYPE

' Zmienne

DIM AS TElement d(N),b(N)
DIM AS UINTEGER L(KMIN TO KMAX)
DIM AS INTEGER i,j,v
DIM s AS STRING

PRINT "  Sortowanie Przez Zliczanie  "
PRINT "------------------------------"
PRINT "  (C)2005 mgr Jerzy Walaszek  "
PRINT
PRINT "Przed sortowaniem:"
PRINT

' Generujemy losowe elementy do sortowania oraz ich klucze

RANDOMIZE
FOR i = 1 TO N
  s = ""
  FOR j = 1 TO 3: s += CHR$(65 + INT(RND(1) * 3)): NEXT
  d(i).wyraz = s
  d(i).klucz = 0
  v = 1
  FOR j = 3 TO 1 STEP -1
    d(i).klucz += v * (ASC(MID$(d(i).wyraz,j,1)) - 65)
    v *= 3
  NEXT
NEXT

' Wyświetlamy wygenerowane elementy

FOR i = 1 TO N: PRINT " "; d(i).wyraz;: NEXT
PRINT

' Zerujemy liczniki

FOR i = KMIN TO KMAX: L(i) = 0: NEXT

' Zliczamy wystąpienia kluczy

FOR i = 1 TO N: L(d(i).klucz) += 1: NEXT

' Obliczamy pozycje końcowe elementów

FOR i = KMIN + 1 TO KMAX: L(i) += L(i - 1): NEXT

' Przepisujemy elementy z d[ ] do b[ ]

FOR i = N TO 1 STEP -1
  b(L(d(i).klucz)) = d(i)
  L(d(i).klucz) -= 1
NEXT

' Wyświetlamy wyniki w b[ ]

PRINT "Po sortowaniu:"
PRINT
FOR i = 1 TO N: PRINT " ";b(i).wyraz;: NEXT
PRINT
PRINT "Koniec. Nacisnij dowolny klawisz..."
SLEEP
END

JavaScript

<html>
  <head>
  </head>
  <body>
    <form style="BORDER-RIGHT: #ff9933 1px outset;
                 PADDING-RIGHT: 4px; BORDER-TOP: #ff9933 1px outset;
                 PADDING-LEFT: 4px; PADDING-BOTTOM: 1px;
                 BORDER-LEFT: #ff9933 1px outset; PADDING-TOP: 1px;
                 BORDER-BOTTOM: #ff9933 1px outset;
                 BACKGROUND-COLOR: #ffcc66" name="frmcountingsort">
      <h3 style="text-align: center">Sortowanie Przez Zliczanie</h3>
      <p style="TEXT-ALIGN: center">
        (C)2012 mgr Jerzy Wałaszek - I LO w Tarnowie
      </p>
      <hr>
      <p style="TEXT-ALIGN: center">
        <input onclick="main()" type="button" value="Sortuj" name="B1">
      </p>
      <p id="t_out" style="TEXT-ALIGN: center">...</p>
    </form>

<script language=javascript>

// Sortowanie przez zliczanie
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

var N = 80;
var KMIN = 0;
var KMAX = 26;
var d = new Array();
var b = new Array();
var L = new Array;
var i;

for(i = 0; i < N; i++)
{
  d[i] = new Object();
  b[i] = new Object();
}

function main()
{

  var i,j,t,v;

// Generujemy losowe elementy do sortowania oraz ich klucze

  for(i = 0; i < N; i++)
  {
    d[i].wyraz = String.fromCharCode(65 + Math.floor(Math.random() * 3)) +
                 String.fromCharCode(65 + Math.floor(Math.random() * 3)) +
                 String.fromCharCode(65 + Math.floor(Math.random() * 3));
    d[i].klucz = 0;
    v = 1;
    for(j = 2; j >= 0; j--)
    {
      d[i].klucz += v * (d[i].wyraz.charCodeAt(j) - 65);
      v *= 3;
    }
  }

// Wyświetlamy wygenerowane elementy

  t = "Przed sortowaniem:<BR><BR>";
  for(i = 0; i < N; i++) t += " " + d[i].wyraz;
  t += "<BR><BR>";

// Zerujemy liczniki

  for(i = KMIN; i <= KMAX; i++) L[i - KMIN] = 0;

// Zliczamy wystąpienia kluczy

  for(i = 0; i < N; i++) L[d[i].klucz - KMIN]++;

// Obliczamy pozycje końcowe elementów

  for(i = KMIN + 1; i <= KMAX; i++) L[i - KMIN] += L[i - KMIN - 1];

// Przepisujemy elementy z d[ ] do b[ ]

  for(i = N - 1; i >= 0; i--) b[(L[d[i].klucz - KMIN]--) - 1] = d[i];

// Wyświetlamy wyniki w b[ ]

  t += "Po sortowaniu:<BR><BR>";
  for(i = 0; i < N; i++) t += " " + b[i].wyraz;
  document.getElementById("t_out").innerHTML = t;
}

</script> 

  </body>
</html>

Wynik:

Sortowanie Przez Zliczanie
------------------------------
(C)2005 mgr Jerzy Walaszek

Przed sortowaniem:

CAC CAA AAB BAB AAC CAB CBC BCC ACC AAA ACA BCC ABC CAC ACC CAA ACB BCC CAB CAA
ACA CCB BAC BCA ABB ABB CAB CAC AAA BCA BCC ACB AAA BAA CAC AAB BCA CCB CAB CAA
BCB BBB BBB BCB BCB CAA BAA CCC BAA BCC AAC CBC BAA BCA BAA CAC ABA ABC CAA CCC
CBA ABC BCA BBA ACC BBB CBC ACA ABC ACC BBA CCC BBA CAB BBC BBB ABB AAC CCB BCA

Po sortowaniu:

AAA AAA AAA AAB AAB AAC AAC AAC ABA ABB ABB ABB ABC ABC ABC ABC ACA ACA ACA ACB
ACB ACC ACC ACC ACC BAA BAA BAA BAA BAA BAB BAC BBA BBA BBA BBB BBB BBB BBB BBC
BCA BCA BCA BCA BCA BCA BCB BCB BCB BCC BCC BCC BCC BCC CAA CAA CAA CAA CAA CAA
CAB CAB CAB CAB CAB CAC CAC CAC CAC CAC CBA CBC CBC CBC CCB CCB CCB CCC CCC CCC

Na początek: podrozdziału strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Sortowanie przez zliczanie
Counting Sort

Algorytm

Przykład:

Czynności wstępne

Obieg zliczający

Obieg dystrybucyjny

Podsumowanie

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Schemat blokowy

Przykładowe programy

Sortowanie Przez Zliczanie

Sortowanie przez zliczanie Counting Sort

Algorytm

Przykład:

Czynności wstępne

Obieg zliczający

Obieg dystrybucyjny

Podsumowanie

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Schemat blokowy

Przykładowe programy

Sortowanie Przez Zliczanie

Sortowanie przez zliczanie
Counting Sort