Remember, "the answer" is only half of it! Also, make sure everyone in your group can explain why.

We will use this Gradescope Online Assignment as our worksheet for in-class work. These problems are coded as being worth points for our simplicity, but will not impact your grade in the course.

# Question 2

## Q2.1

``````[1, 9] [0, 2] [5] [4] [7]
``````

## Q2.2

``````[0, 1, 2, 9] [5] [4] [7]
``````

## Q2.3

``````[0, 1, 2, 9] [4, 5] [7]
``````

## Q2.4

``````[0, 1, 2, 9] [4, 5, 7]
``````

## Q2.5

``````[0, 1, 2, 4, 5, 7, 9]
``````

# Question 3

## Q3.1

First = 1, Middle = 7, Last = 3. The median of these three numbers, 3, is selected as the pivot.

## Q3.2

Below is a trace of all the steps of partitioning, as described in the lecture videos.

``````**Input**
[1, 9, 5, 4, 7, 2, 8, 6, 3]

**Swap pivot to front**
[3, 9, 5, 4, 7, 2, 8, 6, 1]

**Start moving "fingers"**
[3, 9, 5, 4, 7, 2, 8, 6, 1]
**^**                    **^**
Low                  High

**Swap and move both "fingers" inward**
[3, 1, 5, 4, 7, 2, 8, 6, 9]
**^**              **^**
Low            High

**Keep moving high down since both values are larger than pivot**
[3, 1, 5, 4, 7, 2, 8, 6, 9]
**^**        **^**
Low      High

**Swap and move both "fingers" inward**
[3, 1, 2, 4, 7, 5, 8, 6, 9]
**^**  **^**
Low  High

**Keep moving high down since both values are larger than pivot (stop when they cross)**
[3, 1, 2, 4, 7, 5, 8, 6, 9]
**^**
Low  High

**Swap pivot back with end of low section**
[2, 1, 3, 4, 7, 5, 8, 6, 9]
``````