Sortowanie przez zliczanie

Autor podstrony: Krzysztof Zajączkowski

Stronę tą wyświetlono już: 6878 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:

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:

var s = {"data1": 0, "data2": 0, "data3": 0, "data4": 0, "data5": 0}; var d = ["data1", "data3", "data2", "data2", "data1", "data5", "data3", "data3", "data2", "data5"]; for(var i = 0; i < d.length; i++){ s[d[i]] ++; } for(key in s){ document.write("<p>Klucz " + key + " wystąpił " + s[key] + " razy</p>"); }

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

Propozycje książek