Seminar MARA

☰ Meni

V ponedeljek, 17. marca 2014, bo ob 16.00 uri v prostorih Fakultete za matematiko, naravoslovje in informacijske tehnologije Univerze na Primorskem, Glagoljaška 8, Koper predavanje v okviru skupnega SEMINARJA ZA MATEMATIČNE IN RAČUNALNIŠKE ZNANOSTI Oddelka za matematiko in Oddelka za Informacijske znanosti in tehnologije UP FAMNIT, Oddelka za matematiko in Oddelka za Informacijske znanosti in tehnologije UP IAM, Oddelka za matematiko in računalništvo UP PEF ter Oddelkov za matematiko in teoretično računalništvo IMFM.

RAČUNALNIŠKI SEMINAR

Prostor: FAMNIT-1-RU1 ob 16:00

Predavatelj: Prof. Alejandro (Alex) Lopez-Ortiz, University of Waterloo, Canada

Naslov: Multi-Pivot Quicksort: Theory and Experiments

Povzetek:

Recently Vladimir Yaroslavskiy proposed a dual pivot quicksort algorithm that, contrary to prior theory and intuition, outperforms standard quicksort by a a significant margin under the Java JVM. More
recently, this algorithm has been analyzed in terms of comparisons and swaps by Wild and Nebel but failed to resolve the disagreement between theory and practice. We provide strong theoretical and practical evidence that cache behavior is causing most of the performance differences in these algorithms.

Lastly, we propose 3-pivot variant showing a 7-8% performance improvement over the previously best known quicksort algorithms.

Vabljeni!