# Homework 7: Sorting

Due: 05/04 12:30pm

Name & Perm # (no partners allowed):

Reading: DS 13.1, also review DS 12.1, 2.6, 6.1

Please also read the handout at http://cs.ucsb.edu/~richert/cs32/misc/h07-handout.pdf

## 1.  (10 pts)

Briefly explain: What does it mean to say that an algorithm has quadratic worst-case run time?

## 2. 

Show the steps of bubble sort following the example of the solved problems on the handout for the algorithm and the format of your answer. Stop after the first pass with no swaps.

### 2.1. 5 pts

initial values 8 5 3 10 2
i = 4
i = 3
i = 2
i = 1

### 2.2. 5 pts

initial values 40 42 -3 10 0
i = 4
i = 3
i = 2
i = 1

## 3. 

Show the steps of insertion sort following the example of the solved problems on the handout for the algorithm and the format of your answer.

### 3.1. 5 pts

initial values 8 5 3 10 2
i = 0
i = 1
i = 2
i = 3
i = 4

### 3.2. 5 pts

initial values 40 42 -3 10 0
i = 0
i = 1
i = 2
i = 3
i = 4

## 4. 

Show the steps of selection sort following the example of the solved problems on the handout for the algorithm and the format of your answer. Show all rows even for passes that no swaps occur.

### 4.1. 5 pts

initial values 8 5 3 10 2
i = 4
i = 3
i = 2
i = 1

### 4.2. 5 pts

initial values 40 42 -3 10 0
i = 4
i = 3
i = 2
i = 1

Author: Instructor: Mehmet Emre

Created: CS 32 Spring '22

The material for this class is based on Prof. Richert Wang's material for CS 32