Sortowanie przez zliczanie – algorytm oraz implementacja w C++

Klasycznie już, wraz z kolejnym piątym dniem tygodnia, przed wami kolejna część „Piątku z sortowaniem”. Tym razem rozgryziemy wspólnie sposób działania algorytmu sortowania przez zliczanie (counting sort) oraz przyjrzymy się przykładowej implementacji.

Algorytm

Zasada działania algorytmu sortowania przez zliczanie, jest łudząco podobna do algorytmu sortowania kubełkowego, omawianego tydzień temu. Ponownie zliczać będziemy wystąpienia poszczególnych elementów, by na końcu stworzyć tablicę, którą wypełnimy odpowiednimi wartościami. Ich ilość podyktowana będzie przez liczniki.

Algorytm ten podzielony jest na kilka kroków:

  1. Wyznaczamy wartość ymin i ymax.
  2. Tworzymy tablicę liczników, której rozmiar obliczamy ze wzoru  ymax – ymin + 1.
  3. Przechodzimy przez zbiór wejściowy, zliczając wystąpienia poszczególnych elementów przy pomocy tablicy liczników.
  4. Do tablicy docelowej dodajemy elementy, których wartość podyktowana jest przez wzór: indeks tablicy liczników + ymin, a ilość tych elementów przez wartość licznika na rozpatrywanej pozycji.

W ten właśnie sposób otrzymujemy posortowaną tablicę.

Przykład

By w pełni zrozumieć ten algorytm, spójrzmy na przykład. Weźmy zbiór {4, 2, 5, 6, 1, 4, 6, 6, 4}. W pierwszym kroku wyznaczmy wartość maksymalną i minimalną w danym zbiorze. W tym przypadku wynoszą one:

ymin = 1;  ymax =6

Korzystając ze wzoru ymax – ymin + 1 wiemy, że tablica liczników, musi mieć rozmiar 6. Na potrzeby pisemnego przykładu stwórzmy ją według wzorca [ wartość zliczanego elementu: liczba wystąpień; …]:

[1:0; 2:0; 3:0; 4:0; 5:0; 6:0]

Idąc zgodnie z krokami algorytmu, zliczamy teraz liczbę wystąpień poszczególnych elementów, poruszając się od początku do końca zbioru. Daje nam to wyjściową tablicę liczników:

[1:1; 2:1; 3:0; 4:3; 5:1; 6:3]

Po zliczeniu wystąpień elementów, możemy zabrać się za tworzenie nowego zbioru, dodając do niego elementy o wartości i ilości podyktowanej przez licznik. Nasz zbiór, będzie wyglądał następująco:

{1, 2, 4, 4, 4, 5, 6, 6, 6}

Zbiór ten jest posortowanym zbiorem wejściowym, co kończy nasz algorytm. By jeszcze lepiej zrozumieć działanie tego algorytmu spójrzmy na wizualizację powyższego przykładu:

Sortowanie przez zliczanie – implementacja w C++

Trochę teorii

Algorytm sortowania przez zliczanie jest niezwykle szybki – ma złożoność obliczeniową O(n+m), gdzie m to rozpiętość danych. Podobnie jak w przypadku algorytmu sortowania kubełkowego, gdy sortujemy zbiór o dużej liczności i stosunkowo małym zakresie wartości elementów, algorytm zbliża się do złożoności O(n) – czyli złożoności liniowej.

Oczywiście, nic nie może być idealne i tak jest również w przypadku tegoż algorytmu. Po pierwsze, w przypadku zbiorów o większej rozpiętości danych, radzi on sobie znacznie gorzej, niż chociażby sortowanie przez kopcowanie. Kolejną wadą, jest potrzeba znajomości zakresu wartości zbioru, przed rozpoczęciem sortowania. Jeśli nie znamy zakresu, efektywność algorytmu ponownie spada, z powodu potrzeby przejścia przez cały zbiór i znalezienia największego oraz najmniejszego elementu. Złożoność czasowa zmienia się więc na O(2n+m). Dodatkowo, jest on praktycznie niemożliwy do wykorzystania, w przypadku liczb ułamkowych, chyba że ograniczymy się do liczb konkretnego rzędu. Mimo tego, że ograniczenie rzędu umożliwia zaimplementowanie algorytmu, w takim scenariuszu, jego efektywność tragicznie spada. Czemu tak jest?

Przypadek nadzwyczajny

Za przykład weźmy malutki zbiór ułamków dziesiętnych, ograniczonych do dwóch miejsc po przecinku np.: { 2.31, 1.89, 2.11 }. W przypadku takiego zbioru, mimo tego, że wartości elementów nie różnią się od siebie znacząco, musimy stworzyć tablicę liczników o rozmiarze, aż 43! Nasza rozpiętość wartości jest więc dość duża. Jeśli spojrzycie, na funkcję sortowania w implementacji powyżej, możecie zauważyć, że w trzeciej z pętli, będziemy musieli przejść przez całą tablicę liczników, by uzupełnić tablicę docelową. Wyobraźcie sobie, co by się stało, dla zakresu od 0.99 do 100.99.

W praktyce, algorytm ten jest więc wykorzystywany, jedynie dla liczb całkowitych i to tylko w specyficznych przypadkach, przez potrzebę znajomości zakresu.

Podsumowanie

Płynąc meandrami wiedzy algorytmicznej, minęliśmy kolejny kamień milowy w postaci sortowania przez zliczanie. Jeśli chcecie jak najlepiej przygotować się na nadchodzącą maturę z informatyki i wciąż jesteście głodni wiedzy, zapraszam was za tydzień na kolejny wpis z serii „Piątek z sortowaniem”. Zajrzyjcie również, do zakładki matura z informatyki, gdzie znajdziecie inne materiały do nauki.

You Might Also Like
Dodaj komentarz