Lesson 2.3: Insertion Sort
Class Meeting:
| Section | Slides | Annotated Slides | Video |
| 12–1PM | 2.3-insertion-sort-203-1221.pdf Download 2.3-insertion-sort-203-1221.pdf | PDF Download PDF |
See Zoom Cloud Recordings |
| 1–2PM | 2.3-insertion-sort-1pm-2.pdf
Download 2.3-insertion-sort-1pm-2.pdf (corrected) |
2.3-insertion-sort-1pm-annotated.pdf Download 2.3-insertion-sort-1pm-annotated.pdf |
See Zoom Cloud Recordings |
| 4–5PM | 2.3-insertion-sort-4pm-2.pdf Download 2.3-insertion-sort-4pm-2.pdf | 2.3-insertion-sort-4pm-annotated.pdf Download 2.3-insertion-sort-4pm-annotated.pdf |
See Zoom Cloud Recordings |
Readings:
- Carrano & Henry : 11.1
- Epp : Chapter 11.2 - 11.3
- Zych C++ construct.pdf
- Zych C++ parameters.pdf
Summary:
In this lesson we make running time and correctness inferences for a more complex function, and then use that function to design a new sorting algorithm--Insertion Sort.
Learning Outcomes:
Upon completion off this lesson, students will be able to:
- make running time inferences for a new example function
- prove correctness in a non-standard context
- design a new sorting algorithm -- Insertion Sort
- argue running time and correctness for Insertion Sort