Sortowanie przez zliczanie

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

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

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

Komentarze