Week 10 - Searches and Sorts

Learning objectives

Upon finishing this week, you should be able to:

  • Write a binary search
  • Write various quadratic sort algorithms
  • Write MergeSort
  • Identify the efficiency of various search and sort algorithms

Suggested pacing

Day 1

Day 2

Day 3

Day 4

  • Final review
  • See the review guide in Canvas
If you have not already done so, schedule your final. See the discussion board for details.

Activity Outline

We only have briefly covered Big-O in this course. In CS260, we will dive into the rest of Ch 25. Until that point, don't worry about understanding all the arguments about the efficiency of various algorithms. You should know which category of efficiency each algorithm falls into and have a general idea of why, but you don't need to be able to reproduce the arguments for why that is the case.

Read Ch 26.1-26.5

These videos review the two approaches and their efficiency:



Quadratic Sorts

Read Ch 24.6-26.8 about insertion sort and selection sort.

This video reviews the algorithms and their efficiencies:


Merge Sort

Read Ch 24.9-26.12.

This video covers Mergesort. Coverage of the efficiency starts at ~7:00: