Category Archives: řazení

Vstříc řazení v lineárním čase

Obecné řazení v lineárním čase je meta, které není možné dosáhnout1. Ve výsledné složitosti se vždycky vyskytne log(n) faktor. Může být maskovaný za něco jiného, ale vždycky tam bude. Třeba takový LSD radix sort má složitost O(kn), kde k je právě … Continue reading 

Posted in Algo, řazení | 2 Comments

Mergeselect

Quickselect všichni známe a milujeme – jde o algoritmus pro nalezení k-tého nejmenšího prvku neseřazeného pole v průměrném čase O(n). Jediný jeho nedostatek je, že v patologických případech může běžet v čase O(n2). Quicksort to má ale stejně a je to součást dohody, kterou jsme … Continue reading 

Posted in Algo, řazení | 5 Comments

Jak rychle řadit a šetřit čas

Když už tu mluvím o řazení a řadící mašinerii, tak bych taky mohl stručně a srozumitelně shrnout co, jak a proč dělat a čemu se vyhnout. Asi takhle: Obecné řadící algoritmy jako quicksort, mergesort nebo heapsort jsou super. Sami o sobě nejsou … Continue reading 

Posted in Algo, CPU, Paměť, řazení | 1 Comment

How to sort out your life in O(n) time

slides

Posted in řazení | Leave a comment

Jak řadit v lineárním čase, křísit mrtvé a dosáhnout osvícení

Když se řekne řazení, většina lidí, kteří napsali víc než jednu smyčku a dva ify se zeptá: „A je to nutné?“ Řazení nemá pověst nejrychlejší operace pod sluncem a je preferováno, když se tomu dá vyhnout např. hashováním. Někdy je to … Continue reading 

Posted in Algo, CPU, Paměť, řazení | 3 Comments