Sorting using complete subintervals and the maximum number of runs in a randomly evolving sequence: Extended abstract.

Abstract : We study the space requirements of a sorting algorithm where only items that at the end will be adjacent are kept together. This is equivalent to the following combinatorial problem: Consider a string of fixed length n that starts as a string of 0's, and then evolves by changing each 0 to 1, with the n changes done in random order. What is the maximal number of runs of 1's? We give asymptotic results for the distribution and mean. It turns out that, as in many problems involving a maximum, the maximum is asymptotically normal, with fluctuations of order $n^{1/2}$, and to the first order well approximated by the number of runs at the instance when the expectation is maximized, in this case when half the elements have changed to 1; there is also a second order term of order $n^{1/3}$. We also treat some variations, including priority queues and sock-sorting.
Type de document :
Communication dans un congrès
Jacquet, Philippe. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), pp.259-270, 2007, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01184796
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 17 août 2015 - 17:00:13
Dernière modification le : jeudi 11 mai 2017 - 01:02:52
Document(s) archivé(s) le : mercredi 18 novembre 2015 - 12:18:17

Fichier

dmAH0117.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184796, version 1

Collections

Citation

Svante Janson. Sorting using complete subintervals and the maximum number of runs in a randomly evolving sequence: Extended abstract.. Jacquet, Philippe. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), pp.259-270, 2007, DMTCS Proceedings. 〈hal-01184796〉

Partager

Métriques

Consultations de la notice

46

Téléchargements de fichiers

56