This repository is a collection of ~20 popular algorithms implemented in Python. It's intended to cover different design paradigms
and if possible, to illustrate problems they solve.
-
Selection sort [code]
Basic O(n^2) sorting algorithm.
-
Quicksort [code]
An example of "divide and conquer" algorithm with an average O(n log n) complexity.
The implementation provides comparisons counter and pivot selection.
-
Merge sort [code]
Another example of "divide and conquer" algorithm. The implementation can monitor a number of inversions.
-
Heap sort [code]
There are two versions of this algorithm. The first one takes advantage of heapq library. The second one is a part of heap data structure implementation. That's exactly what makes a difference between this and selection sort algorithms - the heap under the hood.
-
Heap [code]
The implementation supports both, min and max heaps. There is also sort method and opportunity to draw a heap to stdout.
heap = Heap(maxheap=True) # maxheap
heap.heapify([1, -2, 3, 18, 2, -8, 12, 4, 5, -6, 9, 3, 2, 0, 45])
heap.draw(print_width=80) Level: 0
45
Level: 1
9 18
Level: 2
4 5 3 12
Level: 3
-2 3 -6 2 -8 2 0 1 -
Median maintenance [code]
Briefly speaking, there are two heaps, min and max. The algorithm do its best to keep a number of elements in each of them equal all the time.
The value "between" heaps is the median.
-
Prim-Dijkstra-Jarnik MST [code]
It's almost a copy of Dijkstra's shortest path algorithm. They're very similar to each other.
-
Kruskal's MST [code]
The implementation is based on union-find (disjoint-set) data structure.
-
Dijkstra shortest path [code]
It's almost a copy of Prim-Dijkstra-Jarnik MST algorithm. They're very similar to each other.
-
Bellman-Ford shortest path [code]
Bellman-Ford with negative weight cycle detection.
-
DFS topological sort [code]
Uses depth-first search on a directed acyclic graph. DFS recursive calls and backtracking.
-
Breadth-first search BFS [code]
It checks if a graph is connected. It can also count distance (as a number of edges) between nodes.
Works on both, directed and undirected graphs.
-
Kosaraju's strongly connected components algorithm [code]
Two runs of DFS. First run traverses the graph and builds a stack of nodes according to finishing times.
Second run traverses the reversed graph in the order of nodes in the stack, sets leaders and groups components.
-
Karger's mincut algorithm [code]
Karger's contraction concept is realized as a Monte Carlo type algorithm, that has to be run
multiple times
with hope to find minimum cuts, but with no guarantee.
-
2 sum problem [code]
Are there any two numbers in a given list, that create a given sum? Four approaches for solving the problem:brute force, hashing, binary search and inward walk.
-
Huffman codes [code]
Lossless compression based on prefix Huffman codes.
-
Knapsack problem [code]
Dynamic programming example, memoization leads to a pretty and effective solution.
-
Tasks scheduler [code]
Simple task scheduler based on weight/length ratio. Computes weighted completion time as well.
-
Clustering [code]
The algorithm groups items in k clusters. It's based on the "union-find" structure.
-
Adjacency list [code]
It's just a supporting tool for some of the above graph algorithms.
-
Display graph [code]
Another supporting tool. It uses matplotlib and networkx to display results of couple of the above graph algorithms.
-
If you'd like to learn more about algorithms, data structures, proofs and various theoretical concepts in general, I recommend Tim Roughgarden's classes where you should find a fair and satisfying set of information, that covers all these topics.
-
If you find a bug, typo or have any questions, please feel free to contact me.