BucketSort, RadixSort, and Linear Time Sorting Algorithms Explained

CSE 332 Winter 2024 Lecture 16: Radix Sort, Graphs Nathan Brunelle http://www.cs.uw.edu/332

Linear Time Sorting Algorithms Useable when you are able to make additional assumptions about the contents of your list (beyond the ability to compare) Examples: The list contains only positive integers less than ? The number of distinct values in the list is much smaller than the length of the list The running time expression will always have a term other than the list s length to account for this assumption Examples: Running time might be (? ?) where ? is the range/count of values

BucketSort Assumes the array contains integers between 0 and ? 1 (or some other small range) Idea: Use each value as an index into an array of size ? Add the item into the bucket at that index (e.g. linked list) Get sorted array by appending all the buckets 0 0 0 0 0 2 2 2 3 3 1 1 0 2 3 0 0 1 2 1 3 0 2 0 0 0 0 0 0 1 1 2 2 2 3 3 0 1 2 3

BucketSort Running Time Create array of ? buckets Either (?) or (1)depending on some things Insert all ? things into buckets (?) Empty buckets into an array (? + ?) Overall: ? + ? When is this better than mergesort?

Properties of BucketSort In-Place? No Adaptive? No Stable? Yes!

RadixSort Radix: The base of a number system We ll use base 10, most implementations will use larger bases Idea: BucketSort by each digit, one at a time, from least significant to most significant 103 801 401 323 255 823 999 101 113 901 555 512 245 800 018 121 4 5 7 12 13 15 0 1 2 3 6 8 9 10 11 14 801 401 101 901 121 103 323 823 113 255 555 245 Place each element into a bucket according to its 1 s place 800 018 512 999 4 5 7 0 1 2 3 6 8 9

RadixSort Radix: The base of a number system We ll use base 10, most implementations will use larger bases Idea: BucketSort by each digit, one at a time, from least significant to most significant 801 401 101 901 121 103 323 823 113 255 555 245 800 018 512 999 800 801 401 101 901 103 4 5 7 0 1 2 3 6 8 9 512 113 018 121 323 823 255 555 245 999 Place each element into a bucket according to its 10 s place 4 5 7 0 1 2 3 6 8 9

RadixSort Radix: The base of a number system We ll use base 10, most implementations will use larger bases Idea: BucketSort by each digit, one at a time, from least significant to most significant 800 801 401 101 901 103 512 113 018 121 323 823 255 555 245 999 101 103 113 121 800 801 823 4 5 7 0 1 2 3 6 8 9 245 255 512 555 901 999 323 401 018 Place each element into a bucket according to its 100 s place 4 5 7 0 1 2 3 6 8 9

RadixSort Radix: The base of a number system We ll use base 10, most implementations will use larger bases Idea: BucketSort by each digit, one at a time, from least significant to most significant 101 103 113 121 800 801 823 245 255 512 555 901 999 323 401 018 Convert back into an array 4 5 7 0 1 2 3 6 8 9 018 811 103 113 121 245 255 323 401 512 555 800 801 823 901 999 4 5 7 12 13 15 0 1 2 3 6 8 9 10 11 14

RadixSort Running Time Suppose largest value is ? Choose a radix (base of representation) ? BucketSort all ? things using ? buckets (? + ?) Repeat once per each digit log?? iterations Overall: ?log?? + ?log?? In practice, you can select the value of ? to optimize running time When is this better than mergesort?

ARPANET 11

Undirected Graphs Vertices/Nodes Definition: ? = (?,?) Edges ? = {1,2,3,4,5,6,7,8,9} 2 5 ? = { 1,2 , 2,3 ,(1,3), } 8 1 4 9 3 7 6 12

Directed Graphs Vertices/Nodes Definition: ? = (?,?) Edges ? = {1,2,3,4,5,6,7,8,9} 2 5 ? = { 1,2 , 2,3 ,(1,3), } 8 1 4 9 3 7 6 13

