SH_PANDA: dnes mam spatny den, pardon za pokazeni vtipu.

SULTHAN: "Randomized" a "skoro setříděný" se nutně nevylučuje ale. V podstatě je problém v tom, že Ježíš tu vlastnost demonstruje s existenčním kvantifikátorem, ale aby to bylo zajímavé, musel by jí demonstrovat s univerzálním kvantifikátorem. Taky bys mohl použít i obyčejný BOGO SORT (netřeba kvantum) abys teoreticky mohl v některých případech seřadit v konstantním čase.

KAMAHL: No, akorát v těch svých úvahách předpokládáš, že dostaneš už setříděný (skoro setříděný, nebo jinak předpřipravený) seznam. Je tam jasně zmíněno, že jde o "randomized list", a tam s tím spodním odhadem založeným na minimálním počtu porovnání prostě moc neuděláš.

MAIMONIDES: Pravda, tak tam už bych považoval za zázrak obecné reálné číslo v konečném čase už jen nasamplovat :D

Když už to pitvám, tak v tom vtipu je v podstatě nesmysl v tom, že seřazení v O(n) čase se prezentuje jako zázrak a naráží se na to, že za běžných okolností to lze nejmíň v O(n*log(n)). Jenže O(f(n)) je horní asymptotický odhad a pro nějaký konkrétní vstup není překvapivé, když dostane výrazně menší. Spodní asymptotický odhad řadících algoritmů můžeme srazit až na Ω(1). A Ω(n) nám z běžných algoritmů může dát třeba insertion sort, nemusím ani "cheatovat" radix sortem.Takže Ježíš v tom vtipu nemá pravdu, že popřel logiku.

FJERTIL: Spaghetti sort! A IMHO i sleep sort!

FJERTIL: ACKCHYUALLY.JPG Za určitých podmínek, které v uvedeném případě lze považovat za myslitelné, se dá řadit s přimhouřeným očíčkem v lineárním čase například pomocí radix sortu. Věta, kterou se komix asi snaží "popřít" říká, že to nejde rychleji než n*log(n) pro algoritmy založené na porovnávání hodnot. Ale jsou i řadící algoritmy založené na jiných myšlenkách.