# douchuan/algorithm: the Sedgewick algorithms in Rust

> This repository is a Rust port of the algorithms in Algorithms, 4th Edition by Sedgewick and Wayne, structured to follow the book's numbering so a reader can move between the textbook and the code. The naming is deliberately faithful to the original, which cuts both ways when it comes to idiomatic Rust.

**douchuan/algorithm** — Algorithms written in Rust

- Repository: https://github.com/douchuan/algorithm
- Stars: 584 · Forks: 53
- Language: Rust
- License: MIT
- Published: 2026-10-22 · Updated: 2026-10-22 · Language: en
- Canonical page: https://hysenlabs.com/projects/douchuan-algorithm

## The module names are the book's section numbers

The README is short, and its central idea is stated in the Overview. This repository contains the Rust source code for the algorithms in the textbook Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne, and the official Java source code is hosted separately at the algs4 repository by the same author.

The Goals section explains the design. The aim is to make a Rust implementation of the library so that a Rust programmer can follow the book easily, or prefer to demonstrate the algorithms using Rust, and the stated rule is to keep the interface and variable name consistent with the original book while writing idiomatic Rust code.

That is visible in the Index. Each row is a book section number on the left and a Rust item on the right, and the item names are the book's own: `1.2` is a LIFO stack, `1.3` a FIFO queue, `1.4` a multiset linked list, and `1.5` through the QuickFindUF, QuickUnionUF, WeightedQuickUnionUF and UF series, which the index describes as union-by-rank with path halving. Chapter 2 is sorting, with `2.1` insert.rs for insertion sort, `2.2` selection.rs, `2.3` shell.rs, `2.4` merge.rs, `2.5` quick.rs, and `2.7` floyd.rs described as heapsort. Chapter 3 is searching with `3.4` rb2.rs for the red-black tree and `3.6` SparseVector. Chapter 4 is graphs, and it is the longest section, running from the undirected Graph and DepthFirstSearch through Digraph, the shortest path family, and into the string algorithms in chapter 5 with `5.1` LSD, `5.2` MSD, `5.4` TrieST, `5.5` TST and `5.6` KMP.

For a reader with the book open, this is an unusually usable index. For a programmer looking for a general library, it is a red flag, and the honest reading is that this is a teaching repository rather than a dependency.

## Naming the book is the point, and it costs you idiomatic Rust

The Goals section asks for consistency with the original book in interface and variable names, and the Index shows how far that goes. `PQ::new_max_pq` and `PQ::new_min_pq` are the max and min heap priority queues, `IndexPQ::new_min_pq` and `IndexPQ::new_max_pq` are the index variants, `TopM` finds the largest M elements, `SparseVector` is the sparse vector, `CC` is connected components, `Bipartite` finds a bipartite or odd cycle by DFS, `SymbolGraph` is the symbol graph, `KosarajuSCC` finds strong components, `LazyPrimMST` and `PrimMST` and `KruskalMST` are the three minimum spanning tree implementations, `DijkstraSP` and `DijkstraAllPairsSP` and `AcyclicSP` and `BellmanFordSP` are the shortest path solvers, `Arbitrage` does arbitrage detection, and `CPM` is the critical path method.

`Quick3Way`, `Quick3String` and `TrieST` follow the same convention. These are the book's names, not the ones a Rust library would choose, and that is the central trade-off in the project.

The benefit is real and specific. If you are reading the book, the code is findable by section number, and when the text says to implement a union-by-rank with path halving, the module named UF is where that lives. You are not translating between two naming systems.

The cost is equally specific. A crate that exposes `PQ::new_max_pq` as part of a public API has made a choice about its interface that is defensible for a book companion and questionable for anything else. It is a teaching artifact that happens to compile, and the `instrument` feature flag plus the `instrument` cargo feature in the manifest is the sort of thing that only makes sense in that context.

## The build wants a nightly toolchain, not a stable one

The Running section of the README is two lines, and both matter.

```bash
# setup Rust Toolchain
make test
```

