# 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;
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;
shellsort Shell.java n log3 n unknown c n 3/2 tight code;
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 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