LEADER 04687nam 2200613Ia 450 001 9910139583003321 005 20170809161007.0 010 $a1-283-30622-0 010 $a9786613306227 010 $a1-118-03288-8 010 $a1-118-03113-X 035 $a(CKB)2550000000055761 035 $a(EBL)699717 035 $a(OCoLC)778616741 035 $a(SSID)ssj0000613411 035 $a(PQKBManifestationID)11408149 035 $a(PQKBTitleCode)TC0000613411 035 $a(PQKBWorkID)10586920 035 $a(PQKB)10671925 035 $a(MiAaPQ)EBC699717 035 $a(PPN)250339161 035 $a(EXLCZ)992550000000055761 100 $a19991220d2000 uy 0 101 0 $aeng 135 $aur|n|---||||| 181 $ctxt 182 $cc 183 $acr 200 10$aSorting$b[electronic resource] $ea distribution theory /$fHosam M. Mahmoud 210 $aNew York $cJohn Wiley & Sons$d2000 215 $a1 online resource (414 p.) 225 1 $aWiley-Interscience series in discrete mathematics and optimization 300 $aDescription based upon print version of record. 311 $a0-471-32710-7 320 $aIncludes bibliographical references (p. 373-387) and index. 327 $aSorting: A Distribution Theory; Contents; Preface; Acknowledgments; 1 Sorting and Associated Concepts; 1.1 Sorting; 1.2 Selection; 1.3 Jargon; 1.4 Algorithmic Conventions; 1.5 Order; 1.6 Binary Trees; 1.7 Decision Trees; 1.8 Bounds on Sorting; 1.8.1 Lower Bounds on Sorting; 1.8.2 Upper Bounds on Sorting; 1.9 Bounds on Selection; 1.9.1 Lower Bounds on Selection; 1.9.2 Upper Bounds on Selection; 1.10 Random Permutations; 1.10.1 Records; 1.10.2 Inversions; 1.10.3 Cycles; 1.10.4 Runs; 1.11 An Analytic Toolkit; 1.11.1 The Saddle Point Method; 1.11.2 The Mellin Transform; 1.11.3 Poissonization 327 $a1.11.4 The Dirichlet Transform1.11.5 Rice's Method; 2 Insertion Sort; 2.1 A General Framework; 2.2 A Sufficient Condition for Normality; 2.3 Linear Insertion Sort; 2.4 Binary Insertion Sort; 3 Shell Sort; 3.1 The Algorithm; 3.2 Streamlined Stochastic Analysis; 3.2.1 The Empirical Distribution Function; 3.2.2 The Brownian Bridge; 3.2.3 Using the Stochastic Tools; 3.3 Other Increment Sequences; 4 Bubble Sort; 4.1 The Algorithm; 4.2 A limit Law for Passes; 4.3 A Limit Law for Comparisons; 5 Selection Sort; 5.1 The Algorithm; 5.2 Analysis; 6 Sorting by Counting; 6.1 COUNT SORT 327 $a6.2 Sorting by Counting Frequencies7 Quick Sort; 7.1 The Partitioning Stage; 7.2 Bookkeeping; 7.3 Quick Sort Tree; 7.4 Probabilistic Analysis of QUICK SORT; 7.5 Quick Selection; 7.5.1 Hoare's FIND; 7.5.2 MULTIPLE QUICK SELECT; 8 Sample Sort; 8.1 The Small Sample Algorithm; 8.2 The Large Sample Algorithm; 9 Heap Sort; 9.1 The Heap; 9.2 Sorting via a Heap; 10 Merge Sort; 10.1 Merging Sorted Lists; 10.1.1 LINEAR MERGE; 10.1.2 BINARY MERGE; 10.1.3 The HWANG-LIN Merging Algorithm; 10.2 The Merge Sort Algorithm; 10.3 Distributions; 10.4 Bottom-Up Merge Sort; 11 Bucket Sorts 327 $a11.1 The Principle of Bucket Sorting11.1.1 Distributive Sorts; 11.1.2 Radix Sorting; 11.2 Bucket Selection; 11.2.1 Distributive Selection; 11.2.2 Radix Selection; 12 Sorting Nonrandom Data; 12.1 Measures of Presortedness; 12.2 Data Randomization; 12.3 Guaranteed Performance; 12.3.1 The FORD-JOHNSON Algorithm; 12.3.2 Linear-Time Selection; 12.4 Presorting; 13 Epilogue; Answers to Exercises; Appendix: Notation and Standard Results from Probability Theory; A.1 Logarithms; A.2 Asymptotics; A.3 Harmonic Numbers; A.4 Probability; Bibliography; Index 330 $aA cutting-edge look at the emerging distributional theory of sortingResearch on distributions associated with sorting algorithms has grown dramatically over the last few decades, spawning many exact and limiting distributions of complexity measures for many sorting algorithms. Yet much of this information has been scattered in disparate and highly specialized sources throughout the literature. In Sorting: A Distribution Theory, leading authority Hosam Mahmoud compiles, consolidates, and clarifies the large volume of available research, providing a much-needed, comprehensive treatment o 410 0$aWiley-Interscience series in discrete mathematics and optimization. 606 $aDistribution (Probability theory) 606 $aProbabilities 615 0$aDistribution (Probability theory) 615 0$aProbabilities. 676 $a519.24 700 $aMahmoud$b Hosam M$g(Hosam Mahmoud),$f1954-$0280986 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910139583003321 996 $aSorting$9671608 997 $aUNINA