The art of computer programming.

Volume 3 Sorting and searching

Donald E. Knuth

Dnes vráceno


Copies Bound volumes
Loading copies
Document is currently in processing No copies Document has no bound volumes
Citation
Related
All parts
Contents
CONTENTS Chapter 5 — Sorting ........................................................ 1 *5.1. Combinatorial Properties of Permutations............................. 11 *5.1.1. Inversions.................................................... 11 *5.1.2. Permutations of a Multiset ................................... 22 *5.1.3. Runs.......................................................... 35 *5.1.4. Tableaux and Involutions...................................... 47 5.2. Internal sorting ..................................................... 73 5.2.1. Sorting by Insertion.......................................... 80 5.2.2. Sorting by Exchanging........................................ 105 5.2.3. Sorting by Selection......................................... 138 5.2.4. Sorting by Merging........................................... 158 5.2.5. Sorting by Distribution...................................... 168 5.3. Optimum Sorting............_...................................... 180 5.3.1. Minimum-Comparison Sorting................................... 180 *5.3.2. Minimum-Comparison Merging................................... 197 *5.3.3. Minimum-Comparison Selection................................. 207 *5.3.4. Networks for Sorting......................................... 219 5.4. External Sorting..................................................... 248 5.4.1. Multiway Merging and Replacement Selection................... 252 *5.4.2. The Polyphase Merge.......................................... 267 *5.4.3. The Cascade Merge............................................ 288 *5.4.4. Reading Tape Backwards....................................... 299 *5.4.5. The Oscillating Sort ........................................ 311 *5.4.6. Practical Considerations for Tape Merging.................... 317 *5.4.7. External Radix Sorting....................................... 343 *5.4.8. Two-Tape Sorting ............................................ 348 *5.4.9. Disks and Drums.............................................. 356 5.5. Summary, History, and Bibliography................................... 380 Chapter 6 — Searching..................................................... 392 6.1. Sequential Searching................................................. 396 6.2. Searching by Comparison of Keys .................................. 409 6.2.1. Searching an Ordered Table................................... 409 6.2.2. Binary Tree Searching........................................ 426 6.2.3. Balanced Trees............................................... 458 6.2.4. Multiway Trees............................................... 481 6.3. Digital Searching.................................................... 492 6.4. Hashing.............................................................. 513 6.5. Retrieval on Secondary Keys.......................................... 559 Answers to Exercises...................................................... 584 Appendix A — Tables of Numerical Quantities............................. 748 1. Fundamental Constants (decimal) ............................. 748 2. Fundamental Constants (octal)................................ 749 3. Harmonic Numbers, Bernoulli Numbers, Fibonacci Numbers . . . 750 Appendix ? — Index to Notations........................................... 752 Index and Glossary........................................................ 757
Record Details
MARC
Field Ind Field content
leader -----nam-a22------a-4500
1 kpw015826
3 CZ-OsVSB
5 20210822155447.6
7 ta
8 020117s1998----xxu----------u0|0 --eng--
20 ## $a 0-201-89685-0 (sv. 3 : váz.)
20 ## $a 978-0-201-89685-5 (sv. 3 : dotisk : váz.)
20 ## $a 0-321-75104-3 (soubor : váz.)
20 ## $a 978-0-321-75104-1 (soubor : dotisk : váz.)
40 ## $a OSD002 $b cze
41 0# $a eng
44 ## $a xxu
72 #7 $a 004.4/.6 $2 Konspekt
72 #7 $a 37.016 $2 Konspekt
80 ## $a 004 $2 MRF
80 ## $a 004.4 $2 MRF
100 1# $a Knuth, Donald Ervin, $d 1938- $7 skuk0003460
245 14 $a The art of computer programming. $n Volume 3, $p Sorting and searching / $c Donald E. Knuth
250 ## $a 2nd ed.
260 ## $a Boston : $b Addison-Wesley, $c c1998
300 ## $a xiii, 782 s., [1] složený list obr. příl. : $b il.
500 ## $a "The classic work, newly updated and revised"--Obálka
500 ## $a Obsahuje bibliografické odkazy a rejstříky
650 #4 $a Algoritmy (programování)
650 #4 $a počítačová věda
650 #4 $a programování
910 ## $a OSD002 $b 254760
1090 $a 2002/01/17 $b 2013/12/12 $c OSD 002/VOD25 $d OSD 002/VOL05
1260 $a Addison-Wesley
Loan history
{{$parent.item.lendDate | jpDate:'d.M.yyyy'}}
{{$parent.item.endDate | jpDate:'d.M.yyyy'}}
{{$parent.item.state | loc}} by user {{$parent.item.user | loc}}
Item {{$parent.item.exemplar | loc}}
Dept {{$parent.item.department | loc}}
Processing history
Permanent link