Overview

You’ve learned about how sorting can be useful, but how do you actually sort a list of items such as numbers or strings? More importantly perhaps, how do you do so as quickly as possible? Today’s focus will be on a set of sorting algorithms that aren’t the quickest, but are pretty good.

Basic Learning Objectives

Before class, you should be able to:

  • Define what we mean by a sorted list
  • Explain the high-level idea of selection sort
  • Explain the high-level idea of insertion sort

Advanced Learning Objectives

After class, you should be able to:

  • Implement selection and insertion sort in code or on paper
  • Explain the time complexity of selection and insertion sort

Resources

You should read the following and complete the embedded checks:

Checks

Submit answers to the following to Moodle:

  • Suppose you have the following list of numbers to sort: [11, 7, 12, 14, 19, 1, 6, 18, 8, 20]. What will the partially sorted list look like after three complete passes of selection sort?
  • Suppose you have the following list of numbers to sort: [15, 5, 4, 18, 12, 19, 14, 10, 8, 20]. What will the partially sorted list look like after three complete passes of insertion sort?
  • What are the key differences between selection and insertion sort?