Category Archives: řazení

Jazyk D a radix sort

V poslední době jsem se začal učit jazyk D. Chtěl jsem poznat nějaký nový jazyk, nejlépe něco kompilovaného, co mi poskytne dobrou kontrolou nad layoutem paměti. Zkoušel jsem Rust, ale nějak moc mě nechytl, vždycky mi připadalo, že učící křivka začíná … Continue reading 

Posted in D, low level, řazení | Leave a comment

Radix merge sort

Nedávno jsem psal o divoké hybridizaci řadících algoritmů, která mě dovedla k mergeselectu. Teď budu v započaté cestě pokračovat. Metoda sledování os a hledání průsečíků ukázala jedno nepokryté místo: Radixovou obdobu merge sortu. Quicksort má radixovou verzi (radixsort) a proto by mělo být … 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