CS200 Bridge Assignment 1: Sorting Lists

Submit to: The "Bridge 1: Sorting (2025+)" assignment on the 111 -> 200 Gradescope.

Sorting collections of data is a common task in computing. Most programming languages provide built-in operators for sorting. As a programmer, you need to know how to use these functions. As a computer scientist, however, you should understand how these functions work under the hood.

There are multiple ways to sort a list. Here, we will look at three different methods. In general, a method of computing the answer to a specific problem is called an algorithm.

Below are descriptions of three common sorting algorithms: insertion sort, quicksort, and mergesort. You will implement each one of these algorithms. You may use any of the lists module functions (filter, etc) in your code that you'd like, EXCEPT for the sort function.

In each case, the goal is to sort a list of numbers into ascending (increasing) order.

Insertion Sort

Insertion sort follows the list template that we have discussed in class. Specifically, insertion-sort starts from the following code:

fun insertion-sort(lst :: List<Number>) -> List<Number>:
  cases (List) lst:
    | empty => ...
    | link(n, rst) => ... insertion-sort(rst)
  end
end

Task: Start with this template and use it to write a function that sorts a list into increasing order.

Note: Every year when we give this task, we get a bunch of solutions in which students write a program that sorts, but doesn't make use of the structure we have given you. For example, a function that searches for the smallest element in the rest and puts it on the front is NOT following the given structure. Your solution should be calling insertion sort directly on the rst (not some other list) as shown here.

Hints and guidance:

• Work with examples. Start with a list. We've already told you that your code has to run the function on the rest of the list. Remembering that recursion is an "exercise in trust," if you write insertion-sort correctly, insertion-sort(rst) will result in a sorted list. What do you need to do with fst so that the overall result is also a sorted list?
• It's fine to write additional helper functions here.
• It's easy to overthink this, especially if you are focusing on how sorting could be done in general. There's pretty much only one way to sort a list if you start from the code we've given, so focus on what that code does, not how you think sorting should occur.

Quicksort

Insertion sort is somewhat brute force: each element gets inserted into the partly sorted list one at a time. Quicksort tries to be more clever. It takes a single element (called the "pivot"), and splits the list into two sublists: one of the items that are smaller (or equal to) the pivot, and one of the items that are larger than the pivot. The algorithm sorts each of these sublists, then appends the sorted lists with the pivot in the middle.

Here's an image showing how the algorithm works. The pivot is the first element in each list (shaded in blue). The purple arrows show the lists of smaller and larger elements that get used in recursive calls. The green line shows how the elements end up ordered in the final list.

Here's a summary of the steps of the algorithm:

• If the input list is empty: return the empty list
• If the input list contains a single element: return a list containing just that element
• Otherwise: the first element of the list becomes the "pivot."
  • Split all of the elements in the rest of the list into two separate lists: one containing all elements less than the pivot, and one containing all elements greater than the pivot.
  • Run quicksort (recursively) on each of the new lists.
  • Join elements into a new list in the following order: first the one with elements less than the pivot, then the pivot, then the one with elements greater than the pivot.

If the algorithm isn't yet clear to you, work out a couple of examples on paper, along the lines of the diagram we provided above, but this time using the first element of the list as the pivot. Don't try to write the code until the examples make sense to you. You do not have to turn in the examples.

Task: Write this function with header quicksort(lst :: List<Number>) -> List<Number>. You may use maps and filters, or explicit recursion, as you wish.

Mergesort

Like Quicksort, Mergesort divides the list and sorts the pieces, but it uses a different splitting strategy. In mergesort, you sort by splitting a list in half by position, sorting each half, then merging the two sorted lists together. When the lists you have to sort have at most one element, there is no need to split and merge – you can just return the lists.

Here's a diagram showing an example (this is from the wikipedia page on mergesort).

Here's a summary of the steps of the algorithm:

• If the list has at most one element, return it (it is already sorted)
• If the list has more than one element, divide it in half, sort each half (using mergesort), then merge the two halves into a single sorted list. Return the merged list.
  • If the list has odd length, the extra element can be in either half.

The example uses arrays, but you will do this with lists and recursion in Pyret.

Task: Write this function with header mergesort(lst :: List<Number>) -> List<Number>.

Customizeable sort

All three of the sorting algorithms were written to sort numbers into increasing order. But we can do other kinds of sorting too: numbers in decreasing order, strings in alphabetical order, words in order of decreasing length, and so on. Sorting is a general-purpose activity: shouldn't we be able to write a sort that handles any of these sorting tasks with a common core implementation?

Task: Pick any ONE of your three sorting implementations and adapt it so it can sort a list with any type of element according to any criterion that the user of your code chooses. In particular, you should end up with:

fun sort-general(lst :: List, ???) -> List:
  ...
end

where any additional parameters needed to capture the criterion go in place of ??? (the list to sort should be the first parameter, you decide the rest).

You only need to provide three examples in your where block. Each one needs to capture a different list-type/criterion combination.

Hints and details:

• If you aren't sure how to proceed, copy your chosen algorithm and adapt it to sort another concrete list type (like list of String) on a concrete criterion (like alphabetical order)
• You should not use String/Boolean as a criterion for sorting (i.e. don't simply have an if-expression that switches between ascending/descending, or numerical/string sorting but repeats the same code. If you find yourself copy-pasting code multiple times to implement sort-general, this is not what we're looking for. It might help to look back at summary-generator for project 1, and the related lecture on functions as inputs, to think about how to customize a computation)

Reflection

In a block comment, write a few sentences about what you've learned from these bridge problems. Also mention any questions you have (if any) based on these exercises.

Handin

Turn in a file sorting-code.arr with your code. You don't have to turn in diagrams you drew to understand the algorithms. Make sure you submit this to the the 111 -> 200 Gradescope, not the 111 Gradescope for this semester.

Information about the Autograder

After you submit your work, Gradescope will run our autograder tests and display the results. It is your responsibility to make sure that all nine autograder tests pass.

• If you get an error message saying the autograder failed to run, check to make sure that your code file is named sorting-code.arr and that the function names and inputs are exactly as asked for in the handout. This error can also happen if your code has erroneous recursion logic and runs on an infinite loop on one of our test inputs (then, the autograder runs out of memory and cannot give back results). Writing a thorough set of tests can help you diagnose and resolve this issue.
• If you are failing some tests, go back and write some tests of your own and reason through them in your code. Part of the transition from 111 to 200 is getting more practice reasoning about what a comprehensive set of tests looks like. What kind of input lists should you try to make sure that your sorting algorithms are working correctly? If your code is failing the autograder, the first hint we'll give you is to think about writing more tests.

The autograder runs our tests on your insertion sort, mergesort, and quicksort implementations. Getting a full autograder score does not guarantee that you passed the assignment – Milda will manually grade your sort-general and look over your code to make sure that the sorting algorithms were implemented as described in the handout.