QuickSort, HeapSort and ADTs

Go to:
> Material
> Lecture Recap

Material

• Slides: pre-class (w.o. solutions)
• Slides: with solutions & annotations

Lecture Recap

This week you have learned about three things:

Efficient Sorting and Trade-Offs

We finished sorting by covering Quicksort, which uses a clever partitioning scheme, and Heapsort, which introduces a new data structure (the heap) to sort efficiently in-place.

Tree-Based Data Structures

We introduced our first data structures. The goal is for you to gain intuition for tree-based structures and feel comfortable describing and reasoning about their properties.

Abstract Data Types (ADTs)

You learned the important concept of separating an interface (an ADT) from its implementation (a data structure). We analyzed the trade-offs involved for specific ADTs, starting with Lists.