Lekcja: "Algorytmy sortujące - sortowanie przez scalanie, sortowanie przez zliczanie"
Sortowanie przez zliczanie (counting sort)
Kolejny algorytm, którego zasadę działania poznamy to sortowanie przez zliczanie. W metodzie tej stosowane są pewne założenia wobec sortowanego zbioru.
Algorytm posiada liniową klasę złożoności obliczeniowej O(n+k)
(n – oznacza liczebność zbioru, k – rozpiętość danych, czyli w przypadku liczb: powiększoną o 1 różnicę między maksymalną, a minimalną wartością, np. rozpiętość liczb w Dużym Lotku wynosi 48 + 1= 49).
Sortowanie przez zliczanie, oprócz tego że jest szybki, ma swoje dwie poważne wady. Po pierwsze - do tego sortowania potrzebna jest dodatkowa pamięć n+k (czyli nie jest to sortowanie w miejscu),a po drugie - tym sposobem można sortować tylko liczby całkowite z ograniczonego zakresu.
