Sortowanie przez zliczanie – omówienie algorytmu

Algorytm sortowania przez zliczanie polega na zliczeniu wystąpień kluczykluczkluczy w danym zbiorzezbiórzbiorze. W przypadku tego typu sortowania domyślnie operujemy na samych liczbach, choć po dostosowaniu algorytmu możliwe jest również sortowanie znaków.

Za pomocą omawianego algorytmu nie można posortować liczb rzeczywistych. Wynika to z faktu, że pomiędzy dwiema dowolnymi liczbami całkowitymi występuje nieskończenie wiele liczb rzeczywistych.

Warto również podkreślić, że algorytm sortowania przez zliczanie może być używany dla zbiorów, w których znajdują się liczby ujemne.

Omówmy algorytm na przykładzie.

Załóżmy, że chcemy niemalejąco posortować następujący zbiór danych:

{ 2, 7, 5, 2, 3, 9, 1, 2, 1, 5, 1, 9, 4, 8, 7 }.

Jego największa wartość to $9$, a najmniejsza to $1$. Dla tego zbioru k (różnica między wartością maksymalną a minimalną powiększoną o $1$) wynosi 9 - 1 + 1 = 9, zatem k = 9.

Tworzymy zatem dziewięcioelementową tablicę pomocniczą, którą wypełnimy zerami – dla każdej wartości w zbiorze przygotujemy licznik, a jego wartość ustawimy na $0$.

Dla czytelności przedstawimy to w formie tabeli.

Sprawdzamy elementy zbioru. W następnym kroku zliczamy ich wystąpienia w odpowiednich licznikach, np.: zliczenie elementu o wartości $1$ powoduje zwiększenie o $1$ wartości licznika elementu o indeksie $0$, a zliczenie elementu o wartości $2$ powoduje zwiększenie o $1$ wartości licznika elementu o indeksie $1$.

W poszczególnych licznikach znajdują się liczby wystąpień każdej wartości.

W zbiorze znajdują się trzy elementy o wartości $1$:

{ 2, 7, 5, 2, 3, 9, 1, 2, 1, 5, 1, 9, 4, 8, 7 }

W kolumnie licznik wpisujemy zatem wartość $3$ dla wiersza, w którym zliczamy liczbę wystąpień elementu zbioru o wartości $1$. Podobnie postępujemy w przypadku pozostałych elementów zbioru.

Dla podanego przykładu tabela zliczeń wygląda następująco:

W następnym kroku, zaczynając od drugiego licznika, sumujemy zawartość danego licznika oraz jego poprzednika. Dzięki tej operacji dokładnie wiemy, gdzie w tablicy wynikowej umieścić każdy z elementów tablicy wejściowej.

Gdy zliczamy wystąpienia poszczególnych liczb w tablicy wejściowej, otrzymujemy tablicę, która mówi nam, ile razy występuje każda liczba. Jednak aby posortować tablicę wejściową, potrzebujemy wiedzieć, gdzie dokładnie umieścić każdy element w tablicy wynikowej.

Sumując wartość licznika z jego poprzednikiem, przekształcamy tablicę pomocniczą w taki sposób, że każda wartość w tej tablicy będzie przechowywać informację, ile elementów o wartości mniejszej lub równej danej liczbie znajduje się w tablicy wejściowej.

W zaprezentowanej tabeli możemy zobaczyć, ile liczb mniejszych lub równych danej wartości (kolumna element zbioru) znajduje się w zbiorze (kolumna licznik).

Zatem w zbiorze wejściowym znajdują się trzy wartości równe $1$ lub mniejsze od $1$. Oznacza to, że w posortowanej tablicy liczby mniejsze niż $1$ lub równe $1$ zajmują trzy pierwsze miejsca (czyli indeksy od $0$ do $2$ włącznie). Wiedząc to, możemy umieścić wszystkie elementy o wartości $1$ na odpowiednich miejscach tablicy wynikowej.

Oto posortowany zbiór danych:

{ 1, 1, 1, 2, 2, 2, 3, 4, 5, 5, 7, 7, 8, 9, 9 }

Algorytm zapisany za pomocą pseudokodu

Sortowanie przez zliczanie liczb całkowitych – pseudokod

Zapoznajmy się z algorytmem zapisanym za pomocą pseudokodu.

Specyfikacja problemu:

Dane:

• n – długość tablicy, liczba naturalna

• Wej[0...n - 1] – tablica liczb całkowitych

Wynik:

• Wyj[0...n - 1] – posortowana niemalejąco tablica liczb całkowitych

Potrzebne nam będą trzy tablice:

• Wej[] – tablica wejściowa, zawierająca liczby, które chcemy posortować;

• pom[] – tablica pomocnicza, którą wykorzystamy do zliczania wystąpień danych;

• Wyj[] – tablica wynikowa, w której zapiszemy posortowane dane.