The Makefile shows what `make test` actually does. The `CARGO` variable is `RUST_BACKTRACE=1 rustup run nightly cargo`, and the test, bench and build targets all go through it. So the whole crate is built and tested with a nightly Rust toolchain, with backtraces enabled.

That is a meaningful constraint for anyone planning to depend on this. Nightly is a moving target, and a project pinned to it does not inherit the stability guarantees of a release channel. It also means a contributor needs rustup with the nightly toolchain installed, which the README flags as a setup step.

The rest of the Makefile is a small set of conveniences. `build` calls the build target, `clippy` runs clippy, `bench` runs the benchmarks, `eg_quadratic` runs the quadratic example, and `doc` runs `cargo doc --open`. There is a `stats` target that runs `cloc` for a line count, counts commits, finds the first commit date with `git rev-list --max-parents=0 HEAD`, and reports the size of the target directory, which is a maintainer convenience rather than something a user would invoke.

The Cargo manifest explains the rest of the shape. The package is `algorithm` at version 0.1.0 with edition 2021, the license is MIT, and the library target is named `algo` with its path at `src/lib.rs`. The runtime dependencies are `lazy_static`, `libc`, `nom` at version 7 and `rand` at 0.8, with `approx` and `plotters` as dev dependencies, and a `cc` build dependency, which is what compiles the C sources in the `cpp/` directory.

## The repository carries the original C sources and a plotting harness

The top level of the repository shows that this is more than a set of Rust files.

There is a `cpp/` directory, which lines up with the `cc` build dependency in the Cargo manifest. Non-Rust sources compiled into the build through the `cc` crate, and the `build.rs` file at the root is what wires that compilation into the Cargo build.

There is a `benches/` directory, and `plotters` as a dev dependency explains what they are for. The dev dependency list is short, with `approx` for floating point comparison in tests and `plotters` for producing charts. Combined with the `plotters-doc-data/` directory in the repository root, that is a plotting setup for visualizing algorithm behavior, which connects to the Roadmap.

The Roadmap has two items. Implement algorithms in the textbook Algorithms, 4th Edition, which is the ongoing work, and algorithms visualization, described as easy to study with a short learning curve. The second one is the interesting commitment, because visualization is what makes an algorithm legible, and it is the reason for a plotting dependency in a crate whose stated purpose is a textbook port.

The rest of the tree is conventional Rust. `src/` holds the implementation, `tests/` the test suite, `examples/` the runnable examples, and the only example listed is `quadratic.rs`, which corresponds to the `eg_quadratic` Makefile target. There is a `CheatSheet.md` at the root, a `todos.md`, a `res/` directory, a `build.rs`, and a `Cargo.lock` committed alongside the manifest, so builds are reproducible.

## The coverage is uneven, and the index shows you where

Reading the Index as a table rather than as a list of names tells you what this repository is and is not.

The fundamentals and sorting chapters are close to complete. Stack, queue, linked list and the four union-find variants are all there, all five sorting algorithms are there, and the priority queue family is there with four variants plus `TopM`.

The graphs chapter is the deepest, covering undirected and directed graphs, DFS and BFS with path extraction, connected components, bipartite detection, cycle detection, symbol graphs, topological order, transitive closure, strong components, edge-weighted graphs, three minimum spanning tree implementations, four shortest path algorithms, the critical path method, and arbitrage detection.

The strings chapter is where the coverage thins. The index lists `Alphabet`, a count.rs client, `LSD`, `MSD`, `Quick3String`, `TrieST`, `TST` and `KMP`, and that is the end of the list. The README's own table index links to the Princeton code site, which is the place to see the full catalogue the book covers, and the gap between the two is the honest measure of what is implemented here.

So if your interest is sorting, union-find, priority queues, graph traversal or shortest paths, this repository is a solid reference. If your interest is the string-processing material, the last third of the book, you will be reading the book and writing the code yourself.

That unevenness is normal for a port in progress, and the `todos.md` file at the repository root is where the remaining work is presumably tracked. The `todos.md` file is the visible hint that the remaining work is tracked somewhere.

