Thumbnail
Access Restriction
Subscribed

Author Hurwitz, H.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Statistical analysis ♦ Binary trees ♦ Sorting
Abstract An integral equation is derived for the generating function for binary tree values, the values reflecting sorting effort. The analysis does not assume uniformly distributed branching ratios, and therefore is applicable to a family of sorting algorithms discussed by Hoare, Singleton, and van Emden. The solution to the integral equation indicates that using more advanced algorithms in the family makes only minor reductions in the expected sorting efforts, but substantially reduces the variance in sorting effort.Statistical tests of the values of several thousand trees containing up to 10,000 points have given first, second, and third moments of the value distribution function in satisfactory agreement with the moments computed from the generating function. The empirical tests, as well as the analytical results, are in agreement with previously pubished results for the first moment in the cases of uniform and nonuniform distribution of branching ratio, and for the second moment in the case of uniform distribution of branching ratio.
Description Affiliation: General Electric, Schenectady, NY (Hurwitz, H.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 14
Issue Number 2
Page Count 4
Starting Page 99
Ending Page 102


Open content in new tab

   Open content in new tab
Source: ACM Digital Library