W algorytmie sortowania przez zliczanie istotne jest określenie najmniejszego oraz największego elementu tablicy.

min ← Wej[0]
max ← Wej[0]
dla i = 1, 2, ..., n - 1 wykonuj
    jeżeli Wej[i] < min
        min ← Wej[i]
    jeżeli Wej[i] > max
        max ← Wej[i]

W następnym kroku utworzymy tablicę pomocniczą pom[]. By to zrobić, utworzymy najpierw zmienną k, której przypiszemy różnicę maksymalnej i minimalnej wartości tablicy wejściowej Wej[], powiększoną o $1$.

Zmienna k będzie przechowywać wartość będącą długością tablicy pomocniczej pom.

k  ← max - min + 1
pom[k] ← utwórz pustą tablicę

Kolejnym krokiem jest wyzerowanie tablicy pomocniczej pom[], czyli przypisanie wszystkim jej elementom wartości $0$ (ponieważ jeszcze nie wiemy, ile razy element o danej wartości występuje w tablicy do posortowania Wej[]).

Wykorzystamy pętlę dla, która będzie iterować po wszystkich indeksach tablicy pomocniczej pom[].

dla i = 0, 1, 2 ..., k - 1 wykonuj
	pom[i] ← 0

Następnie policzymy, ile razy dana wartość występuje w tablicy liczb do posortowania Wej[].

Ponownie wykorzystamy pętlę dla. Będzie ona  iterować po tablicy wejściowej, zwiększając wartość spod indeksu przypisanego danemu kluczowi za każdym razem, gdy napotka dany element.

W tym przypadku kluczami są wartości z przedziału [min; max].

Wartość indeksu obliczamy zgodnie ze wzorem: wartość - min, gdzie przez wartość rozumiemy wartość reprezentowaną przez klucz.

W sortowaniu przez zliczanie zakładamy, że tablica wejściowa składa się z liczb całkowitych, które należą do pewnego zakresu. Wiemy, że zmienna min przechowuje wartość najmniejszą, a zmienna max największą. Celem przesunięcia jest ograniczenie rozmiaru tablicy pom[] do dokładnie tego zakresu liczb, które pojawiają się w tablicy wejściowej Wej[].

Gdybyśmy użyli wartości z tablicy Wej[] bezpośrednio jako indeksów dla tablicy pomocniczej pom[], tablica pom[] musiałaby mieć rozmiar co najmniej równy max. Jednak dzięki przesunięciu wartości o wartość zmiennej min możemy zmniejszyć rozmiar tablicy pomocniczej pom[] do dokładnie max - min + 1. Jakie ma to dla nas znaczenie?

Zapoznajmy się z przykładem, który to zobrazuje.

Podsumowując: przesunięcie Wej[i] - min umożliwia korzystanie z tablicy pomocniczej pom[] o minimalnym koniecznym rozmiarze, jednocześnie zapewniając poprawne indeksowanie wartości w tablicy. Pomaga to w zachowaniu wydajności i efektywnego wykorzystania pamięci w algorytmie sortowania przez zliczanie.

dla i = 0, 1, 2..., n - 1 wykonuj
	pom[Wej[i] - min] ← pom[Wej[i] - min] + 1

Wypełniliśmy tablicę pomocniczą, w której przechowujemy informacje dotyczące wystąpień poszczególnych wartości.

W kolejnym kroku zaktualizujemy wartości tablicy pomocniczej pom[] – czyli zaczynając od drugiego elementu, dodamy do siebie wartość licznika danego elementu oraz jego poprzednika.

W tym miejscu ustalamy, ile jest liczb nie mniejszych od liczby przypisanej do danego klucza.

dla i = 1, 2, ..., k - 1 wykonuj
	pom[i] ← pom[i] + pom[i - 1]

Po wykonaniu operacji możemy przejść do wypełniania tablicy wyjściowej. Zaczynamy więc ponownie po niej iterować, jednak tym razem od końca.

Iterujemy po tablicy wejściowej Wej[], zaczynając od ostatniego elementu. Dla każdego z elementów tablicy wejściowej znajdujemy odpowiedni indeks w tablicy wynikowej Wyj[] na podstawie wartości w tablicy pomocniczej pom[].

Następuje końcowy etap sortowania tablicy wejściowej Wej[].

Umieszczamy element w tablicy wynikowej i aktualizujemy wartość w tablicy pomocniczej.

W tym celu tworzymy zmienną element, której przypisujemy wartość analizowanego elementu tablicy wejściowej Wej[].

Następnie tworzymy zmienną indeksWTablicyWynikowej, której przypisujemy różnicę odpowiedniej wartości tablicy pomocniczej (przechowywanej pod indeksem równym różnicy wartości zmiennych element oraz min) oraz liczby 1.

