On tree-growing search strategies
Lent, Janice ; Mahmoud, Hosam M.
Ann. Appl. Probab., Tome 6 (1996) no. 1, p. 1284-1302 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
Using the concept of a "tree-growing" search strategy, we prove that for most practical insertion sorting algorithms, the number of comparisons needed to sort n keys has asymptotically normal behavior. We prove and apply a sufficient condition for asymptotically normal behavior. The condition specifies a relationship between the variance of the number of comparisons and the rate of growth in height of the sequence of trees that the search strategy "grows."
Publié le : 1996-11-14
Classification:  Searching,  sorting,  limit distributions,  60F05,  68P10,  05C05 
@article{1035463333,
     author = {Lent, Janice and Mahmoud, Hosam M.},
     title = {On tree-growing search strategies},
     journal = {Ann. Appl. Probab.},
     volume = {6},
     number = {1},
     year = {1996},
     pages = { 1284-1302},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1035463333}
}

Lent, Janice; Mahmoud, Hosam M. On tree-growing search strategies. Ann. Appl. Probab., Tome 6 (1996) no. 1, pp.  1284-1302. http://gdmltest.u-ga.fr/item/1035463333/