COMPSCI 220 Programming Methodology

Exercise Assignment 04: Quicksort

Overview

Quicksort is a widely-used sorting algorithm that can be elegantly implemented in the functional style. In this assignment, you will take a functional approach to writing Quicksort, instead of the imperative approach you’ve seen in your previous classes.

Unlike previous exercise assignments, you must do this assignment entirely by hand. You should have brought pen and paper with you, as per the Piazza post. We will not be taking electronic submissions for this assignment. Additionally, you must hand in your implementation at the end of the discussion section. We will not accept late submissions.

Please write your name and student ID number on your submission.

NOTE: You are not allowed to use your laptop for this exercise activity. We want you to focus on thinking about the details of Quicksort and how you can implement it with functional programming.

Learning Goals

• To understand Quicksort from a functional perspective
• To work with functional programming offline
• To focus on thinking about a problem and how to solve it
• To practice programming with immutable lists

Part 1: The Quicksort Algorithm

The Quicksort algorithm is very simple. You should have seen it in previous classes, but here are the steps as a refresher.

For the list ls,

1. Choose a pivot value p from the list (p is removed from the list.)
2. Partition the list into two lists: less, the values less than or equal to p, and greater, the values greater than p.
3. Recursively sort less and greater. (Base case: Nil, the empty list.)
4. Recombine the sorted lists with the pivot: less ++ p ++ greater.

For this exercise, please write an implementation of the Quicksort algorithm using functional programming techniques.

• The head of the list will be chosen as the pivot, for simplicity.
• The implementation must be generic.
• It must be functional. Recursion, pattern matching, folds and maps – whatever you think is needed.

Because we want a generic implementation of Quicksort, we need a way to compare elements without knowing what type they are. Our Quicksort implementation will take two arguments: The list to sort, and a compare function:

def quicksort[A](list: List[A], comp: (A,A) => Int): List[A]

The compare function takes two values a and b of the same type and compares them. It returns a value x where:

• x < 0 if a < b
• x == 0 if a == b
• x > 0 if a > b

By checking if comp(a,b) is less than 0, equal to 0, or greater than 0, we can check if a is less than b, equal to b, or greater than b, respectively. We don’t care about the actual returned value, just the sign!

For example, this function compares two integers:

def compInt(a: Int, b: Int): Int = a - b

Convince yourself that compInt conforms to the expectations above.

You will not write compare functions. You need to understand how they work and think how you can use them in your implementation, but don’t spend time writing them.

Submission

Hand in your written solution at the end of discussion.