CS21: Lab 9

For this assignment you should work on your own. No partners this week.

Run update21, if you haven't already, to create the cs21/labs/09 directory. Then cd into your cs21/labs/09 directory and create the python programs for lab 9 in this directory (handin21 looks for your lab 9 assignments in your cs21/labs/09 directory):

$ update21
$ cd cs21/labs/09
$ vim sort.py

Introduction

For this assignment, you will write a few small programs. The first program will implement insertion sort, while for the other programs you will write both iterative and recursive solutions to some problems. The focus of this assignment is for you to further practice sorting and to become more comfortable with recursion.

Insertion sort

Insertion sort is an iterative comparision based sorting method similar to selection sort. The algorithm loops over all items in a given input list, and repeatedly inserts the next item in the list in sorted order. The algorithm maintains the property that after i iterations of the loop, the first i elements in the list are in sorted order.

The top level description of insertion sort can be described as follows:

for each position i in the list A:
   insert A[i] in sorted order

To insert in sorted order a value val=A[i] initially in position i, start by walking backwards in the list from position i to find the first position j where A[j] < val (Note that if val < A[0], val should be the new first item in the list). While the item at position j < i is larger than val, move A[j] forward in the list by one position, thus making room for val. If the item in position j is the smaller than val, insert val at postion j+1.

A step by step execution of insertion sort is shown below.

Original List:
[14, 11, 13, 18, 19, 12, 16, 10, 17, 15]
inserting 14 from position 0 into position 0
[14, 11, 13, 18, 19, 12, 16, 10, 17, 15]
inserting 11 from position 1 into position 0
[11, 14, 13, 18, 19, 12, 16, 10, 17, 15]
inserting 13 from position 2 into position 1
[11, 13, 14, 18, 19, 12, 16, 10, 17, 15]
inserting 18 from position 3 into position 3
[11, 13, 14, 18, 19, 12, 16, 10, 17, 15]
inserting 19 from position 4 into position 4
[11, 13, 14, 18, 19, 12, 16, 10, 17, 15]
inserting 12 from position 5 into position 1
[11, 12, 13, 14, 18, 19, 16, 10, 17, 15]
inserting 16 from position 6 into position 4
[11, 12, 13, 14, 16, 18, 19, 10, 17, 15]
inserting 10 from position 7 into position 0
[10, 11, 12, 13, 14, 16, 18, 19, 17, 15]
inserting 17 from position 8 into position 6
[10, 11, 12, 13, 14, 16, 17, 18, 19, 15]
inserting 15 from position 9 into position 5
[10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

Note that after i steps, the first i items from the original list appear in sorted order at the beginning of the list. These sorted items are shown in orange. Note also how items move over one spot to make room for a newly inserted item. For example, when inserting 11, the 14 moves over one spot.

[14, 11, 13, 18, 19, 12, 16, 10, 17, 15]
inserting 11 from position 1 into position 0
[11, 14, 13, 18, 19, 12, 16, 10, 17, 15]

Or, when inserting 12, the sorted items 13, 14, 18, 19 all move over one spot to make room for 12.

[11, 13, 14, 18, 19, 12, 16, 10, 17, 15]
inserting 12 from position 5 into position 1
[11, 12, 13, 14, 18, 19, 16, 10, 17, 15]

Write a function insertionSort(ls) in the file sort.py that implements insertion sort as described above to sort the input list ls. Your code should modify the input list ls such that after the function finishes, the list ls is sorted. It should not return a new list. This behavior is the same as the selection sort algorithm described in class. Also write a small main program to test your function.

Recursion

Consider the following functions:

def reverse(ls): 
"""
Given a list ls, returns a new list containing
the elements of ls in reverse order
"""

def sumrange(n):
"""
 Return the sum of the first n integers
 1+2+3+4+...+n
"""

Open a file iterative.py and implement iterative solutions to these functions. Include a small main function to test your solution. You cannot use the builtin reverse method for lists to implement this solution (the reverse method modifies the list in place anyways, and your solution must create a new list)

Next, open the file recursive.py and implement recursive solutions to these functions. You can use the same main function from iterative.py to test your recursive solution. Some example output is shown below:

ls= [1, 2, 7, 8, 9, 4, 0, 3, 6, 5]
reverse(ls)= [5, 6, 3, 0, 4, 9, 8, 7, 2, 1]
sumrange(3) = 6
sumrange(10) = 55

Submit

Once you are satisfied with your programs, hand them in by typing handin21 in a terminal window.

CS21 Lab 9: Sorting and recursion