Analytic Variations on Bucket Selection and Sorting - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1998

Analytic Variations on Bucket Selection and Sorting

Hosam Mahmoud
  • Fonction : Auteur
Philippe Flajolet
  • Fonction : Auteur
  • PersonId : 829512
Philippe Jacquet
Mireille Regnier
  • Fonction : Auteur
  • PersonId : 833582

Résumé

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-3399.pdf (391.82 Ko) Télécharger le fichier

Dates et versions

inria-00073290 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00073290 , version 1

Citer

Hosam Mahmoud, Philippe Flajolet, Philippe Jacquet, Mireille Regnier. Analytic Variations on Bucket Selection and Sorting. [Research Report] RR-3399, INRIA. 1998. ⟨inria-00073290⟩
163 Consultations
180 Téléchargements

Partager

Gmail Facebook X LinkedIn More