A generating functions approach for the analysis of grand averages for multiple QUICKSELECT

✍ Scribed by Alois Panholzer; Helmut Prodinger

• Publisher: John Wiley and Sons
• Year: 1998
• Tongue: English
• Weight: 230 KB
• Volume: 13
• Category: Article
• ISSN: 1042-9832
• DOI: 10.1002/(sici)1098-2418(199810/12)13:3/4<189::aid-rsa1>3.0.co;2-r

✦ Synopsis

Hoare's FIND algorithm can be used to select p specified order statistics n Ž . Ä 4 j , . . . , j from a file of n elements simultaneously. Averaging over all subsets of 1, . . . , n p 1 p defines the grand a¨erages of the number of passes and comparisons. We use a generating functions approach to compute averages and variances of these parameters. Additionally, we sketch analogous developments for the instance of median-of-three partition and binary Ž .