sorting.md

Sorting & Searching Study Guide

We advise you to study in the following order:

1. Begin by understanding the slides (ignore for now the Advanced Exercises that are at the end of the sorting slides.)

2. Solve the following tracing question:

   Fill out the following table with the exact number of operations: 
   swaps/shifts and data compares (DCs). 
   Assume the algorithm implementations covered in class where:
      •  Bubble Sort uses a "swapped" flag to stop when the array gets sorted.
      •  Selection Sort does not swap an element with itself.

      |----------------|----------------|----------------|-------------|
      |                | Selection Sort | Insertion Sort | Bubble Sort |
      |----------------|----------------|----------------|-------------|
      |  `1 2 3 4 5`   | Swaps =        | Shifts =       | Swaps =     |
      |                | DCs   =        | DCs    =       | DCs   =     |
      |----------------|----------------|----------------|-------------|
      |  `5 4 3 2 1`   | Swaps =        | Shifts =       | Swaps =     |
      |                | DCs   =        | DCs    =       | DCs   =     |
      |----------------|----------------|----------------|-------------|
      |  `5 1 2 3 4`   | Swaps =        | Shifts =       | Swaps =     |
      |                | DCs   =        | DCs    =       | DCs   =     |
      |----------------|----------------|----------------|-------------|
      |  `1 5 4 3 2`   | Swaps =        | Shifts =       | Swaps =     |
      |                | DCs   =        | DCs    =       | DCs   =     |
      |----------------|----------------|----------------|-------------|

3. Practice using (recent) previous exams:

   1. Midterm Exam - Fall 2021: Question 4 (solution)
   2. First Exam - Fall 2022: Question 2 (solution)
   3. First Exam - Spring 2022: Question 2 (solution)

4. Practice using the advanced exercises at the end of the sorting slides. Here is a video explaining the answers.

5. Practice using old previous exams