CS 115 Pre-Lab 11 Instructions

Deadline: Tu 4/14/2015 at 7 AM

Refer to the Week 13 reading or other resources as necessary to complete this assignment.

Part 1: The problem of sorting

In this lab, we explore different ways of taking the elements of a list and putting them in ascending order. That is, L[0] <= L[1] will be True, as will L[1] <= L[2], etc.

For numbers, this means that the smaller numbers will be at the beginning of the list. For strings, the list will be alphabetically sorted from A-Z as long as we are never comparing uppercase to lowercase letters. Note that the techniques we use can be easily modified to support descending order (where L[0] >= L[1], etc.).

Answer Question 1 in your pre-lab.

Part 2: Selection sort

Selection sort is an algorithm for sorting lists. It works by making multiple passes over the list. In each pass, it does two things:

• Finds the index of the minimum element in the unsorted portion of list.
• Swaps that element into its correct position.

For example, consider the list

['E', 'G', 'A', 'C', 'D']

In the first pass through the list, selection sort would identify position 2 as the index of the minimum element (since 'A' is the minimum element). Then, it would swap 'A' with the current first element:

['A', G', 'E', 'C', 'D']

In the next pass, we would ignore 'A', since we know it's in position already. The index of the minimum element in the remainder of the list is 3 (the position of 'C'). Then we would swap 'C' into place:

['A', 'C', 'E', 'G', 'D']

and so on. Answer Questions 2 and 3 in your pre-lab.

Part 3: Merge sort

Merge sort is a more efficient, although more complicated, sorting algorithm. We will be doing a bottom-up merge sort, which works as follows:

• Start by sorting pairs of adjacent elements. After this step, our list will consist of a bunch of 2-element sorted sub-lists.
• Merge pairs of adjacent 2-element sorted sublists. Now we will have a bunch of adjacent 4-element sorted sublists.
• Keep doubling the size of the sublists to be merged until the entire list is in sorted order.

For the list ['B', 'F', 'H', 'A', 'E', 'G', 'D', 'C'], this algorithm will work as follows:

1. Sort pairs of elements. We would look at 'B' and 'F' (which are already in order); 'H' and 'A' (which are not); 'E' and 'G' (which are); and 'D' and 'C' (which are not). After we put each of these 4 pairs in order, we have the list
   ['B', 'F', A', 'H', 'E', 'G', 'C', 'D']
2. Merge pairs of two-element sub-lists. This is a relatively fast operation since each two-element list is guaranteed to be in order thanks to the previous step. So we merge ['B', 'F'] with ['A', H'] and ['E', 'G'] with ['C', 'D']. This gives us ['A', 'B', 'F', 'H', 'C', 'D', 'E', 'G']
3. Merge the 4-element sublists ['A', 'B', 'F', 'H'] and ['C', 'D', 'E', 'G'], which will again be fast since each sublist is sorted. This gives us the final list ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'].

Answer Question 4 in your pre-lab.

Part 4: Submit the pre-lab (due Tu at 7 AM)

Review your answers, and then click the Next button at the bottom of the Moodle quiz. Once you do that, you should see something similar to this:

Click the Submit all and finish button. You MUST do this so that your pre-lab can be graded! Once you have submitted your quiz, you should see something similar to this at the top of your Moodle window. The important part is that the State shows up as Finished.