Self-Edges and Duplicate Edges Some graphs may have duplicate edges (e.g. here we have the edge (1,2) twice). Some may also have self-edges (e.g. here there is an edge from 1 to 1). Graph with Neither self-edges nor duplicate edges are called simple graphs 2 5 8 1 4 9 3 7 6 14

Weighted Graphs Vertices/Nodes Definition: ? = (?,?) ? ? = weight of edge ? Edges 8 ? = {1,2,3,4,5,6,7,8,9} 2 5 8 10 ? = { 1,2 , 2,3 ,(1,3), } 8 7 2 1 9 5 4 9 9 12 3 3 3 11 7 1 6 15 6

Graph Applications For each application below, consider: What are the nodes, what are the edges? Is the graph directed? Is the graph simple? Is the graph weighted? Facebook friends Twitter followers Java inheritance Airline Routes

Some Graph Terms 2 5 8 1 Adjacent/Neighbors Nodes are adjacent/neighbors if they share an edge Degree Number of neighbors of a vertex Indegree Number of incoming neighbors Outdegree Number of outgoing neighbors 4 9 3 7 6 2 5 8 1 4 9 3 7 6

Graph Operations To represent a Graph (i.e. build a data structure) we need: Add Edge Remove Edge Check if Edge Exists Get Neighbors (incoming) Get Neighbors (outgoing)

Adjacency List 2 5 3 1 2 8 3 5 2 1 1 4 9 2 4 1 3 6 3 4 3 5 6 7 6 4 7 2 8 5 Time/Space Tradeoffs Space to represent: (? + ?) Add Edge: (1) Remove Edge: (1) Check if Edge Exists: (?) Get Neighbors (incoming): (? + ?) Get Neighbors (outgoing): deg ? 6 4 7 3 6 8 7 5 9 ? = ? ? = ? 7 9 5 8 8 9 7 19

Adjacency List (Weighted) 8 2 5 3 1 2 10 8 8 7 3 5 2 1 2 1 9 5 4 9 9 2 4 1 3 6 12 3 3 3 4 3 5 6 11 7 6 1 6 4 7 2 8 5 Time/Space Tradeoffs Space to represent: (? + ?) Add Edge: (1) Remove Edge: (1) Check if Edge Exists: (?) Get Neighbors (incoming): (?) Get Neighbors (outgoing): (?) 6 4 7 3 6 8 7 5 9 ? = ? ? = ? 7 9 5 8 8 9 7 20

Adjacency Matrix 2 5 C D E F I A B G H 8 1 A 1 1 4 9 1 1 1 B 1 C 1 1 1 3 1 1 1 D 7 6 1 1 1 1 E Time/Space Tradeoffs Space to represent: (?) Add Edge: (?) Remove Edge: (?) Check if Edge Exists: (?) Get Neighbors (incoming): (?) Get Neighbors (outgoing): ? 1 1 1 F G 1 1 1 1 1 1 1 H ? = ? ? = ? I 1 1 21

Adjacency Matrix (weighted) 8 2 5 10 8 C D E F I A B G H 8 7 2 1 A 1 1 9 5 4 9 9 1 1 1 B 12 3 1 C 1 1 1 3 3 11 1 1 1 D 7 6 1 6 1 1 1 1 E Time/Space Tradeoffs Space to represent: (?2) Add Edge: (1) Remove Edge: (1) Check if Edge Exists: (1) Get Neighbors (incoming): (?) Get Neighbors (outgoing): ? 1 1 1 F G 1 1 1 1 1 1 1 H ? = ? ? = ? I 1 1 22

Aside Almost always, adjacency lists are the better choice Most graphs are missing most of their edges, so the adjacency list is much more space efficient and the slower operations aren t that bad

Definition: Path A sequence of nodes (?1,?2, ,??) s.t. 1 ? ? 1, ??,??+1 ? 8 B E 10 8 H 7 2 A 9 5 D 9 I 12 3 3 C 11 G F 1 6 Simple Path: A path in which each node appears at most once Cycle: A path which starts and ends in the same place 24

