Sortowanie przez zliczanie (Counting Sort) i Kubełkowe (Bucket Sort)

Nieporównaniowe algorytmy sortowania

Tradycyjne algorytmy sortowania oparte na porównaniach (QuickSort, MergeSort, HeapSort) mają teoretyczną granicę złożoności rzędu Ω(n log n). Algorytmy Counting Sort i Bucket Sort omijają to ograniczenie, osiągając liniowy czas działania O(n + k) przy założeniu ograniczonego zakresu danych wejściowych.

1. Sortowanie przez zliczanie (Counting Sort):

• Zasada: Tworzy pomocniczą tablicę liczników count[] o rozmiarze równym zakresowi wartości [0, k]. Zlicza wystąpienia każdej liczby, a następnie przepisuje elementy w kolejności rosnącej.
• Złożoność: Czasowa O(n + k), Pamięciowa O(k) (gdzie k to rozpiętość liczb max - min).
• Wada: Nieefektywny, gdy zakres k jest olbrzymi w porównaniu do liczby elementów n (np. sortowanie 5 liczb o wartościach od 1 do 10⁹).

2. Sortowanie kubełkowe (Bucket Sort):

• Zasada: Dzieli przedział wartości na m równych przedziałów (kubełków), rozrzuca elementy do odpowiednich kubełków, sortuje każdy kubełek osobno (np. Insertion Sortem), a na koniec łączy zawartość kubełków w jedną listę.
• Złożoność: Średnia O(n + m), pesymistyczna O(n²) (gdy wszystkie elementy wpadną do jednego kubełka).

Pułapki na egzaminie INF.04:

• Sortowanie przez zliczanie charakteryzuje się złożonością O(n + k) i wymaga znajomości zakresu sortowanych wartości całkowitych.