| Adaptive heapsort: Source code | |
| Authors: | Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen |
| Publication: | CPH STL Report 2011-1, Department of Computer Science, University of Copenhagen (2011--2015), 28 pp. |
| Full text: |  PDF (360 kB)  PS (904 kB) |
| Abstract: | A priority queue is a great tool for solving different kinds of sorting problems. However, a general-purpose priority queue is often an overkill for these applications since the number of elements processed is known beforehand and the operation repertoire to be supported just includes two operations: insert and extract-min. This report is an electronic appendix to our paper "Two constant-factor-optimal realizations of adaptive heapsort", where we show how two priority queues—a weak heap and a weak queue—can be specialized and used in adaptive sorting. At the time of writing, the programs developed provide the best performance of all implementations of known adaptive sorting algorithms with respect to the number of element comparisons performed, but due to a poor cache behaviour the programs are not always the fastest when sorting elements for which element moves and element comparisons are cheap. This report together with an accompanying tar file gives the source code used in the experiments reported in the paper. Our main conclusion is that the gap between the theory of adaptive sorting and the actual computing practice is still big. By making the source code available, we hope that other researchers can use our code in their experiments and this way confirm that their work actually reduces the gap. |
| Related: |  HTML (Conference paper) HTML (Journal article) HTML (tar ball) |
| BibLATEX: | @report{EEK2011bS,
author = {Stefan Edelkamp and Amr Elmasry and Jyrki Katajainen},
title = {Adaptive heapsort: {S}ource code},
type = {CPH STL Report},
number = {2011-1},
institution = {Department of Computer Science, University of Copenhagen},
year = {2011--2015},
pagetotal = {28},
}
|