Book:Donald E. Knuth/The Art of Computer Programming: Volume 3: Sorting and Searching
Jump to navigation
Jump to search
Donald E. Knuth: The Art of Computer Programming: Volume 3: Sorting and Searching
Published $\text {1973}$
Subject Matter
Contents
- Preface
- Notes on the Exercises
- Chapter 5 Sorting
- *5.1. Combinatorial Properties of Permutations
- *5.1.1. Inversions
- *5.1.2. Permutations of a Multiset
- *5.1.3. Runs
- *5.1.4. Tableaux and Involutions
- 5.2. Internal sorting
- 5.2.1. Sorting by Insertion
- 5.2.2. Sorting by Exchanging
- 5.2.3. Sorting by Selection
- 5.2.4. Sorting by Merging
- 5.2.5. Sorting by Distribution
- 5.3. Optimum Sorting
- 5.3.1. Minimum-Comparison Sorting
- *5.3.2. Minimum-Comparison Merging
- *5.3.3. Minimum-Comparison Selection
- *5.3.4. Networks for Sorting
- 5.4. External Sorting
- 5.4.1. Multiway Merging and Replacement Selection
- *5.4.2. The Polyphase Merge
- *5.4.3. The Cascade Merge
- *5.4.4. Reading Tape Backwards
- *5.4.5. The Oscillating Sort
- *5.4.6. Practical Considerations for Tape Merging
- *5.4.7. External Radix Sorting
- *5.4.8. Two-Tape Sorting
- *5.4.9. Disks and Drums
- 5.5. Summary, History, and Bibliography
- *5.1. Combinatorial Properties of Permutations
- Chapter 6 - Searching
- 6.1. Sequential Searching
- 6.2. Searching by Comparison of Keys
- 6.2.1. Searching an Ordered Table
- 6.2.2. Binary Tree Searching
- 6.2.3. Balanced Trees
- 6.2.4. Multiway Trees
- 6.3. Digital Searching
- 6.4. Hashing
- 6.5. Retrieval on Secondary Keys
- Answers to Exercises
- Appendix A - Tables of Numerical Quantities
- 1. Fundamental Constants (decimal)
- 2. Fundamental Constants (octal)
- 3. Harmonic Numbers, Bernoulli Numbers, Fibonacci Numbers
- Appendix B - Index to Notations
- Index and Glossary