CS18 Bridge Assignment: Sorting Lists
Mergesort originally appeared in lab 8. We’ve duplicated that info here, so that we can keep all of the CS18 material in its own place. We’ve also added some clarifying text.
Below are descriptions of three common sorting algorithms: insertion sort, quicksort, and mergesort
You job is to implement them and predict their runtimes.
Insertion Sort
Insertion sort works by traversing an input list, taking each element in turn, and inserting it into the (sorted) output list. The sorted output gets larger one element at a time until the entire list has been sorted.
Here are 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
- Run
insertion-sort (recursively) on the rest of the list.
- Insert the current first element into the correct place in the now-sorted rest of the list.
Write this function using explicit recursion in Pyret (because CS18 will assume you’ve seen the recursive version).
Think about the running time – how many computations does this take in terms of the length of the input list in the worst case? What about in the best case? You can think about “computations” as the number of comparisons (> or <).
Quicksort
Quicksort tries to improve on the running time of insertion sort by limiting the number of comparisons that get made between elements. It does this by taking a single element (called the “pivot”), and splitting 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 (from a third-party website; see image URL for credit) showing how the algorithm works. This particular example grabs the last element of a list as the pivot. When working in Pyret, it’s easier for us to use the first element as the pivot. The core idea is the same, however.
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
- Choose the first element of the list to be 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.
Write this function in Pyret. You may use maps and filters, or explicit recursion, as you wish.
Quicksort running time, intuitively
The goal of quicksort is to do fewer comparison operations than insertion sort. Let’s think about that goal:
-
Is quicksort always faster than insertion sort? Remember, when comparing algorithms, we generally consider two algorithms with the same growth rate (linear, quadratic, etc) in the size of the input to have the same performance. So the question here is whether quicksort has a lower growth rate than insertion sort.
-
In thinking about your answer, write down concrete examples of lists that would yield worst and best case performance of quicksort. What performance would these same lists have in insertion sort?
Put your answers to these in a block comment
You’ll work out the worst-case running times more formally in the assignment on running times. For now, we just want to build your intuition.
Mergesort
In mergesort, you sort by splitting a list in half, sorting each half, then merging the two sorted lists together. By doing this, you skip comparing each element to every other element as you would do in insertion sort. When sorting the halves, you again split the lists in half, sort, and merge the results. 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.
Handin
Turn in a file sorting.arr with your code, and discussions of the running time questions in comment blocks. You don’t have to turn in diagrams you drew to understand the algorithms.
CS18 Bridge Assignment: Sorting Lists
Mergesort originally appeared in lab 8. We’ve duplicated that info here, so that we can keep all of the CS18 material in its own place. We’ve also added some clarifying text.
Below are descriptions of three common sorting algorithms: insertion sort, quicksort, and mergesort
You job is to implement them and predict their runtimes.
Insertion Sort
Insertion sort works by traversing an input list, taking each element in turn, and inserting it into the (sorted) output list. The sorted output gets larger one element at a time until the entire list has been sorted.
Here are the steps of the algorithm:
insertion-sort(recursively) on the rest of the list.Write this function using explicit recursion in Pyret (because CS18 will assume you’ve seen the recursive version).
Think about the running time – how many computations does this take in terms of the length of the input list in the worst case? What about in the best case? You can think about “computations” as the number of comparisons (> or <).
Quicksort
Quicksort tries to improve on the running time of insertion sort by limiting the number of comparisons that get made between elements. It does this by taking a single element (called the “pivot”), and splitting 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 (from a third-party website; see image URL for credit) showing how the algorithm works. This particular example grabs the last element of a list as the pivot. When working in Pyret, it’s easier for us to use the first element as the pivot. The core idea is the same, however.
Here’s a summary of the steps of the algorithm:
quicksort(recursively) on each of the new lists.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.
Write this function in Pyret. You may use maps and filters, or explicit recursion, as you wish.
Quicksort running time, intuitively
The goal of quicksort is to do fewer comparison operations than insertion sort. Let’s think about that goal:
Is quicksort always faster than insertion sort? Remember, when comparing algorithms, we generally consider two algorithms with the same growth rate (linear, quadratic, etc) in the size of the input to have the same performance. So the question here is whether quicksort has a lower growth rate than insertion sort.
In thinking about your answer, write down concrete examples of lists that would yield worst and best case performance of quicksort. What performance would these same lists have in insertion sort?
Put your answers to these in a block comment
You’ll work out the worst-case running times more formally in the assignment on running times. For now, we just want to build your intuition.
Mergesort
In mergesort, you sort by splitting a list in half, sorting each half, then merging the two sorted lists together. By doing this, you skip comparing each element to every other element as you would do in insertion sort. When sorting the halves, you again split the lists in half, sort, and merge the results. 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.
Handin
Turn in a file sorting.arr with your code, and discussions of the running time questions in comment blocks. You don’t have to turn in diagrams you drew to understand the algorithms.