W kolejnym kroku elementowi tablicy pom[] przechowywanemu pod indeksem równym różnicy wartości zmiennych element oraz min przypiszemy wartość różnicy wartości tablicy pomocniczej (przechowywanej pod indeksem równym różnicy wartości zmiennych element oraz min) oraz liczby 1.

Następnie elementowi tablicy wyjściowej Wyj[] o indeksie równym wartości zmiennej indeksWTablicyWynikowej przypiszemy wartość zmiennej element.

dla i = n - 1, ..., 0 wykonuj
	element ← Wej[i]
	indeksWTablicyWynikowej ← pom[element - min] - 1
    pom[element - min] ← pom[element - min] - 1
    Wyj[indeksWTablicyWynikowej] ← element

W przedstawionym fragmencie pseudokodu dla danej liczby z tablicy wejściowej odnajdujemy odpowiadający jej indeks w tablicy pomocniczej (będzie on jednak musiał być pomniejszony o najmniejszą wartość, żeby uwzględnić przesunięcie przedziału wartości). Odczytujemy wartość spod tego indeksu, jednocześnie dekrementującdekrementacjadekrementując go, a następnie umieszczamy liczbę w tablicy wynikowej. Po zakończeniu iterowania możemy zwrócić tablicę wyjściową, w której otrzymaliśmy posortowany zbiór z tablicy wejściowej.

Algorytm sortowania przez zliczanie jest stabilnysortowanie stabilnestabilny – umieszcza wartości w tablicy wyjściowej z zachowaniem ich kolejności w tablicy wejściowej.

Kompletny pseudokod algorytmu sortowania przez zliczanie prezentuje się następująco:

min ← Wej[0]
max ← Wej[0]
dla i = 1, 2, ..., n - 1 wykonuj
    jeżeli Wej[i] < min
        min ← Wej[i]
    jeżeli Wej[i] > max
        max ← Wej[i]
        
k  ← max - min + 1
pom[k] ← utwórz pustą tablicę

dla i = 0, 1, 2 ..., k - 1 wykonuj
	pom[i] ← 0
    
dla i = 0, 1, 2..., n - 1 wykonuj
	pom[Wej[i] - min] ← pom[Wej[i] - min] + 1

dla i = 1, 2, ..., k - 1 wykonuj
	pom[i] ← pom[i] + pom[i - 1]

dla i = n - 1, ..., 0 wykonuj
	element ← Wej[i]
	indeksWTablicyWynikowej ← pom[element - min] - 1
    pom[element - min] ← pom[element - min] - 1
    Wyj[indeksWTablicyWynikowej] ← element

Złożoność pamięciowa oraz czasowa

Algorytm sortowania przez zliczanie charakteryzuje się złożonością pamięciowązłożoność pamięciowazłożonością pamięciową $O(n + k)$ i złożonością czasowązłożoność czasowazłożonością czasową $O(n + k)$, gdzie:

• $n$ to rozmiar tablicy wejściowej;

• $k$ to rozmiar tablicy pomocniczej; zakres wartości znajdujących się w tablicy wejściowej.

Wpływ wartości n i k na wykonanie algorytmu:

• wartość n:

  • odnosi się do liczby elementów w tablicy wejściowej Wej[];

  • ma bezpośredni wpływ na czas potrzebny na przeglądanie tej tablicy w różnych etapach algorytmu, takich jak znajdowanie wartości minimalnej i maksymalnej, zliczanie wystąpień i umieszczanie elementów w odpowiedniej kolejności w tablicy wynikowej;

  • większa wartość n oznacza, że te operacje zajmą więcej czasu.

• wartość k:

  • reprezentuje zakres wartości w tablicy wejściowej obliczany jako max - min + 1;

  • ma wpływ na rozmiar tablicy pomocniczej pom[], która przechowuje zliczenia poszczególnych wartości;

  • większa wartość k oznacza, że tablica pomocnicza będzie większa i jej inicjalizacja oraz operacje na niej (takie jak kumulacja liczb) zajmą więcej czasu.

Algorytm działa najszybciej, gdy zakres sortowanych wartości, czyli k, jest względnie mały w stosunku do liczby wartości do posortowania, czyli n. W takiej sytuacji:

• Tablica pomocnicza pom[] jest relatywnie mała, co sprawia, że operacje na niej są szybsze.

• Mniejszy zakres wartości k oznacza, że algorytm potrzebuje mniej dodatkowej pamięci, co jest korzystne w kontekście złożoności pamięciowej.

• Mniejsza wartość k minimalizuje również różnicę między złożonością pamięciową a czasową algorytmu, czyniąc go bardziej efektywnym.

W sytuacjach, gdy k jest porównywalne lub nawet większe niż n, algorytm może być mniej efektywny ze względu na wzrost zarówno złożoności czasowej, jak i pamięciowej.

Słownik