Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching (3rd Edition)

"This is an eminently readable book which an ordinary programmer, unskilled in mathematical analysis and wary of theoretical algorithms, ought to be able to pick up and get a lot out of.." - Steve Summit, author of C Programming FAQs Sedgewick has a real gift for explaining concepts in a way that makes them easy to understand. The use of real programs in page-size (or less) chunks that can be easily understood is a real plus. The figures, programs, and tables are a significant contribution to the learning experience of the reader; they make this book distinctive. - William A. Ward, University of South Alabama Robert Sedgewick has thoroughly rewritten and substantially expanded his popular work to provide current and comprehensive coverage of important algorithms and data structures. Many new algorithms are presented, and the explanations of each algorithm are much more detailed than in previous editions. A new text design and detailed, innovative figures, with accompanying commentary, greatly enhance the presentation. The third edition retains the successful blend of theory and practice that has made Sedgewick's work an invaluable resource for more than 250,000 programmers! This particular book, Parts 1-4, represents the essential first half of Sedgewick's complete work. It provides extensive coverage of fundamental data structures and algorithms for sorting, searching, and related applications. The algorithms and data structures are expressed in concise implementations in C, so that you can both appreciate their fundamental properties and test them on real applications. Of course, the substance of the book applies to programming in any language. Highlights Expanded coverage of arrays, linked lists, strings, trees, and other basic data structures Greater emphasis on abstract data types (ADTs) than in previous editions Over 100 algorithms for sorting, selection, priority queue ADT implementations, and symbol table ADT (searching) implementations New implementations of binomial queues, multiway radix sorting, Batcher's sorting networks, randomized BSTs, splay trees, skip lists, multiway tries, and much more Increased quantitative information about the algorithms, including extensive empirical studies and basic analytic studies, giving you a basis for comparing them Over 1000 new exercises to help you learn the properties of algorithms Whether you are a student learning the algorithms for the first time or a professional interested in having up-to-date reference material, you will find a wealth of useful information in this book. Sedgewick's bestselling book, Algorithms, is now available for C programmers. Algorithms in C describes a variety of algorithms in a number of areas of interest, including: sorting, searching, string-processing, and geometric, graph and mathematical algorithms. The book emphasizes fundamental techniques, providing readers with the tools to confidently implement, run, and debug useful algorithms. Contents 14 Fundamentals 20 Chapter 1. Introduction 22 1.1 Algorithms 23 1.2 A Sample Problem—Connectivity 25 1.3 Union-Find Algorithms 30 1.4 Perspective 41 1.5 Summary of Topics 42 Chapter 2. Principles of Algorithm Analysis 46 2.1 Implementation and Empirical Analysis 47 2.2 Analysis of Algorithms 52 2.3 Growth of Functions 55 2.4 Big-Oh notation 63 2.5 Basic Recurrences 68 2.6 Examples of Algorithm Analysis 72 2.7 Guarantees, Predictions, and Limitations 78 Data Structures 86 Chapter 3. Elementary Data Structures 88 3.1 Building Blocks 89 3.2 Arrays 101 3.3 Linked Lists 109 3.4 Elementary List Processing 115 3.5 Memory Allocation for Lists 124 3.6 Strings 128 3.7 Compound Data Structures 134 Chapter 4. Abstract Data Types 146 4.1 Abstract Objects and Collections of Objects 150 4.2 Pushdown Stack ADT 154 4.3 Examples of Stack ADT Clients 157 4.4 Stack ADT Implementations 163 4.5 Creation of a New ADT 168 4.6 FIFO Queues and Generalized Queues 172 4.7 Duplicate and Index Items 180 4.8 First-Class ADTs 184 4.9 Application-Based ADT Example 197 4.10 Perspective 203 Chapter 5. Recursion and Trees 206 5.1 Recursive Algorithms 207 5.2 Divide and Conquer 215 5.3 Dynamic Programming 227 5.4 Trees 235 5.5 Mathematical Properties of Trees 245 5.6 Tree Traversal 249 5.7 Recursive Binary-Tree Algorithms 254 5.8 Graph Traversal 260 5.9 Perspective 266 Sorting 270 Chapter 6. Elementary Sorting Methods 272 6.1 Rules of the Game 274 6.2 Selection Sort 280 6.3 Insertion Sort 281 6.4 Bubble Sort 284 6.5 Performance Characteristics of Elementary Sorts 286 6.6 Shellsort 292 6.7 Sorting Other Types of Data 300 6.8 Index and Pointer Sorting 306 6.9 Sorting of Linked Lists 313 6.10 Key-Indexed Counting 317 Chapter 7. Quicksort 322 7.1 The Basic Algorithm 323 7.2 Performance Characteristics of Quicksort 328 7.3 Stack Size 332 7.4 Small Sub.les 335 7.5 Median-of-Three Partitioning 338 7.6 Duplicate Keys 343 7.7 Strings and Vectors 346 7.8 Selection 348 Chapter 8. Merging and Mergesort 354 8.1 Two-Way Merging 355 8.2 Abstract In-place Merge 358 8.3 Top-Down Mergesort 360 8.4 Improvements to the Basic Algorithm 363 8.5 Bottom-Up Mergesort 366 8.6 Performance Characteristics of Mergesort 370 8.7 Linked-List Implementations of Mergesort 373 8.8 Recursion Revisited 376 Chapter 9. Priority Queues and Heapsort 380 9.1 Elementary Implementations 384 9.2 Heap Data Structure 387 9.3 Algorithms on Heaps 390 9.4 Heapsort 395 9.5 Priority-Queue ADT 402 9.6 Priority Queues for Index Items 408 9.7 Binomial Queues 411 Chapter 10. Radix Sorting 422 10.1 Bits, Bytes, and Words 424 10.2 Binary Quicksort 428 10.3 MSD Radix Sort 432 10.4 Three-Way Radix Quicksort 440 10.5 LSD Radix Sort 444 10.6 Performance Characteristics of Radix Sorts 447 10.7 Sublinear-Time Sorts 452 Chapter 11. Special-Purpose Sorts 458 11.1 Batcher’s Odd-Even Mergesort 460 11.2 Sorting Networks 465 11.3 External Sorting 473 11.4 Sort-Merge Implementations 479 11.5 Parallel Sort/Merge 485 Searching 494 Chapter 12. Symbol Tables and BSTs 496 12.1 Symbol-Table Abstract Data Type 498 12.2 Key-Indexed Search 504 12.3 Sequential Search 508 12.4 Binary Search 516 12.5 Binary Search Trees (BSTs) 521 12.6 Performance Characteristics of BSTs 527 12.7 Index Implementations with Symbol Tables 530 12.8 Insertion at the Root in BSTs 535 12.9 BST Implementations of Other ADT Functions 538 Chapter 13. Balanced Trees 548 13.1 Randomized BSTs 552 13.2 Splay BSTs 559 13.3 Top-Down 2-3-4 Trees 565 13.4 Red-Black Trees 570 13.5 Skip Lists 580 13.6 Performance Characteristics 588 Chapter 14. Hashing 592 14.1 Hash Functions 593 14.2 Separate Chaining 602 14.3 Linear Probing 607 14.4 Double Hashing 613 14.5 Dynamic Hash Tables 618 14.6 Perspective 622 Chapter 15. Radix Search 628 15.1 Digital Search Trees 629 15.2 Tries 633 15.3 Patricia Tries 642 15.4 Multiway Tries and TSTs 651 15.5 Text String Index Algorithms 667 Chapter 16. External Searching 674 16.1 Rules of the Game 676 16.2 Indexed Sequential Access 679 16.3 B Trees 681 16.4 Extendible Hashing 695 16.5 Perspective 707 Index 712 A 712 B 712 C 713 D 713 E 714 F 714 G 715 H 715 I 715 J 716 K 716 L 716 M 717 N 717 O 717 P 717 Q 718 R 718 S 719 T 720 U 721 V 721 W 721 Y 721 Z 721 Defines and explores the implementation and figures of the algorithms required for various applications, offering commentary, descriptions, and exercises for developers, researchers, and students. THE OBJECTIVE OF this book is to study a broad variety of important and useful algorithms: methods for solving problems that are suited for computer implementation.