Skip to content

Latest commit

 

History

History
49 lines (42 loc) · 3.69 KB

sorting.md

File metadata and controls

49 lines (42 loc) · 3.69 KB
Raw

Sorting & Searching Study Guide

We advise you to study in the following order:

  1. Begin by understanding everything in 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 in the slides, 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   =     |
      |----------------|----------------|----------------|-------------|

  1. Practice using the worksheets:

  2. Practice using the advanced exercises at the end of the sorting slides (most of these exercises are already in the worksheets). Here is a video explaining the answers.

  3. Check out how (recent) previous exams look like (most of the questions are already in the worksheets):

    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. First Exam - Spring 2023: Question 2 (+Question 4) (solution)

  4. If you are still looking for more questions, you can look at old previous exams