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.
[1, 9] [0, 2] [5] [4] [7]
[0, 1, 2, 9] [5] [4] [7]
[0, 1, 2, 9] [4, 5] [7]
[0, 1, 2, 9] [4, 5, 7]
[0, 1, 2, 4, 5, 7, 9]
First = 1, Middle = 7, Last = 3. The median of these three numbers, 3, is selected as the pivot.
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]