Analytic Variations on Bucket Selection and Sorting

Hosam Mahmoud Philippe Flajolet 1 Philippe Jacquet 2 Mireille Regnier 1
1 ALGO - Algorithms
Inria Paris-Rocquencourt
2 HIPERCOM - High performance communication
Inria Paris-Rocquencourt, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : We provide complete average-case as well as probabilistic analysis of the cost of bucket selection and sorting algorithms. Two variations of bucketing (and flavors there in) are considered: distributive bucketing (large number of buckets) and radix bucketing (recursive with a small number of buckets, suitable for digital computation). For Distributive Selection a compound Poisson limit is established. For all other flavors of bucket selection and sorting, central limit theorems underlying the cost are derived by asymptotic techniques involving perturbation of Rice's integral and contour integration (saddle point methods). In the case of radix bucketing, periodic luctuations appear in the moments of both the selection and sorting algorithms.
Type de document :
Rapport
[Research Report] RR-3399, INRIA. 1998
Liste complète des métadonnées

https://hal.inria.fr/inria-00073290
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 12:26:50
Dernière modification le : vendredi 25 mai 2018 - 12:02:06
Document(s) archivé(s) le : jeudi 24 mars 2011 - 12:36:18

Fichiers

Identifiants

  • HAL Id : inria-00073290, version 1

Collections

Citation

Hosam Mahmoud, Philippe Flajolet, Philippe Jacquet, Mireille Regnier. Analytic Variations on Bucket Selection and Sorting. [Research Report] RR-3399, INRIA. 1998. 〈inria-00073290〉

Partager

Métriques

Consultations de la notice

282

Téléchargements de fichiers

148