Overview

Mergesort is pretty good, but with some small tweaks, it can get even better (on average!). It’s time to think a bit more about this seemingly simple problem by examining one of the fastest sorting algorithms: quicksort.

Basic Learning Objectives

Before class, you should be able to:

  • Explain the high-level idea of quicksort
  • Define the terms pivot value and split point
  • Explain why quicksort is typically faster than other sorting algorithms

Advanced Learning Objectives

After class, you should be able to:

  • Implement your own median of three algorithm
  • Analyze how different factors of a list impact quicksort’s performance
  • Explain the idea behind the Big-O of quicksort

Reading

You should read the following:

Checks

Submit an answer to the following on Moodle.

| 46 | 9 | 22 | 5 | 15 | 1 | 96 | 34
  1. Draw out the steps in the quicksort algorithm to sort the list above. You should clearly show which item is the pivot and where swaps happen. Feel free to draw out your answers, take a picture or screenshot, and upload that. Aim to follow a similar structure to figure 5.11.2 in the reading.
  2. Look back to your answer for the mergesort check. What are the main differences in the highlevel sorting of quicksort and mergesort?