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.

Introduction

For this assignment, you will trace a program and write a few small programs. Code you write should still be submitted via handin21, but you can submit the trace of your program electronically or written on paper. If you choose to submit a written solution, it will be due at the start of class on Thursday. The focus of this assignment is for you to further practice sorting and to become more comfortable with recursion.

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

In the file traceSort.py, you will find an implementation of both selection sort and insertion sort, but a high level description of the insertion sort algorithm is included below.

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]

What to submit

In the file traceSort.py, you will find an implementation of both selection sort and insertion sort. Trace through all the function calls (four in total) for the two sorts and count the number of times the body of the inner loop in each sort executes. You should produce a table as follows for each sorting call, and also show the total number of times the inner loop executes over the entire algorithm.

i	# times through inner loop
0	?
1	?
...	?

Note that for the first list the values are in a random order, while the second list is almost in sorted order.

Briefly answer the following questions in your writeup.

Does the performance of selection sort depend on the original unsorted order of the list?
Does the performance of insertion sort depend on the original unsorted order of the list?
Does insertion sort take more or fewer steps than selection sort? Briefly explain your answer.

If you wish to submit your answers electronically, name your file sortAnswers.txt

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

What to submit