Skip to content

dsysoev/fun-with-algorithms

Repository files navigation

Fun with algorithms

This repository was created during the study of Introduction to Algorithms, Third Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein book.

A well-written book with detailed implementation of algorithms.

Install

python3 -m venv venv 
source venv/bin/activate
pip install --upgrade pip
pip install -r requirements.txt 

List of Algorithms

List of algorithms presented in the book.

Sort algorithms comparison

Table of complexity of different sorting algorithms:

For plot beautiful performance chart run following command.

python sort/performance.py

Sort performance chart

Algorithm Worst case Average case
Insertion Sort O(n^2) O(n^2)
Merge Sort O(n*ln(n)) O(n*ln(n))
Heap Sort O(n*ln(n)) O(n*ln(n))
Quick Sort O(n^2) O(n*ln(n))
Counting Sort O(k + n) O(k + n)
Radix Sort O(d(k + n)) O(d(k + n))
Bucket Sort O(n^2) O(n)

Matrix multiplication

  • Naive matrix multiplication O(n^3)
  • Strassen matrix multiplication O(n^2.81)
python matrix/performance.py

Matrix multiplication performance

Additional

Useful links:

Linked Lists

Binary Tree