CS 115 Lab 11 Setup and Practice

[Back to lab instructions]

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

Setup

1. If the machine was on when you started using it, reboot it to MacOS.
2. Follow these procedures to mount your blue home-directory on the local machine and create a PyCharm project (call it Lab11). You will use PyCharm in the next part, but, it is important that you set up your project now so that if you run into any issue, we can resolve them quickly.
3. Right-click or control-click to download these 2 files into your default Python directory (C:\Python34 on Windows or Documents on a Mac):

• cities.txt
• cities-small.txt

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 writeup.

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 writeup.

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 writeup.