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)
  • Recursive algorithms, including but not limited to quicksort

👾 💬 Exam Note

You should be able ot do things like recognize quicksort, describe how it uses recursion, compare it to other sorting algorithms, discuss it Big O time and space complexity. You will not be expected to code or trace it.

Ensure you understand the answers to these questions:

• How does sorting a sorted v unsorted list affect Big O time and space efficiency?
• Is quicksort more efficient on a randomly-ordered list or a partially-sorted list?

[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] What is Quicksort? #

Python 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
• then, recursively call the function on the each section of the list

💻 In pylists_quicksort.py implement quick sort. You may check your answer with the solution.

def pylists_quicksort(alist):
    if len(alist) <= 1:
        return alist

    pivot = alist[0]

    left = []
    for x in alist[1:]:
        if x < pivot:
            left.append(x)

    right = []
    for x in alist[1:]:
        if x > pivot:
            right.append(x)

    return pylists_quicksort(left) + [pivot] + pylists_quicksort(right)

Lomuto Method #

The Lomuto Method uses in-place swapping and chooses the last item as the pivot. The pointers both start at the beginning of the list

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

Hoare Method #

The Hoare Method uses in-place swapping and chooses the first item as the pivot. One pointer starts at the beginning of the list, and the other at the end.

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

[2] Deliverables #

⚡✨ Once you complete the lab, be sure to complete these two steps:

📋 Update Syllabus Tracker: Go to your Syllabus Content Checklist in your Google Drive and update it accordingly.

💻 Push your work to Github

• git status
• git add -A
• git status
• git commit -m “describe your code here”
• git push
• remote