Quicksort #

This lab introduces the recursive sorting algorithm: Quicksort.

Syllabus Topics [HL] #

• B2.4.4 Explain the fundamental concept of recursion and its applications in programming. (HL only)

[0] Set up #

💻 Go into your unit folder and clone your repo. Be sure to replace yourGithubUsername with your actual username.

cd ~/desktop/dpcs/unit02_data_structures
git clone https://github.com/isf-dp-cs/lab_quicksort_yourGithubUsername

cd lab_quicksort_yourGithubUsername

💻 Enter the Poetry Shell to start the lab. As a reminder, we will run this command at the start of each lab, but only when we are inside a lab folder.

poetry shell

👾 💬 Exiting the poetry shell

When you want to exit the shell, you can type exit or ^D

[1] Quicksort Algorithm #

What is Quicksort? #

The idea of quicksort is simple enough. But how do we code it?

We’re going to explore 3 different ways to code quicksort, each with their own pros and cons.

Exam note: Based on the syllabus, you need to be able to do things like recognize quicksort, compare it to other sorting algorithms, discuss its efficiency, etc., but probably will not be expected to code or trace it.

Extra Lists Method #

This method is probably the easiest one to understand. We’re going to create two new lists:

• one list for items smaller than our pivot
• one list for items bigger than our pivot

To keep the code as short as possible, the example uses list comprehension. This is a python trick to make coding easier. It’s not necessary, but it is convenient.

Let’s say we have a list of fruits, and we want a new list with only fruits containing "a".

fruits = ["apple", "banana", "cherry", "kiwi", "mango"]

List comprehension shortens this code:

newlist = []
for x in fruits:
  if "a" in x:
    newlist.append(x)

into this one line:

newlist = [x for x in fruits if "a" in x]

💻 In list_comprehension_quicksort.py, add comments to annotate the quicksort code`.

Lomuto Method #

💻 In lomuto_quicksort.py, add comments to annotate the quicksort code`.

Hoare Method #

💻 In hoare_quicksort.py, add comments to annotate the quicksort code.

[2] Considering Efficiency #

Consider the following questions:

• How do these approaches compare when it comes to space complexity?
• How do these approaches compare when it comes to number of swaps?
• Is quicksort more efficient on a randomly-ordered list or a partially-sorted list?
• What is the Big O time efficiency of quicksort?