Item Details

Sorting: A Distribution Theory

Hosam M. Mahmoud
Format
Book
Published
New York : John Wiley & Sons, 2000.
Language
English
Series
Wiley-Interscience Series in Discrete Mathematics and Optimization
ISBN
0471327107 (cloth : alk. paper)
Contents
  • 1 Sorting and Associated Concepts 1
  • 1.1 Sorting 1
  • 1.2 Selection 2
  • 1.3 Jargon 4
  • 1.4 Algorithmic Conventions 6
  • 1.5 Order 7
  • 1.6 Binary Trees 10
  • 1.7 Decision Trees 18
  • 1.8 Bounds on Sorting 21
  • 1.8.1 Lower Bounds on Sorting 22
  • 1.8.2 Upper Bounds on Sorting 24
  • 1.9 Bounds on Selection 25
  • 1.9.1 Lower Bounds on Selection 26
  • 1.9.2 Upper Bounds on Selection 33
  • 1.10 Random Permutations 36
  • 1.10.1 Records 41
  • 1.10.2 Inversions 44
  • 1.10.3 Cycles 46
  • 1.10.4 Runs 48
  • 1.11 An Analytic Toolkit 53
  • 1.11.1 Saddle Point Method 54
  • 1.11.2 Mellin Transform 56
  • 1.11.3 Poissonization 61
  • 1.11.4 Dirichlet Transform 67
  • 1.11.5 Rice's Method 74
  • 2 Insertion Sort 83
  • 2.1 A General Framework 84
  • 2.2 A Sufficient Condition for Normality 87
  • 2.3 Linear Insertion Sort 88
  • 2.4 Binary Insertion Sort 95
  • 3 Shell Sort 103
  • 3.1 Algorithm 103
  • 3.2 Streamlined Stochastic Analysis 105
  • 3.2.1 Empirical Distribution Function 106
  • 3.2.2 Brownian Bridge 106
  • 3.2.3 Using the Stochastic Tools 114
  • 3.3 Other Increment Sequences 122
  • 4 Bubble Sort 129
  • 4.1 Algorithm 129
  • 4.2 A limit Law for Passes 131
  • 4.3 A Limit Law for Comparisons 136
  • 5 Selection Sort 139
  • 5.1 Algorithm 139
  • 5.2 Analysis 140
  • 6 Sorting by Counting 144
  • 6.1 Count Sort 144
  • 6.2 Sorting by Counting Frequencies 146
  • 7 Quick Sort 148
  • 7.1 Partitioning Stage 148
  • 7.2 Bookkeeping 151
  • 7.3 Quick Sort Tree 152
  • 7.4 Probabilistic Analysis of Quick Sort 153
  • 7.5 Quick Selection 166
  • 7.5.1 Hoare's Find 167
  • 7.5.2 Multiple Quick Select 177
  • 8 Sample Sort 199
  • 8.1 Small Sample Algorithm 199
  • 8.2 Large Sample Algorithm 205
  • 9 Heap Sort 212
  • 9.1 Heap 212
  • 9.2 Sorting via a Heap 217
  • 10 Merge Sort 220
  • 10.1 Merging Sorted Lists 220
  • 10.1.1 Linear Merge 222
  • 10.1.2 Binary Merge 227
  • 10.1.3 Hwang-Lin Merging Algorithm 228
  • 10.2 Merge Sort Algorithm 230
  • 10.3 Distributions 239
  • 10.4 Bottom-Up Merge Sort 243
  • 11 Bucket Sorts 250
  • 11.1 Principle of Bucket Sorting 250
  • 11.1.1 Distributive Sorts 253
  • 11.1.2 Radix Sorting 259
  • 11.2 Bucket Selection 269
  • 11.2.1 Distributive Selection 271
  • 11.2.2 Radix Selection 276
  • 12 Sorting Nonrandom Data 283
  • 12.1 Measures of Presortedness 284
  • 12.2 Data Randomization 284
  • 12.3 Guaranteed Performance 286
  • 12.3.1 Ford-Johnson Algorithm 286
  • 12.3.2 Linear-Time Selection 294
  • 12.4 Presorting 298
  • Appendix Notation and Standard Results from Probability Theory 367
  • A.1 Logarithms 367
  • A.2 Asymptotics 367
  • A.3 Harmonic Numbers 368
  • A.4 Probability 368.
