Stronę tą wyświetlono już: 7324 razy

Sortowanie przez zliczanie jest dość prostym algorytmem sortującym dane, które muszą spełniać warunek taki, że znany jest skończony zbiór możliwych do wystąpienia w sortowanej tablicy wartości. Najłatwiej jest zastosować ten algorytm dla danych w postaci liczb całkowitych np. z zakresu od 0 do 5 z krokiem 1. Do sortowania będzie potrzebna dodatkowa pamięć w postaci k-elementowej tablicy s, gdzie wartość zapisana pod danym indeksem i tablicy s będzie odpowiadała liczbie wystąpień w sortowanej tabeli danych d liczby odpowiadającej indeksowi i.

Niechaj więc będzie dana tablica danych d = [0, 2, 4, 3, 5, 1, 3, 3, 4, 5] i wiadomo jest, że wartości występujące w tabeli d przyjmują wartości: 0, 1, 2, 3, 4 lub 5 to po zliczeniu (posortowaniu) dane tablica s = [1, 1, 1, 3, 2, 2] co oznacza:

• s[0] = 1 - liczba 0 wystąpiła 1 raz;
• s[1] = 1 - liczba 1 wystąpiła 1 raz;
• s[2] = 1 - liczba 2 wystąpiła 1 raz;
• s[3] = 3 - liczba 3 wystąpiła 3 razy;
• s[4] = 2 - liczba 4 wystąpiła 2 razy;
• s[5] = 2 - liczba 5 wystąpiła 2 razy

Jak widać, dane zostały posortowane i pozliczane za jednym razem, niestety zliczanie wymaga odpowiedniej interpretacji uzyskanych danych. Ważne jest również ułożenie elementów w tablicy s, która określa sposób sortowania danych.

Oto przykładowy sposób sortowania przez zliczanie napisany w JavaScript:

Złożoność obliczeniowa algorytmu jest liniowa i wynosi n, czyli tyle, ile liczebność zbioru sortowanego.