Comment by kragen
10 hours ago
That's a cool project!
I feel like the presentation of Lomuto's algorithm on p.110 would be improved by moving the i++ after the swap and making the corresponding adjustments to the accesses to i outside the loop. Also mentioning that it's Lomuto's algorithm.
These comments are probably too broad in scope to be useful this late in the project, so consider them a note to myself. C as the language for presenting the algorithms has the advantage of wide availability, not sweeping performance-relevant issues like GC under the rug, and stability, but it ends up making the implementations overly monomorphic. And some data visualizations as in Sedgewick's book would also be helpful.
My biggest inspiration for this project, though, is The Art of Computer Programming (TAOCP), that level of depth and precision is the ultimate goal. I'm also planning to include formal proofs of all algorithms in Lean, though that could easily turn into a 10-year project.
Sedgewick's Algorithms book is great for practical learning but too tied to Java and implementation details. It is a bit shallow on theory, though the community and resources for other languages help.
That said, I personally prefer Introduction to Algorithms (CLRS) for its formal rigor and clear proofs, and Grokking Algorithms for building intuition.
The broader goal of this project is to build a well tested, reference quality set of implementations in C, Python, and Go. That is the next milestone.
Sedgewick is available for C also.
For clarification, I meant the Algorithms, 4th Edition book at https://algs4.cs.princeton.edu/home/ which is entirely in Java. All the example code, libraries, and exercises there use Java, and the authors explicitly note that the book is written for that language.
However, you are right, Prof. Sedgewick has long maintained versions of his material across multiple languages. I remember that the third edition has C, C++ and Java versions.
For visualization, I'm considering using the awesome Manim library by 3Blue1Brown (https://3b1b.github.io/manim/getting_started/quickstart.html). I'm not very good at visual design, but let see what I can come up with.
To reduce the current monomorphism, I might add a generic version using void* and a comparator, or generate code for a few key types, while keeping the simple monomorphic listings for readability. (Though this would make the code a bit more complex)