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ć.

do podrozdziału do 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

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).

do podrozdziału do 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
// 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 << 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 << endl;
  system("pause");
  return 0;
}

Pascal

// Sortowanie przez zliczanie
//---------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// 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;
  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;
  writeln('Nacisnij Enter...');
  readln;
end.

Basic

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

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
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
PRINT "Nacisnij dowolny klawisz..."
SLEEP
END

Python (dodatek)

# Sortowanie przez zliczanie
#---------------------------
# (C)2026 mgr Jerzy Wałaszek
# I Liceum Ogólnokształcące
# w Tarnowie

import random

n    = 80
kmin =  0
kmax = 26

class List:
    def __init__(self):
        self.klucz = 0
        self.wyraz = []

d = [List() for _ in range(n)]
b = [List() for _ in range(n)]
l = [0] * (kmax - kmin + 1)

print("Sortowanie Przez Zliczanie")
print("--------------------------")
print("(C)2026 mgr Jerzy Wałaszek")
print()
print("Przed sortowaniem:")
print()

# Generujemy losowe elementy
# do sortowania oraz ich klucze
for i in range(n):
    for j in range(3):
        d[i].wyraz.append(random.randrange(65,68))
    v = 1
    for j in reversed(range(3)):
        d[i].klucz += v*(d[i].wyraz[j]-65)
        v *= 3

# Wyświetlamy wygenerowane elementy
for i in range(n):
    print(" ",
          chr(d[i].wyraz[0]),
          chr(d[i].wyraz[1]),
          chr(d[i].wyraz[2]),
          sep="",end="")
print()
print()

# Zliczamy wystąpienia kluczy
for i in range(n):
    l[d[i].klucz - kmin] += 1

# Obliczamy pozycje końcowe elementów
for i in range(kmin+1,kmax+1):
    l[i - kmin] += l[i - kmin - 1]

# Przepisujemy elementy z d[] do b[]
for  i in reversed(range(n)):
    b[l[d[i].klucz-kmin] - 1] = d[i]
    l[d[i].klucz - kmin] -= 1

# Wyświetlamy wyniki w b[]
print("Po sortowaniu:")
print()
for i in range(n):
    print(" ",
          chr(b[i].wyraz[0]),
          chr(b[i].wyraz[1]),
          chr(b[i].wyraz[2]),
          sep="", end="")
print()
print()
input("Naciśnij Enter...")

Wynik:

Sortowanie Przez Zliczanie
--------------------------
(C)2026 mgr Jerzy Wałaszek

Przed sortowaniem:

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

Po sortowaniu:

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

Naciśnij Enter...

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
// 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>

do podrozdziału do 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