## Compared with a general algorithms crate and with the original implementations

Two other options exist, and each teaches something different.

A general purpose Rust algorithms crate, the kind published on crates.io with a semver policy and a documented API surface, is what you want when you are writing an application. Its names are not tied to a textbook, its channel is stable, and it carries a compatibility promise. The trade is that the algorithms are chosen for general utility rather than for pedagogy, so the code is less likely to read like the book and less likely to be the clearest possible implementation of a specific idea.

The original implementations are the other option, and for algorithms the 4th edition the reference Java source at the algs4 repository is public and maintained by the book's author. The difference in approach is that the Java is the canonical, minimal, teaching-oriented code, while this Rust port is a translation that has to make Rust's ownership model fit algorithms that in Java are passed around by reference. The `cpp/` directory and the `build.rs` script show that compiled non-Rust sources are part of this crate.

For a Rust programmer, the port is the point. The Goals section says it plainly: so a Rust programmer can follow the book easily, or prefer to demonstrate the algorithms using Rust. The argument for Rust over Java in that sentence is the one the README then makes at length, that the compiler acts as a gatekeeper refusing to compile code with elusive bugs including concurrency bugs, and that working alongside the compiler lets you spend your time on the program's logic rather than chasing bugs, with the promise of a good night's sleep and no system crashes.

That is a claim about the language rather than about the port, and it is worth reading as such. The port's value is that it lets you study the algorithms in a language that will not let certain mistakes compile, which is a real but narrower benefit than the passage suggests.

## Conclusion

Adopt this repository if you are working through Algorithms, 4th Edition and want to follow the book in Rust, or you need a readable reference implementation of a specific data structure to adapt. Do not adopt it as a general purpose algorithms crate to depend on, since the naming is tied to textbook sections rather than to a public API, and the build expects a nightly toolchain. Verify first which of the book's structures you actually need, because the index shows the coverage is uneven across chapters, and check the `cpp/` directory if you want to compare against the original implementations.

## FAQ

### What is the douchuan/algorithm repository?

It contains the Rust source code for the algorithms in the textbook Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. The goal stated in the README is to make a Rust implementation of the library so a Rust programmer can follow the book, while keeping the interface and variable names consistent with the original.

### How do I build and test the douchuan/algorithm crate?

The README's Running section gives a Makefile target, `make test`, and notes that a Rust toolchain must be set up first. The Makefile runs cargo through `rustup run nightly cargo`, so the crate is built and tested with a nightly toolchain rather than a stable release.

### Which algorithms are implemented in douchuan/algorithm?

The index follows the book: fundamentals including stack, queue, linked list and four union-find variants, sorting with insertion, selection, shell, merge, quick and heapsort, priority queues, searching with a red-black tree, and a large graphs section covering traversal, connected components, minimum spanning trees, shortest paths, topological sort and critical path. Strings are thinner, covering radix sort, tries and KMP.

### Why are the module names in douchuan/algorithm unusual?

The names deliberately follow the textbook rather than Rust conventions, so `PQ::new_max_pq` is the max heap priority queue, `CC` is connected components and `KosarajuSCC` finds strong components. The README's stated goal is keeping the interface and variable names consistent with the original book, which is a teaching-first choice rather than a library-first one.

### What licence is douchuan/algorithm under?

MIT, as declared in both the Cargo.toml manifest and the LICENSE file at the repository root. The crate is named `algorithm` at version 0.1.0 with edition 2021, and the library target is named `algo` with its path at `src/lib.rs`.

## Sources

- [douchuan/algorithm on GitHub](https://github.com/douchuan/algorithm)
- [Issues](https://github.com/douchuan/algorithm/issues)
- [License: MIT](https://github.com/douchuan/algorithm/blob/main/LICENSE)
- [README](https://github.com/douchuan/algorithm/blob/main/README.md)

---

Hysen Labs editorial analysis, written from the project's own repository and release notes. Cite the canonical page: https://hysenlabs.com/projects/douchuan-algorithm