Category Archives: řazení

Radix merge sort

Nedávno jsem tu psal o divoké hybridizaci řadících algoritmů, která mě dovedla k mergeselectu. Teď bych chtěl v této cestě pokračovat. Metodou sledování os a hledání průsečíků jsem našel jedno nepokryté místo: Radixovou obdobu merge sortu. Quicksort má radixovou verzi (radixsort) a proto … Continue reading 

Posted in Algo, řazení | Leave a comment

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