Definition: (Strongly) Connected Graph A Graph ? = (?,?) s.t. for any pair of nodes ?1,?2 ? there is a path from ?1 to ?2 2 5 2 5 8 8 1 1 4 4 9 9 3 3 7 7 6 6 25

Definition: (Strongly) Connected Graph A Graph ? = (?,?) s.t. for any pair of nodes ?1,?2 ? there is a path from ?1 to ?2 2 5 2 5 8 8 1 1 4 4 9 9 3 3 7 7 6 6 Connected Not (strongly) Connected 26

Definition: Weakly Connected Graph A Graph ? = (?,?) s.t. for any pair of nodes ?1,?2 ? there is a path from ?1 to ?2 ignoring direction of edges 2 5 2 5 8 8 1 1 4 4 9 9 3 3 7 7 6 6 Weakly Connected Weakly Connected 27

Definition: Complete Graph A Graph ? = (?,?) s.t. for any pair of nodes ?1,?2 ? there is an edge from ?1 to ?2 1 2 1 2 1 2 4 3 4 4 3 3 Complete Undirected Graph Complete Directed Graph Complete Directed Non-simple Graph 28

Graph Density, Data Structures, Efficiency The maximum number of edges in a graph is |?|2: Undirected and simple: |?|(|?| 1) Directed and simple: |?|(|?| 1) Direct and non-simple (but no duplicates): |?|2 If the graph is connected, the minimum number of edges is ? 1 If ? ?2 we say the graph is dense If ? |?| we say the graph is sparse Because ? is not always near to ?2 we do not typically substitute ?2 for ? in running times, but leave it as a separate variable 2

Definition: Tree A Graph ? = (?,?) is a tree if it is undirect, connected, and has no cycles (i.e. is acyclic). Often one node is identified as the root 4 2 5 8 1 4 3 5 6 9 1 3 8 7 6 2 9 7 A Tree A Rooted Tree 30

Breadth-First Search Input: a node ? Behavior: Start with node ?, visit all neighbors of ?, then all neighbors of neighbors of ?, Output: How long is the shortest path? Is the graph connected? 2 5 8 1 4 9 3 7 6 31

void bfs(graph, s){ found = new Queue(); found.enqueue(s); mark s as visited ; While (!found.isEmpty()){ current = found.dequeue(); for (v : neighbors(current)){ if (! v marked visited ){ } } } } BFS 2 5 8 1 4 9 3 7 6 mark v as visited ; found.enqueue(v); Running time: ? + ? 32

int shortestPath(graph, s, t){ found = new Queue(); layer = 0; found.enqueue(s); mark s as visited ; While (!found.isEmpty()){ current = found.dequeue(); layer = depth of current; for (v : neighbors(current)){ } } return depth of t; } Shortest Path (unweighted) 2 5 8 1 4 9 3 if (! v marked visited ){ mark v as visited ; depth of v = layer + 1; found.enqueue(v); } 7 6 Idea: when it s seen, remember its layer depth! 33

Depth-First Search

Depth-First Search Input: a node ? Behavior: Start with node ?, visit one neighbor of ?, then all nodes reachable from that neighbor of ?, then another neighbor of ?, Output: Does the graph have a cycle? A topological sort of the graph. 1 2 2 5 3 0 8 6 1 4 9 3 5 7 6 4 35 7

void dfs(graph, s){ found = new Stack(); found.pop(s); mark s as visited ; While (!found.isEmpty()){ current = found.pop(); for (v : neighbors(current)){ if (! v marked visited ){ } } } } DFS (non-recursive) 2 5 8 1 4 9 3 7 6 mark v as visited ; found.push(v); Running time: ? + ? 36

DFS Recursively (more common) void dfs(graph, curr){ mark curr as visited ; for (v : neighbors(current)){ if (! v marked visited ){ } } mark curr as done ; } dfs(graph, v); 2 5 8 1 4 9 3 7 6 37