Week 2 - Sorting algorithms

Learning objectives

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

Implement common sorting algorithms including Insertion, Selection, Merge, and Quick Sort
Identify the efficiency and properties of common sorting algorithms

Class Schedule

Day 1

QuickSort
Do the Quicksort Worksheet and check against the key

Todo:

Do the Quicksort Exercise set in the book

Day 2

Bucket Sort
Do the Bucket Sort Worksheet and check against the key

Todo:

You are now ready for all parts of assignment 1. Other than reading, finishing it should be your main out of class task.

Day 3

Debugging at Scale
Array lists
Do the Array List Worksheet and check against the key

Day 4

Linked lists
Do the Linked List Worksheet and check against the key

Recommended Schedule

Day 1

QuickSort
Do the Quicksort Worksheet and check against the key
Do the Quicksort Exercise set in the book

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 not have a writeup.

The writeup should be done in the Readme.md file in your repository. The assignment has a link to this markdown sample - https://github.com/ChemeketaCS/markdown-sample - that you can use as a template for formatting your writeup.

This video shows how to work with markdown and preview your edits in VSCode:

Important Video

Quicksort

Read Ch 26.13-26.15. You might want to also skip ahead and read 26.17 at this point.

This video reviews partitioning, quicksort, and standard sorts:

There is another common partition algorithm that is less efficient than the one covered in the book. I expect you to know how the partition covered in class. So if you use an alternate source, make sure you learn the right algorithm!

Bucket Sort

Read Ch26.16 (and 26.17 if you have not already read it).

This video reviews bucket sort and gives some implementation insight:

And this one discusses radix sort. It goes into more detail than the book, and you are not responsible for all of it. You should know at a high level how radix sort works (successive bucketing on digits), and that it is a special purpose tool, not a general purpose sorting algorithm.

Debugging at Scale

Watch this video with tips about debugging at scale:

Important Video

ArrayLists

Reach Ch 25.10. Review 23.8-23.14 if you need a refresher on the basics of array lists.

This video discusses array lists and their efficiency:

This video demonstrates timing some operations in array lists and using them to verify our understanding of the Big O of inserting at various places.

Important Video

Linked Lists Intro

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.

Read Ch 27.1-27.2

This video reviews the concept of list nodes and how to use them:

This video shows a debugger level view of what is actually happening in memory:

Important Video