Algorithms and Data Structures Cheatsheet


We summarize the performance characteristics of classic algorithms and data structures for sorting, priority queues, symbol tables, and graph processing.


Sorting.

The table below summarizes the number of compares for a variety of sorting algorithms, as implemented in this textbook. It includes leading constants but ignores lower-order terms.

ALGORITHM CODE IN PLACE STABLE BEST AVERAGE WORST REMARKS
selection sort Selection.java ½ n 2 ½ n 2 ½ n 2 n exchanges;
quadratic in best case
insertion sort Insertion.java n ¼ n 2 ½ n 2 use for small or
partially-sorted arrays
bubble sort Bubble.java n ½ n 2 ½ n 2 rarely useful;
use insertion sort instead
shellsort Shell.java n log3 n unknown c n 3/2 tight code;
subquadratic
mergesort Merge.java ½ n lg n n lg n n lg n n log n guarantee;
stable
quicksort Quick.java n lg n 2 n ln n ½ n 2 n log n probabilistic guarantee;
fastest in practice
heapsort Heap.java n 2 n lg n 2 n lg n n log n guarantee;
in place
n lg n if all keys are distinct


Priority queues.

The table below summarizes the order of growth of the running time of operations for a variety of priority queues, as implemented in this textbook. It ignores leading constants and lower-order terms. Except as noted, all running times are worst-case running times.

DATA STRUCTURE CODE INSERT DEL-MIN MIN DEC-KEY DELETE MERGE
array BruteIndexMinPQ.java 1 n n 1 1 n
binary heap IndexMinPQ.java log n log n 1 log n log n n
d-way heap IndexMultiwayMinPQ.java logd n d logd n 1 logd n d logd n n
binomial heap IndexBinomialMinPQ.java 1 log n 1 log n log n log n
Fibonacci heap IndexFibonacciMinPQ.java 1 log n 1 1 log n log n
amortized guarantee


Symbol tables.

The table below summarizes the order of growth of the running time of operations for a variety of symbol tables, as implemented in this textbook. It ignores leading constants and lower-order terms.

worst case average case
DATA STRUCTURE CODE SEARCH INSERT DELETE SEARCH INSERT DELETE
sequential search
(in an unordered array)
SequentialSearchST.java n n n n n n
binary search
(in a sorted array)
BinarySearchST.java log n n n log n n n
binary search tree
(unbalanced)
BST.java n n n log n log n sqrt(n)
red-black BST
(left-leaning)
RedBlackBST.java log n log n log n log n log n log n
hash table
(separate-chaining)
SeparateChainingHashST.java n n n 1 1 1
hash table
(linear-probing)
LinearProbingHashST.java n n n 1 1 1
uniform hashing assumption


Graph processing.

The table below summarizes the order of growth of the worst-case running time and memory usage (beyond the memory for the graph itself) for a variety of graph-processing problems, as implemented in this textbook. It ignores leading constants and lower-order terms. All running times are worst-case running times.


PROBLEM ALGORITHM CODE TIME SPACE
path DFS DepthFirstPaths.java E + V V
cycle DFS Cycle.java E + V V
directed cycle DFS DirectedCycle.java E + V V
topological sort DFS Topological.java E + V V
bipartiteness / odd cycle DFS Bipartite.java E + V V
connected components DFS CC.java E + V V
strong components Kosaraju–Sharir KosarajuSharirSCC.java E + V V
Eulerian cycle DFS EulerianCycle.java E + V E + V
directed Eulerian cycle DFS DirectedEulerianCycle.java E + V V
transitive closure DFS TransitiveClosure.java V (E + V) V 2
minimum spanning tree Kruskal KruskalMST.java E log E E + V
minimum spanning tree Prim PrimMST.java E log V V
minimum spanning tree Boruvka BoruvkaMST.java E log V V
shortest paths (unit weights) BFS BreadthFirstPaths.java E + V V
shortest paths (nonnegative weights) Dijkstra DijkstraSP.java E log V V
shortest paths (negative weights) Bellman–Ford BellmanFordSP.java V (V + E) V
all-pairs shortest paths Floyd–Warshall FloydWarshall.java V 3 V 2
maxflow–mincut Ford–Fulkerson FordFulkerson.java E V (E + V) V
bipartite matching Hopcroft–Karp HopcroftKarp.java V ½ (E + V) V
assignment problem successive shortest paths AssignmentProblem.java n 3 log n n 2