Cześć! Cieszę się, że mnie odwiedziłeś/aś. Zanim przejdziesz do artykułu chciałbym zwrocić Ci uwagę na to, że ten artykuł był pisany kilka lat temu (2012-06-21) miej więc proszę na uwadzę że rozwiązania i przemyślenia które tu znajdziesz nie muszą być aktualne. Niemniej jednak zachęcam do przeczytania.

Sortowanie przez zliczanie jest jednym z nielicznych, prostych w implementacji algorytmów klasy O(n). Dzieje się tak gdyż nie wykorzystuje się tutaj wogóle porównywania. Jedyne operacje to dodawanie, odejmowanie i wypełanie tablicy.

Algorytm:

1. Tablica wejściowa o n długości i największym elementem k. Jest to tablica A[n].

2. Tworzymy tablicę o długości k (długość równa jest największemu elementowi tablicy wejściowej). Będzie to tablica B[k].

3.  Indeksami tablicy B będą wartości tablicy A.

4. Tablica B będzie zawierała ilość wystąpień każdej z liczb z tablicy A.

Dygresja – jeśli tablica A to A={2,3,4,100} to tablica B będzie miała indeksy B[1], B[2], B[3]…B[100].

5. Sumujemy wartości z tablicy B sukcesywnie, tj:

B={0,0,1,2,0,4}

to po sumowaniu będzie to:

B={0,0,1,3,3,7}

Kawałek pseudokodu:

[c]

for i=2 to k do{

B[i]=B[i]+B[i-1]

}

[/c]

Ok, mam nadzieje że to jest w miarę jasne, potem pokażę jakis case study :)

6. Tworzymy tablicę C[n] – tablicę wynikową o rozmiarze n.

7. Tablicę wypełniamy w ten sposób:

7a. Przeglądamy od tyłu tablicę A i…

A[n] = 0;

B[0]=x;

C[x]=A[n];

B[0]=B[0]-1;

aż do momentu skonczenia tablicy A.

Case Study

Posortuj tablicę A= {2,3,5,5,2,5,3,1,1};

Mamy taką tablicę, gdzie n = 9 i k = 5

Tworzymy tablicę B[k];

B[1]=2; //mamy dwa razy 1

B[2]=2; // mamy dwa razy 2

B[3] =2; // dwa razy 3

B[4]=0; //nie mam 4

B[5]=3; // i mamy 3 piątki.

przechodzimy ją, sumując sukcesywnie elementy i tablica

B={2,2,2,0,3} zmienia się w 

B={2,4,6,6,9} – gdzie ostatnia liczba w tablicy B po dodawaniu będzie liczbą cyfr w tablicy A.

Tworzymy tablicę C[n];

i lecimy – przedstawie każdy krok…

1. A[9]=1;

B[1]=2;

C[2]=1;

B[2]=B[2]-1;

Teraz B={1,4,6,6,9}

2.A[8]=1;

B[1]=1; // w poprzednim kroku zmniejszylismy wartosc tej komórki.

C[1]=1;

B[1]=B[1]-1;

Teraz B={0,4,6,6,9}

3. A[7]=3;

B[3]=6;

C[6]=3;

B[3]=B[3]-1;

Teraz B={0,4,5,6,9}

4. A[6]=5;

B[5]=9;

C[9]=5;

B[5]=B[5]-1;

Teraz B={0,4,5,6,8}

5. A[5]=2;

B[2]=4;

C[4]=2;

B[2]=B[2]-1;

Teraz B={0,3,5,6,8}

6. A[4]=5;

B[5]=8;

C[8]=5;

B[5]=B[5]-1;

Teraz B={0,3,5,6,7}

7. A[3]=5;

B[5]=7;

C[7]=5;

B[5]=B[5]-1;

Teraz B={0,3,5,6,6}

8. A[2]=3;

B[3]=5;

C[5]=3;

B[3]=B[3]-1;

Teraz B={0,3,4,6,6}

9. A[1]=2;

B[2]=3;

C[3]=2;

B[2]=B[2]-1;

Teraz B={0,1,4,6,6}

Teraz bierzmy wartości w kolorze pomarańczowym czyli nasze posortowanie wartości:

I	1	2	3	4	5	6	7	8	9
wartości	1	1	2	2	3	3	5	5	5

Chyba jaśniej napisac o tym nie umiem… :)

A może wolisz nowości na mail?