Sorting

Github Classroom

You can clone the starter files for this lab at this GitHub Classroom link. Be sure to open the assignment in VSCode and setup up your virtual environment following these instructions.

Introduction

You are helping implement Courses at Brown! You are given a list of search results, and your job is to sort them by name lexicographically!

Each of the search results represents a course offering. Each offering is associated with the course subject, course code, and total enrollment in course-data.json.

elements = [
    {"code": {"subject": "MCM", "number": "1204K"}, "enrollment": 40},
    {"code": {"subject": "TAPS", "number": "1281W"}, "enrollment": 23},
    {"code": {"subject": "ENGN", "number": "2172"}, "enrollment": 12},
    {"code": {"subject": "ENGN", "number": "0032"}, "enrollment": 100}
]

Since we’ll want to sort each object in lexicographic order based on their course code, we need to transform our input data to extract the course code. The built-in Python sort and sorted functions take in an optional function key. The key function acts as a transform function for elements of the input list into the elements used for comparison-based sorting. For example:

arr = [{"a": 3}, {"a": 1}, {"a": 2}]
sorted_arr = sorted(arr, key=lambda d: d["a"])
print(sorted_arr) # [{"a": 1}, {"a": 2}, {"a": 3}]

The registrar has kindly provided a key function to extract the course code from a course!

def key(course: Course) -> str:
    '''This function is already defined in the stencil code.'''
    # in Python, the builtin < will compare strings in lexicographic order
    return course1['code']['subject'] + course1['code']['number']

Sorting with respect to this key function gives:

elements = [
    {"code": {"subject": "ENGN", "number": "0032"}, "enrollment": 100},
    {"code": {"subject": "ENGN", "number": "2172"}, "enrollment": 12},
    {"code": {"subject": "MCM", "number": "1204K"}, "enrollment": 40},
    {"code": {"subject": "TAPS", "number": "1281W"}, "enrollment": 23}
]

Quicksort

Quicksort is a fast, general purpose, comparison sorting algorithm. Consider the following high level pseudocode for quicksort:

function quicksort(lst):
    1. Check whether the input has fewer than two elements. 
        These lists are returned unmodified, since they are already sorted.
    2. Select a pivot element p. 
        (The simplest choice is to choose the first element.)
    3. Partition the list into two lists: elements less than p, 
        and elements greater than or equal to p (excluding p).
    4. Recursively sort the two partitions.
    5. Return the sorted concatenation of the sorted partitions and p.

Random Pivot Quicksort

To improve the performance of quicksort on certain datasets, we can change the way that we choose the pivot. One of these ways is to select a random pivot element from the list, instead of always choosing the first element.

Small Sort Quicksort

One possible optimization to quicksort is to use a different sorting algorithm when the input is small. The idea is that even though the asymptotic runtime of an algorithm may be worse than quicksort, it may be faster for small inputs.

Semi-In Place Quicksort

One real problem with the naive quicksort implementation is that in order to construct sub-problems and recurse, we need to allocate new lists for elements that are left and right of the pivot.

In practice, we want to avoid this, because memory allocation is costly. One way to get around this is to use only a single auxiliary array to store temporary elements, and reuse this throughout our recursive calls.

Consider the following helper pseudocode for semi-in-place quicksort that takes an input array and also an auxiliary array and sorts the section $[lo, hi)$ in the input array:

function semi_in_place_helper(lo, hi, input, aux):
    1. If the range is a single element or less, do nothing.
    2. Select the first input element as the pivot p. 
    3. From left to right in aux:
        a. Place all elements less than p.
        b. Place the pivot p.
        c. Place all elements greater than or equal to p.
    6. Recuse on the upper and lower partitions of aux, 
        this time passing in the input array as the aux array.
    7. Copy the sorted aux array back into the input array.

Notice here that in the recursive calls, the input for one becomes the aux for the next, so we are only using these two arrays.

Just for Fun!

(Optional) Fully In-Place Quicksort

It is possible to implement quicksort without using any auxiliary arrays at all. We’ll call this fully in-place quicksort.

The idea is that we can remove the external memory dependency by using a portion of the input array as the auxiliary array. A basic pseudocode for the algorithm is given below:

function quicksort_in_place(input, lo, hi):
    1. If the range is a single element or less, do nothing.
    2. Select element hi - 1 as the pivot p.
    3. Sweep the range [lo, hi), and swap elements with
        keys less than the pivot key to the indices starting with lo and
        moving to the right as you swap elements.
    4. Recurse on the upper and lower partitions of the array.