Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sorting and Graphs - Coggle Diagram
Sorting and Graphs
Topological Sort
DAG: directed, acyclical graph (every graph has a vertice with degree 0)
-
-
every acyclical, directed graph has a topological order
-
Adjacency list
array adj. of |V| lists, one per v
-
-
-
-
Quicksort
-
How it works: Pick last element as A[r] (pivot) and partition array from left to right into A[p] < A[r] and A[p] > A[r]. Repeat for each partition. No work needed for combining, since they're sorted in place
-
Randomized Quicksort: Random pivot results in reasonably balanced split on average. Making both best and worst case running time θ(n logn)
-
Definitions
-
Sets vs Tuples
Sets: Unordered, No multiplicity
Tuples: ordered, multiplicity
-
Dijkstra's Algorithm
Input: directed graph, with non-negative weights and starting vertex s
Output: for each vertex the weight of the shortest path from s to v
-
-
Heap Sort
Heap: nearly complete binary tree, filled on all levels except possibly the lowest. Lowest level filled from left to right
k node on level j is stored at position: A[2^j + k-1]
Left child of node i: Left(i) = 2i
Right child of node i: Right (i) = 2i + 1
Parent of node at i: Parent(i) = (lower bound) i / 2
Min-heap: The smallest element is stored at the root: key [parent] ≤ key [child]
Max-heap: The largest element is stored at the root: key[parent] ≥ key [child]
-
-
Trees
Definitions:
One special vertex, called the root
Each non-root node has a unique node towards the root: its parent
Each node has at most two nodes away from the root: its children
A node without children is called a leaf
Connected, undirected, acyclic graph (n vertices, n-1 edges)
