The Art of Computer Programming: Volume 3: Sorting and Searching

Art of Computer Programming

by Donald Ervin Knuth

The bible of all fundamental algorithms and the work that taught many of today's software developers most of what they know about computer programming. – Byte , September 1995 I can't begin to tell you how many pleasurable hours of study and recreation they have afforded me! I have pored over them in cars, restaurants, at work, at home... and even at a Little League game when my son wasn't in the line-up. –Charles Long If you think you're a really good programmer... read [Knuth's] Art of Computer Programming... You should definitely send me a resume if you can read the whole thing. –Bill Gates It's always a pleasure when a problem is hard enough that you have to get the Knuths off the shelf. I find that merely opening one has a very useful terrorizing effect on computers. –Jonathan Laventhol The first revision of this third volume is the most comprehensive survey of classical computer techniques for sorting and searching. It extends the treatment of data structures in Volume 1 to consider both large and small databases and internal and external memories. The book contains a selection of carefully checked computer methods, with a quantitative analysis of their efficiency. Outstanding features of the second edition include a revised section on optimum sorting and new discussions of the theory of permutations and of universal hashing.
Ebook (PDF version) produced by Mathematical Sciences Publishers (MSP),

Genres: Programming, Computer Science, Reference, Algorithms, Technical, Nonfiction, Computers

800 pages, Hardcover

First published January 1, 1973

About the author

Donald Ervin Knuth, born January 10th 1938, is a renowned computer scientist and Professor Emeritus of the Art of Computer Programming at Stanford University.

Author of the seminal multi-volume work The Art of Computer Programming ("TAOCP"), Knuth has been called the "father" of the analysis of algorithms, contributing to the development of, and systematizing formal mathematical techniques for, the rigorous analysis of the computational complexity of algorithms, and in the process popularizing asymptotic notation.

In addition to fundamental contributions in several branches of theoretical computer science, Knuth is the creator of the TeX computer typesetting system, the related METAFONT font definition language and rendering system, and the Computer Modern family of typefaces.

A prolific writer and scholar, Knuth created the WEB/CWEB computer programming systems designed to encourage and facilitate literate programming, and designed the MMIX instruction set architecture.

Reviews

[Roger · Rating 5 out of 5]

I felt smart having it on myshelf. I felt dumb trying to fathom it

[Josh Berry · Rating 5 out of 5]

There are definitely sections of the book that are hard to appreciate. In that I probably did not. The majority of it is approachable and really gives an appreciation for the decisions that go into how to organize data. The section on retrieval by secondary key was a real delight.

The feeling at each section of "that data structure is awesome" followed by a more apt one is impressive. Especially for how often it happens. Even seeing I was coming to the end of the book, I got used to the surprise of yet another way to do things.

I do hope he gets the next version out with some of the items on Persistent Data Structures out. I am not completely sold that those are necessary for most applications, but I suspect I'll be proven wrong. :)

[Bernie4444 · Rating 5 out of 5]

Just try sorting and searching without this book.

I just bought the book I needed out of the set. I needed to build a database that did not use any commercial package (this gives full access and no royalties). This book saved my bacon. I almost did not buy it when all I saw in it was math. But I was desperate and it paid off. Turns out you could not explain it any other way. This book goes way beyond binary, and bubble sorts. I use it primarily for balanced trees. I may try something more exotic later. I can not tell you about the other volumes but this one will defiantly pay for itself.

[Topilno]

Creating Web Pages for Dummies

[marcel · Rating 4 out of 5]

Because of the emphasis placed on sorting and searching algorithms in the undergraduate curriculum, this volume is the most likely to show up on a computer science class' "recommended reading" list. True to its title, Volume 3 is split almost evenly between sorting, in the first half, and searching in the second. All of the bread-and-butter algorithms and data structures are covered, from quicksort to binary heaps to tries, which makes this a very important volume, but also perhaps a bit boring, since any computer science major will have seen many these concepts in undergraduate classes (though certainly in only a fraction of the detail that Knuth devotes to them). There is a somewhat large section, complete with a wonderful foldout, devoted to the ins-and-outs of merging large files stored on huge physical rolls of magnetic tape. I found this section quite entertaining because of the novelty of learning about how people used to store data, but most of it is quite useless to the modern reader. I believe that Knuth intends to scrap it and replace it with something else in the next edition.

[Abdellah · Rating 4 out of 5]

The Art of Computer Programming: Volume 3: Sorting and Searching is considered a comprehensive reference on the subject of sorting and searching algorithms. The book covers a wide range of algorithms, including basic methods such as insertion and bubble sort, as well as more advanced methods such as quicksort and merge sort. The book also covers searching algorithms, including linear search, binary search, and hash tables. The book is written in a clear, easy-to-understand style and includes numerous examples and exercises to help readers understand the concepts.

In addition to its coverage of algorithms, the book also includes chapters on data structures such as linked lists, trees, and graphs. The book also includes a discussion of computational complexity and performance analysis of algorithms, which is essential for understanding the trade-offs between different algorithms.

The book has been widely used as a textbook in computer science education and is also widely used as a reference by professionals in the field. It is considered an essential resource for anyone interested in the field of algorithms and data structures.

[Robert Fishell · Rating 5 out of 5]

Of the first 3 volumes in this series, this is the most essential after the first. Sorting and searching are among the most important concepts programmers need to master in order to become master programmers.

[Gaetano Venezia · Rating 4 out of 5]

Lives up to the hype as an excellent reference book, but definitely a difficult/tedious read without a specific goal and problem in mind. Cleared up several ambiguous ideas I had about search and sort algorithms and time complexity.

[Tuấn Kiệt · Rating 5 out of 5]

nice

[Manoj Khatri · Rating 5 out of 5]

The LEGEND.

[Jeffrey]

I haven't read this through, but I have used it is a reference.