Sorting Algorithms Review

💬 Discuss: describe how you would sort [7, 2, 9, 4, 1, 6, 3, 8, 5] using:

1. Bubble Sort.
2. Selection Sort.
3. Merge Sort.

13A: Sorting and Graphs

August 12, 2026 // Jennifer Zhao

Overview

What will we learn today?

1. Selection Sort Review
2. Merge Sort Review
3. In-Place Sorting
4. What Are Graphs?
5. Graph Vocabulary
6. Graphs In Code

Selection Sort Review…

Selection Sort Demonstration

1. Look at the unsorted elements. Find the smallest unsorted element.
2. Swap the smallest unsorted element with the element sitting at the most left of the unsorted zone.
3. Repeat on the new, smaller unsorted zone.

Merge Sort Review…

Live Demonstration…

1. Split list into two halves, left and right.
2. Sort the left half by Merge Sort.
3. Sort the right half by Merge Sort.
4. Merge the two sorted halves into one sorted list.

In-Place Sorting

In-Place Sorting

What does this function return?

def selection_sort(arr):

for i in range(len(arr)):

smallest = i

for j in range(i + 1, len(arr)):

if arr[j] < arr[smallest]:

smallest = j

arr[i] = temp

arr[i] = arr[smallest]

arr[smallest] = temp

def merge_sort(arr):

​

if len(arr) <= 1:

return arr

​

mid = len(arr) // 2

​

left = merge_sort(arr[:mid])

right = merge_sort(arr[mid:])

merged_list = merge(left, right)

​

return merged_list

In-Place Sorting

What does this function return?�→ None

What does this function return?�→ None

def selection_sort(arr):

for i in range(len(arr)):

smallest = i

for j in range(i + 1, len(arr)):

if arr[j] < arr[smallest]:

smallest = j

arr[i] = temp

arr[i] = arr[smallest]

arr[smallest] = temp

def merge_sort(arr):

​

if len(arr) <= 1:

return arr

​

mid = len(arr) // 2

​

left = merge_sort(arr[:mid])

right = merge_sort(arr[mid:])

merged_list = merge(left, right)

​

return merged_list

In-Place Sorting

What does this function return?�→ None

What does this function return?�

def selection_sort(arr):

for i in range(len(arr)):

smallest = i

for j in range(i + 1, len(arr)):

if arr[j] < arr[smallest]:

smallest = j

arr[i] = temp

arr[i] = arr[smallest]

arr[smallest] = temp

def merge_sort(arr):

​

if len(arr) <= 1:

return arr

​

mid = len(arr) // 2

​

left = merge_sort(arr[:mid])

right = merge_sort(arr[mid:])

merged_list = merge(left, right)

​

return merged_list

In-Place Sorting

What does this function return?�→ None

What does this function return?�→ A sorted list!

def selection_sort(arr):

for i in range(len(arr)):

smallest = i

for j in range(i + 1, len(arr)):

if arr[j] < arr[smallest]:

smallest = j

arr[i] = temp

arr[i] = arr[smallest]

arr[smallest] = temp

def merge_sort(arr):

​

if len(arr) <= 1:

return arr

​

mid = len(arr) // 2

​

left = merge_sort(arr[:mid])

right = merge_sort(arr[mid:])

merged_list = merge(left, right)

​

return merged_list

In-Place Sorting

This function mutates/changes the original list…

This function creates a new list and returns it!

def selection_sort(arr):

for i in range(len(arr)):

smallest = i

for j in range(i + 1, len(arr)):

if arr[j] < arr[smallest]:

smallest = j

arr[i] = temp

arr[i] = arr[smallest]

arr[smallest] = temp

def merge_sort(arr):

​

if len(arr) <= 1:

return arr

​

mid = len(arr) // 2

​

left = merge_sort(arr[:mid])

right = merge_sort(arr[mid:])

merged_list = merge(left, right)

​

return merged_list

What Are Graphs?

What Are Graphs?

A graph is:

• A list of vertices (nodes).
• And a list of edges.

4

1

7

2

3

5

6

8

0

What Are Graphs?

A graph is:

• A list of vertices (nodes).
• And a list of edges.

4

1

7

2

3

5

6

8

0

What Are Graphs?

• Undirected → edges do not have direction.

4

1

7

2

3

5

6

8

0

What Are Graphs?

• Undirected → edges do not have direction.
• Directed → edges have direction.

4

1

7

2

3

5

6

8

0

What Are Graphs?

• For example, this graph might represent cities with one-way roads in-between.
• Or, this graph might represent who follows who on social media.

4

1

7

2

3

5

6

8

0

What Are Graphs?

• For example, this graph might represent cities with one-way roads in-between.

​

💬 Discuss: what could you represent with an undirected graph? With a directed graph?

4

1

7

2

3

5

6

8

0

What Are Graphs?

What Are Graphs?

• Is this a graph?

4

1

7

2

3

5

6

8

0

What Are Graphs?

• Is this a graph?
• Yes! But let's talk only about simple graphs for now…
• No self loops.

4

1

7

2

3

5

6

8

0

Graph Vocabulary

Graph Vocabulary

Because there is an edge between vertex 1 and �vertex 4, these two vertices are adjacent.

​

Equivalently, vertex 4 is a neighbor of vertex 1.

4

1

7

2

3

5

6

8

0

Graph Vocabulary

The degree of a node is the number of neighbors.

​

Vertex 4 has a degree of 3.

4

1

7

2

3

5

6

8

0

Graph Vocabulary

The degree of a node is the number of neighbors.

​

Vertex 4 has a degree of 3.

Vertex 1 has a degree of 1.

4

1

7

2

3

5

6

8

0

Graph Vocabulary

• For a directed edge from u to v, u is the predecessor. v is the successor.
• The in-degree of a vertex is its # of predecessors.
• The out-degree is its # of successors.

4

1

7

2

3

5

6

8

0

Graph Vocabulary

💬 Discuss: what is the degree of each vertex in this graph?

4

7

3

5

6

0

2

Graph Vocabulary

💬 Discuss: what is the in-degree and out-degree of each vertex in this graph?

4

7

3

5

6

0

2

Graphs in Code

#1: Adjacency Dictionary

Each element is vertex : [neighbors]

graph = {

____ : ____,

____ : ____,

____ : ____,

____ : ____,

}

2

0

3

1

#1: Adjacency Dictionary

Each element is vertex : [neighbors]

graph = {

0: [2],

1: [2, 3],

2: [0, 1, 3],

3: [1, 2]

}

2

0

3

1

#1: Adjacency Matrix

graph[i][j] is 1 if there is an edge between i and j.

graph = [

[_, _, _, _],

[_, _, _, _],

[_, _, _, _],

[_, _, _, _]

]

2

0

3

1

#1: Adjacency Matrix

graph[i][j] is 1 if there is an edge between i and j.

graph = [

[0, 0, 1, 0],

[0, 0, 1, 1],

[1, 1, 0, 1],

[0, 1, 1, 0]

]

2

0

3

1

Graph Vocabulary

💬 Discuss: write the graph as an adjacency dictionary.

​

Then, write the graph as an adjacency matrix.

4

7

3

5

6

0

2

Graph Vocabulary

💬 Discuss:

• How many vertices are in this graph?
• How many edges are in this graph?
• Name two vertices that are adjacent.
• What is the degree of each vertex in this graph?

4

3

1

0

2

👩‍💻 Let's Write Some Code!

What's Next?

What's Next?

• More graphs!
• A special type of graph called a tree.