Skip to content

About

Tested Python implementations of classic algorithms & data structures (sorting, searching, LRU cache, graph shortest paths) with complexity notes and CI.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Latest commit

 

History

5 Commits

Folders and files

Repository files navigation

python-algorithms-lab

Tested, documented implementations of classic algorithms and data structures in Python. Built as a reference for correctness and complexity trade-offs, not as a drop-in replacement for the standard library.

What's here

Module Algorithm Time Space
algolab/sorting/comparison_sorts.py Merge sort O(n log n) O(n)
algolab/sorting/comparison_sorts.py Quicksort (median-of-3 pivot, insertion-sort cutoff, tail recursion on the larger partition) O(n log n) avg O(log n)
algolab/searching/binary_search.py Binary search, lower_bound / upper_bound O(log n) O(1)
algolab/structures/lru_cache.py LRU cache (hash map + doubly linked list) O(1) get/put O(capacity)
algolab/graphs/shortest_path.py Dijkstra, BFS shortest path O((V+E) log V) / O(V+E) O(V)

Notable design decisions

  • Quicksort uses median-of-three pivot selection and recurses into the smaller partition first (looping into the larger one) specifically to avoid O(n²) blowups and recursion-depth issues on already-sorted or reverse-sorted input — a naive first/last-element pivot implementation degrades badly on exactly that input shape. Falls back to insertion sort below a 12-element cutoff, which is faster than the recursive overhead for small ranges.
  • LRUCache uses sentinel head/tail nodes in its linked list so insert/remove never need null checks for "am I at the boundary."
  • Dijkstra explicitly rejects negative edge weights rather than silently returning wrong answers.

Running the tests

pip install pytest
pytest -v

62 tests covering empty inputs, duplicates, adversarial ordering, mutation safety, and randomized differential testing against Python's built-in sorted().

Project structure

algolab/
  sorting/comparison_sorts.py
  searching/binary_search.py
  structures/lru_cache.py
  graphs/shortest_path.py
tests/
  test_sorting.py
  test_searching.py
  test_lru_cache.py
  test_shortest_path.py

About

Tested Python implementations of classic algorithms & data structures (sorting, searching, LRU cache, graph shortest paths) with complexity notes and CI.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages