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

  • Array lists

Thursday

  • Linked lists

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

Bucket and Radix Sort are special purpose tools. A bucket sort does a partial sort where different groups of items are put into order (all Freshmen before Sophomores, Sophomores before Juniors, etc...) but the items within each group are not sorted (the Freshmen all stay in their original order).

This video explains it:

  • Ch 19.7 explains how a Radix Sort works. By doing a series of Bucket Sorts on different digits of values, you can end up doing a complete sort. You will not need to actually implement a radix sort, so don't worry about anything but picking up the basic idea.
  • Do BucketSort WS
  • Radix Sort Demo

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

Arrays are one of the main building blocks for building data structures in memory; the other main tool we have is the pointer. We can use pointers to connect structures in memory to form lists without using arrays. This videos introduce the basic ideas of how we will do this.

  • 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.