In Python

the comments in the attached Python file for details of what you are to do. Do not rename functions, parameters, the filename, etc. If you do, then my test cases won't run, and you will lose substantial points.

Grading: 30% insertion_sort, 35% heap_sort (including its helper functions), 10% is_sorted, 10% random_list, 15% code demonstrating that your sorts work.

First run your module via F5 in IDLE or you can find it in the run menu of IDLE. Most syntax errors will be identified there.

___________________________________________________________________________________________________

# Student name: .

#

# Assignment Instructions: (DO NOT DELETE... you will lose points).

#

# Implement the insertion sort and heap sort algorithms in the

# functions that follow. Also implement the is_sorted function

# to check if a list is sorted, and the random_list function to

# generate a list of random integers. When you are working on

# implementing heap sort, in addition to the heap_sort function,

# you will likely want to begin by implementing all of its helper

# functions, which include: _build_max_heap, _max_heapify, _left,

# and _right. Carefully read the comments I have throughout, as I

# made a few minor adjustments relative to the textbook pseudocode.

# After implementing all of the functions, write some code in the

# if block at the very bottom of this file to test that your two

# sorts, your is_sorted, and your random_list works.

#

# DO NOT delete the docstrings (the multiline strings immediately after

# the signature lines of the functions). You will lose points if you

# delete the docstrings. You may delete comments that I inserted to give

# you hints.

#

# Don't change the names of any of the functions or the names of the

# parameters.

# IMPORTANT: DO NOT have any print statements in the functions in this

# Python file (e.g., in the is_sorted, random_list, insertion_sort,

# heap_sort, and heap_sort's various helper functions).

# In general, you want to separate output from the computation. You'll

# be outputting results (e.g., using print) in the if block at the very

# bottom of this module.

def is_sorted(A) :

"""Returns True if A is sorted in non-decreasing order,

and returns False if A is not sorted.

Keyword arguments:

A - a Python list.

"""

pass # Here temporarily (Delete this pass and put your code here)

## Hints for implementing issorted:

## Hint 1: DO NOT use the built-in function sorted in this function.

## You will get 0 points for the issorted

## function if you call Python's sorted function.

## Hint 2: If A is sorted then A[0] <= A[1] <= A[2] <= ....

## So, you can write a loop whose body does one

## comparison of adjacent elements, returning False if there is a violation

## within the loop. If you manage to get through the loop without returning,

## then the list must be sorted, so return True.

def random_list(length, low=0, high=100) :

"""Generates and returns a Python list of random integer values.

The integers in the list are generated uniformly at random from

the interval [low, high], inclusive of both end points.

Keyword arguments:

length - the length of the list.

low - the lower bound for the random integers.

high - the upper bound for the random integers.

"""

pass # here temporarily (Delete this pass and put your code here)

## Hint:

## There are useful functions there for generating random numbers.

##

The random.sample

## function doesn't allow repeat selection.

##

##dir(random) will just list the function names.

##

## Another hint: You can use a Python list comprehension to

## generate the list.

##

## Yet another hint: If you follow the above hints, it is possible

## to implement this function with a single line of code,

## a return statement with a list comprehension.

##

## One more hint: Recall that Python allows default values for

## parameters. For example, the low=0 means that if the programmer

## doesn't pass anything for the low parameter, then low will be 0;

## but otherwise low will be whatever is passed for it.

def insertion_sort(A) :

"""Implementation of the insertion sort algorithm

as specified on page 19 of the textbook.

But keep in mind that the textbook pseudocode uses 1

as the first index into an array, but Python list

indexes begin at 0, so you will need to think how to

adjust for that.

Keyword arguments:

A - a Python list.

"""

pass # Here temporarily. Remove and replace with your code.

def heap_sort(A) :

"""Implementation of the heapsort algorithm

as specified on page 170 of the textbook.

Keyword arguments:

A - a Python list.

"""

