Generating nearly sorted sequences: the use of measures of disorder

Estivill-Castro, V. (Vladimir)

doi:http://dx.doi.org/10.1016/j.entcs.2003.12.006

Generating nearly sorted sequences: the use of measures of disorder

License

Citation

Estivill-Castro V. Generating nearly sorted sequences: the use of measures of disorder. Electron Notes Theor Comput Sci. 2004 Feb 16;91:56-95. DOI: 10.1016/j.entcs.2003.12.006

Abstract

There have been several formal proposals for a function that evaluates disorder in a sequence. We show here that definitions that allow equivalence to an operational formulation allow for the construction of an algorithm for pseudo-random generation of nearly sorted sequences. As there is interest in comparing performance of algorithms on nearly sorted sequences during experimental evaluations of their implementation, our methods here provide the pathway for establishing the benchmarks datasets to compare such algorithms.