In Python IDLE

1.

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)

2.

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)

3.

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.

4.

def heap_sort(A) : """Implementation of the heapsort algorithm as specified on page 170 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 both in this function and its helpers.

Keyword arguments: A - a Python list. """

5.

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 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 we are sorting. """

6.

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.

7.

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.

8.

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

9.

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)