algs4

This repository contains C++ implementations of the algorithms and clients in the textbook Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

For the original Java source code, visit the official repository.

• 1.1 Pushdown stack (resizing array): Stack.hpp
• 1.2 Pushdown stack (linked-list): LinkedStack.hpp
• 1.3 FIFO queue: Queue.hpp
• 1.4 Bag: Bag.hpp
• 1.5 Union-find: UF.hpp

• 2.1 Selection sort: Selection.hpp
• 2.2 Insertion sort: Insertion.hpp
• 2.3 Shellsort: Shell.hpp
• 2.4 Top-down mergesort: Merge.hpp
• Bottom-up mergesort: MergeBU.hpp
• 2.5 Quicksort: Quick.hpp
• Quicksort with 3-way partitioning: Quick3way.hpp
• 2.6 Heap priority queue: MaxPQ.hpp
• 2.7 Heapsort: Heap.hpp

• 3.1 Sequential search: SequentialSearchST.hpp
• 3.2 Binary search: BinarySearchST.hpp
• 3.3 Binary tree search: BST.hpp
• 3.4 Red-black BST search: RedBlackBST.hpp
• 3.5 Hashing with separate chaining: SeparateChainingHashST.hpp
• 3.6 Hashing with linear probing: LinearProbingHashST.hpp

• 4.1 Depth-first search: DepthFirstPaths.hpp
• 4.2 Breadth-first search: BreadthFirstPaths.hpp
• 4.3 Connected components: CC.hpp
• 4.4 Reachability: DirectedDFS.hpp
• 4.5 Topological order: Topological.hpp
• 4.6 Strong components (Kosaraju): KosarajuSCC.hpp
• 4.7 Minimum spanning tree (Prim): PrimMST.hpp
• 4.8 Minimum spanning tree (Kruskal): KruskalMST.hpp
• 4.9 Shortest paths (Dijkstra): DijkstraSP.hpp
• 4.10 Shortest paths in DAGs: AcyclicSP.hpp
• 4.11 Shortest paths (Bellman-Ford): BellmanFordSP.hpp

• 5.1 LSD string sort: LSD.hpp
• 5.2 MSD string sort: MSD.hpp
• 5.3 Three-way string quicksort: Quick3string.hpp
• 5.4 Trie symbol table: TrieST.hpp
• 5.5 TST symbol table: TST.hpp
• 5.6 Substring search (Knuth-Morris-Pratt): KMP.hpp
• 5.7 Substring search (Boyer-Moore): BoyerMoore.hpp
• 5.8 Substring search (Rabin-Karp): RabinKarp.hpp
• 5.9 Regular expression pattern matching: NFA.hpp
• 5.10 Huffman compression/expansion: Huffman.hpp
• 5.11 LZW compression/expansion: LZW.hpp

• Stack (Stack, LinkedStack): Stack.cpp.in
• Queue (Queue): Queue.cpp
• Bag (Bag): Bag.cpp
• Union-find (UF): UF.cpp

• Sorts (Selection, Insertion, Shell, Merge, MergeBU, Quick, Quick3way, Heap): Sorting.cpp.in
• Heap priority queue (MaxPQ): MaxPQ.cpp

• Symbol table tests (TestSequentialSearchST, TestBinarySearchST, TestBST, TestRedBlackBST, TestSeparateChainingHashST, TestLinearProbingHashST): TestST.cpp.in

• Depth-first search (DepthFirstPaths) | Breadth-first search (BreadthFirstPaths): Paths.cpp.in
• Connected components (CC, KosarajuSCC): CC.cpp.in
• Reachability (DirectedDFS): DirectedDFS.cpp
• Topological order (Topological): Topological.cpp
• Minimum spanning tree (PrimMST, KruskalMST): MST.cpp.in
• Shortest paths (DijkstraSP, AcyclicSP, BellmanFordSP): SP.cpp.in

• String sorts (LSD, MSD, Quick3string): Sorting.cpp.in
• Trie symbol table tests (TestTrieST) | TST symbol table tests (TestTST): TestST.cpp.in
• Substring search (KMP, BoyerMoore, RabinKarp): SubstrSearch.cpp.in
• Regular expression pattern matching (GREP): GREP.cpp
• Huffman compression/expansion (Huffman) | LZW compression/expansion (LZW): Compress.cpp.in

This project uses CMake as the build system. Ensure you have CMake 3.21+ and a C++20 compliant compiler.

cmake -B build
cmake --build build

By default, all clients are built and the executables can be found in the build directory. Refer to the comments in the source files listed in Clients for instructions on how to run each client. Go to the book's website for test data.

Add to your CMakeLists.txt:

add_subdirectory(/path/to/algs4)
target_link_libraries(your_target PRIVATE algs4)

If you are not using CMake, simply ensure the include/ directory is in your compiler's include path and include the headers you need.