2020-03-16
Aby osiągnąć sortowanie o złożoności należy dodać dodatkowe założenia na dane wejściowe (wyjść poza comparison model), takie jak sortujemy liczby naturalne z danego przedziału.
CountingSort
CountingSort
ma złożoność Własność stabilności sortowania:
algorytm sortowania musi zachowywać porządek równych sobie elementów.
CountingSort
ma własność stabilności sortowania.
RadixSort
Użycie np. CountingSort
a aby sortować w złożoności linowej z przedziału wielkości , gdzie jest stałe.
Złożoność RadixSort
a to