# I wrote the statement that corresponds to line 1

# of the pseudocode from page 170 for you, mainly

# because I'm altering how the heap_size is maintained

# compared with how it is maintained in the textbook.

# Multiple helper functions need it. The textbook assumes

# that it is a property of A, but we cannot add fields to

# a Python list. So _build_max_heap will initialize it

# and return it, and then we'll pass it around as a parameter

# wherever it is needed.

heap_size = _build_max_heap(A)

# Implement the rest of the algorithm as specified on page 170

# here. You probably want to work on the helper functions first

# though (see below).

# Hint: When you call _max_heapify, in addition to the parameters

# indicated in textbook pseudocode, you will need to pass the

# heap_size as well because of the minor adjustments I made.

def _build_max_heap(A) :

"""Helper function for heap_sort.

This should be mostly as described on page 167.

The one modification is that this function should

return the heap_size. The textbook version relies

on A having it as a property, but we cannot do that

here because A is a Python list and we cannot add

properties to it. But other helper functions need

access to it, so we will return it here, and then

pass around as a parameter as needed.

But keep in mind Python list.

indexes begin at 0, so you will need to think how to

adjust for that.

Keyword arguments:

A - The list we are sorting.

"""

# I wrote this statement for you. This is the

# equivalent of line 1 of the pseudocode of page 167.

heap_size = len(A)

# YOUR CODE HERE: Implement the rest of _build_max_heap here.

# Hint 1: When you call _max_heapify, in addition to the parameters

# indicated in textbook pseudocode, you will need to pass the

# heap_size as well because of the minor adjustments I made.

#

# Hint 2: The loop uses floor of the result of a division..

# Instead, using Python's integer division operator // will accomplish

# that. Although make sure you first consider the effects on that

# statement of 0-based indexes rather than the textbook's assumption

# of 1-based indexes.

# Return the heap_size (after implementing rest of function

# above). See docstring for explanation of why we are

# returning this here.

return heap_size

def _left(i) :

"""Returns the index of the left child of index i.

But keep in mind that the textbook pseudocode uses 1

as the first index into an array, but Python list

indexes begin at 0, so you will need to think how to

adjust for that.

Keyword arguments:

i - An index into the heap.

"""

pass # Replace this pass statement with the return statement that you need.

def _right(i) :

"""Returns the index of the right child of index i.

But keep in mind that the textbook pseudocode uses 1

as the first index into an array, but Python list

indexes begin at 0, so you will need to think how to

adjust for that.

Keyword arguments:

i - An index into the heap.

"""

pass # Replace this pass statement with the return statement that you need.

def _max_heapify(A, i, heap_size) :

"""This is the helper function described with pseudocode

on page 165 of the textbook. It is a little different than

the textbook version. Specificially, it has a parameter for

the heap_size.

But keep in mind that the textbook pseudocode uses 1

as the first index into an array, but Python list

indexes begin at 0, so you will need to think how to

adjust for that.

Keyword arguments:

A - The list to sort.

i - The index.

heap_size - The heap_size as used on page 165, but passed as

a parameter.

"""

# Remove this pass statement and replace with your code.

# The pass is here temporarily so that this is valid syntax.

pass

# Hint: When you recursively call _max_heapify, in addition to

# the parameters indicated in textbook pseudocode, you will need

# to pass the heap_size as well.

if __name__ == "__main__" :

## Indented within this if block, do the following:

## 1) Write a few lines of code to demonstrate that your

## is_sorted works correctly (i.e., that it returns True

## if given a list that is sorted, and False otherwise).

## 2) Write a few lines of code to demonstrate that insertion_sort

## correctly sorts a list (your random_list function will be useful

## here). Output (i.e., with print statements) the contents

## of the list before sorting, and then again after sorting).

## 3) Repeat 2 to demonstrate that your heap_sort sorts correctly.

pass # Here temporarily (replace with your code)