Podsumowujac:
Skoro nie istnieje algorytm sortujacy za pomoca porownan o zlozonosci mniejszej niz (n lg n), to algorytmy sortowania przez kopcowanie, scalanie oraz quick-sort sa asymptotycznie optymalnymi algorytmami.
Natomiast, jesli wyjdziemy poza obszar sortowania za pomoca porownan istnieja algorytmy sortowania o mniejszej zlozonosci, chociazby juz wspomniane sortowanie przez zliczanie, ktore w uzywane w praktyce dla sortowania n elementow z przedzialu od 1 do k ma zlozonosc (k+n). Mozna wiec przyjac, ze jest to sortowanie w czasie liniowym :))) Kolejna zaleta tego algotrytmu jest jego "stabilnosc" tzn. liczby o tej samej wartosci w tablicy wynikowej wystepuja w tej samej kolejnosci co w tablicy poczadkowej, co jest istotne, gdy z sortowanymi elementami zwiazane sa dodatkowe dane.
Sredni czas sortowania kubelkowego rowniez jest liniowy, wiec tak samo jak w sortowaniu przez zliczanie otrzymujemy "szybkie" sortowanie przyjmujac pewne zalozenia o danych wejsciowych. Gdy w sortowaniu przez zliczanie zakladalismy, ze elementy sa malymi liczbami calkowitymi, to w sortowaniu kubelkowym zaklada sie, ze dane wejsciowe sa liczbami rzeczywistymi wybieranymi losowo z przedzialu [0, 1), zgodnie z rozkladem jednostajnym.
Jesli ktos doczytal do tego miejsca i bylby zainteresowany konkretnym algorytmem, to moge go zamiesc.
Pozdrawiam-- ---| p00f |---
Delphi (3, 4 ...) & Kylix r0x
---| p00f |---