Sorting : a distribution theory / / Hosam M. Mahmoud

• Autore: Mahmoud Hosam M (Hosam Mahmoud), <1954->
• Pubblicazione: New York, : John Wiley & Sons, 2000
• Descrizione fisica: 1 online resource (414 p.)
• Disciplina: 519.2/4
• Soggetto topico: Distribution (Probability theory); Probabilities
• Note generali: Description based upon print version of record.
• Nota di bibliografia: Includes bibliographical references (p. 373-387) and index.
• Nota di contenuto: Sorting: 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 ; 1.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 ; 6.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 ; 11.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
• Sommario/riassunto: A 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
• Titolo autorizzato: Sorting
• ISBN: 9786613306227; 9781283306225; 1283306220; 9781118032886; 1118032888; 9781118031131; 111803113X
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9911019966803321
• Lo trovi qui: Univ. Federico II
• Serie: Wiley-Interscience series in discrete mathematics and optimization.