Overview

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.

Algorithms

Fundamentals

• 1.5 Union-find: UF.hpp

Sorting

• 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

Symbol Tables

• 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

Graphs

• 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

Strings

• 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

Clients

Fundamentals

• Union-find (UF): UF.cpp

Sorting

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

Symbol Tables

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

Graphs

• 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

Strings

• 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

Usage

Build the project

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

Run the clients

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.

Use as a header-only library

Option A: CMake add_subdirectory

Add to your CMakeLists.txt:

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

Option B: Simple include

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

#include <iostream>
#include <string>

#include "algs4/BST.hpp"

int main() {
    algs4::BST<std::string, int> st;
    
    st.put("A", 1);
    st.put("B", 2);
    
    if (const auto &val = st.get("A"))
        std::cout << "Key A has value: " << *val << std::endl;
    
    return 0;
}