Week 2 - Sorting algorithms

Learning objectives

Upon finishing this learning module, you should be able to:

  • Implement Quicksort and Mergesort
  • Identify the efficiency and properties of common sorting algorithms
  • Reason about the efficiency of an array based list

Class Schedule

Monday

  • QuickSort

Tuesday

  • Debugging at Scale
  • Bucket And Radix Sort

Wednesday

  • ArrayList review

Thursday

  • List Nodes

Topics

Quicksort

There is another common partition algorithm that is less efficient than the one shown here and the book. I expect you to know how this one works, so if you use an alternate source, make sure you are learning the right algorithm.
  • Read Liang Ch19.5
  • Video Review:
  • Do Quicksort WS to practice partitioning.
  • Do Quicksort CPPLab

Bucket and Radix Sort

Debugging at scale

Watch this video with tips about debugging at scale:

ArrayLists

  • Refresh your memory about the efficiencies of Array based lists with these videos from CS162:
  • If you need a refresher on building an array based list, also watch this one
  • Do the ArrayList WS

Linked Lists & ListNodes

  • Do the ListNodes WS

Sorting Resources

Assignment 1

Keep chipping away at assignment 1. You should be ready to finish it up after the Day 2 material. Do the writeup as you go. If you run out of time at the end, it is better to have the writeup done and one part of the assignment not complete than to spend all your time on programming (and still maybe have a broken function) and not have any writeup.