Generating nearly sorted sequences: the use of measures of disorder

Descripció

• Resum

  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.
  Llegir més + Llegir menys -

• DOI

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

• Col·leccions

  Articles (Departament de Tecnologies de la Informació i les Comunicacions)
Mostra el registre complet