Description
xv, 394 p. : ill. ; 25 cm.
Notes
Includes bibliographical references (p. 373-387) and index.
Technical Details
  • Access in Virgo Classic

  • LEADER 03918cam a22003254a 4500
    001 u3707861
    003 SIRSI
    005 20001108172945.0
    008 991220s2000 nyua b 001 0 eng
    010
      
      
    a| 99086783
    020
      
      
    a| 0471327107 (cloth : alk. paper)
    035
      
      
    a| (Sirsi) i0471327107
    035
      
      
    a| (OCoLC)43185926
    040
      
      
    a| DLC c| DLC d| DLC d| MvI
    042
      
      
    a| pcc
    050
    0
    0
    a| QA273.6 b| .M285 2000
    082
    0
    0
    a| 519.2/4 2| 21
    090
      
      
    a| SCIENG/QA273.6 b| .M285 2000
    100
    1
      
    a| Mahmoud, Hosam M. q| (Hosam Mahmoud), d| 1954-
    245
    1
    0
    a| Sorting : b| a distribution theory / c| Hosam M. Mahmoud.
    260
      
      
    a| New York : b| John Wiley & Sons, c| 2000.
    300
      
      
    a| xv, 394 p. : b| ill. ; c| 25 cm.
    440
      
    0
    a| Wiley-Interscience series in discrete mathematics and optimization
    504
      
      
    a| Includes bibliographical references (p. 373-387) and index.
    505
    0
    0
    g| 1 t| Sorting and Associated Concepts g| 1 -- g| 1.1 t| Sorting g| 1 -- g| 1.2 t| Selection g| 2 -- g| 1.3 t| Jargon g| 4 -- g| 1.4 t| Algorithmic Conventions g| 6 -- g| 1.5 t| Order g| 7 -- g| 1.6 t| Binary Trees g| 10 -- g| 1.7 t| Decision Trees g| 18 -- g| 1.8 t| Bounds on Sorting g| 21 -- g| 1.8.1 t| Lower Bounds on Sorting g| 22 -- g| 1.8.2 t| Upper Bounds on Sorting g| 24 -- g| 1.9 t| Bounds on Selection g| 25 -- g| 1.9.1 t| Lower Bounds on Selection g| 26 -- g| 1.9.2 t| Upper Bounds on Selection g| 33 -- g| 1.10 t| Random Permutations g| 36 -- g| 1.10.1 t| Records g| 41 -- g| 1.10.2 t| Inversions g| 44 -- g| 1.10.3 t| Cycles g| 46 -- g| 1.10.4 t| Runs g| 48 -- g| 1.11 t| An Analytic Toolkit g| 53 -- g| 1.11.1 t| Saddle Point Method g| 54 -- g| 1.11.2 t| Mellin Transform g| 56 -- g| 1.11.3 t| Poissonization g| 61 -- g| 1.11.4 t| Dirichlet Transform g| 67 -- g| 1.11.5 t| Rice's Method g| 74 -- g| 2 t| Insertion Sort g| 83 -- g| 2.1 t| A General Framework g| 84 -- g| 2.2 t| A Sufficient Condition for Normality g| 87 -- g| 2.3 t| Linear Insertion Sort g| 88 -- g| 2.4 t| Binary Insertion Sort g| 95 -- g| 3 t| Shell Sort g| 103 -- g| 3.1 t| Algorithm g| 103 -- g| 3.2 t| Streamlined Stochastic Analysis g| 105 -- g| 3.2.1 t| Empirical Distribution Function g| 106 -- g| 3.2.2 t| Brownian Bridge g| 106 -- g| 3.2.3 t| Using the Stochastic Tools g| 114 -- g| 3.3 t| Other Increment Sequences g| 122 -- g| 4 t| Bubble Sort g| 129 -- g| 4.1 t| Algorithm g| 129 -- g| 4.2 t| A limit Law for Passes g| 131 -- g| 4.3 t| A Limit Law for Comparisons g| 136 -- g| 5 t| Selection Sort g| 139 -- g| 5.1 t| Algorithm g| 139 -- g| 5.2 t| Analysis g| 140 -- g| 6 t| Sorting by Counting g| 144 -- g| 6.1 t| Count Sort g| 144 -- g| 6.2 t| Sorting by Counting Frequencies g| 146 -- g| 7 t| Quick Sort g| 148 -- g| 7.1 t| Partitioning Stage g| 148 -- g| 7.2 t| Bookkeeping g| 151 -- g| 7.3 t| Quick Sort Tree g| 152 -- g| 7.4 t| Probabilistic Analysis of Quick Sort g| 153 -- g| 7.5 t| Quick Selection g| 166 -- g| 7.5.1 t| Hoare's Find g| 167 -- g| 7.5.2 t| Multiple Quick Select g| 177 -- g| 8 t| Sample Sort g| 199 -- g| 8.1 t| Small Sample Algorithm g| 199 -- g| 8.2 t| Large Sample Algorithm g| 205 -- g| 9 t| Heap Sort g| 212 -- g| 9.1 t| Heap g| 212 -- g| 9.2 t| Sorting via a Heap g| 217 -- g| 10 t| Merge Sort g| 220 -- g| 10.1 t| Merging Sorted Lists g| 220 -- g| 10.1.1 t| Linear Merge g| 222 -- g| 10.1.2 t| Binary Merge g| 227 -- g| 10.1.3 t| Hwang-Lin Merging Algorithm g| 228 -- g| 10.2 t| Merge Sort Algorithm g| 230 -- g| 10.3 t| Distributions g| 239 -- g| 10.4 t| Bottom-Up Merge Sort g| 243 -- g| 11 t| Bucket Sorts g| 250 -- g| 11.1 t| Principle of Bucket Sorting g| 250 -- g| 11.1.1 t| Distributive Sorts g| 253 -- g| 11.1.2 t| Radix Sorting g| 259 -- g| 11.2 t| Bucket Selection g| 269 -- g| 11.2.1 t| Distributive Selection g| 271 -- g| 11.2.2 t| Radix Selection g| 276 -- g| 12 t| Sorting Nonrandom Data g| 283 -- g| 12.1 t| Measures of Presortedness g| 284 -- g| 12.2 t| Data Randomization g| 284 -- g| 12.3 t| Guaranteed Performance g| 286 -- g| 12.3.1 t| Ford-Johnson Algorithm g| 286 -- g| 12.3.2 t| Linear-Time Selection g| 294 -- g| 12.4 t| Presorting g| 298 -- g| Appendix t| Notation and Standard Results from Probability Theory g| 367 -- g| A.1 t| Logarithms g| 367 -- g| A.2 t| Asymptotics g| 367 -- g| A.3 t| Harmonic Numbers g| 368 -- g| A.4 t| Probability g| 368.
    596
      
      
    a| 5
    650
      
    0
    a| Distribution (Probability theory)
    999
      
      
    a| QA273.6 .M285 2000 w| LC i| X004474332 l| STACKS m| SCI-ENG t| BOOK

Availability

Google Preview

Library Location Map Availability Call Number
Brown Science and Engineering Stacks N/A Available