In this lab, we will explore sorting algorithms and perform a practical analysis of algorithm runtimes. In lecture, we have introduced algorithm - or asymptotic - analysis. In theoretical analysis, we care about the behavior of our algorithms out at the asymptotes. Or in other words, as the problem sizes get larger and larger, what functions can we use to bound algorithmic runtime? Does an algorithm's runtime grow at a linear rate to the problem size? Or is it logarithmic? Or Quadratic?

From the theoretical perspective, in our discussion of runtime, we care about the number of operations required for algorithms to complete. This allows us to separate the "runtime" of an algorithm from any individual computer on which it is run. Theoretically, we can analyze the runtime of the Merge Sort algorithm irrespective of any specific hardware.

Practically however, we do care about the actual time it takes for algorithms and programs to complete. In this lab, you will perform a runtime analysis to measure the actual time it takes for sorting algorithms selection sort and merge sort to complete for lists of increasing size. Since, on an individual computer, runtime is a good proxy for an algorithm's Big-O behavior, you will illustrate the runtime behaviors of these two algorithms.

This lab is broken into two parts:

• ZyBooks Coding Portion
• Canvas Runtime Analysis

Once you complete the coding portion for this lab, you will use it to perform a runtime analysis of both Selection Sort and Merge Sort which you will submit through canvas.

Sort Verification

We will start by writing functions to determine whether lists or files contain sorted data.

A) Warm-up

Write a program that checks whether a list of numbers is sorted in increasing order and prints True if the list is sorted in increasing order, and False otherwise. Test your program for several lists.

B) Is Sorted Function

Refactor your program as a function is-sorted(lst) that takes as input a list of numbers, and returns True if the list is sorted in increasing order, and False otherwise.

Pro-tip: Use doctests to test your function for several inputs.

Its fantastic if you can make your function recursive, but in this case, its ok to use loops as well.

C) Is File Sorted Function

Write a function is_file_sorted(filename). This function takes as input a name of the input file containing a list of integer numbers, one number per line, and returns True if the list is sorted in increasing order, and False otherwise. Test your function with several inputs.

Important: Remember to convert string values to integers before testing. Otherwise your numbers will be sorted alphabetically, for example, numbers [1,2,11,12] will be sorted [1,11,12,2], which is not the right order for integers.

Sort Verifier

Now write a sort_verifier(filename) function that, as above, takes as input a name of the input file containing a list of integer numbers, one number per line, and outputs a user-friendly message with the result, as follows:

>>> sort_verifier("input.txt") Looks like input.txt needs to be sorted 

or

>>> sort_verifier("inputsorted.txt") Congratulations! The file inputsorted.txt is nicely sorted! 

Using Sorting Algorithms

Two sorting algorithms have been provided to you in the file sorters.py. In python, we can import and use functions from other modules (other python source files).

Start with carefully studying the implementations of sorting algorithms provided in sorters.py.

Now add the following line to the top of your lab6.py file:

from sorters import selection_sort, merge_sort

Now you can call on these two functions directly from within lab6.py.

A) Merge Sort Write a function use_mergesort(inputfile, outputfile). This function takes as input a name of the input file containing a list of integer numbers, one number per line, and the output file name. This function should read-in numbers from the file, sort them using the provided merge_sort function, and output the sorted numbers to the output file, one number per line.

Important: Remember to convert string values to integers before testing. Otherwise your numbers will be sorted alphabetically, for example, numbers [1,2,11,12] will be sorted [1,11,12,2], which is not the right order for integers.

B) Selection Sort

Write a function use_selection(inputfile, outputfile). This function takes as input a name of the input file containing a list of integer numbers, one number per line, and the output file name. This function should read-in numbers from the file, sort them using the provided selection_sort function, and output the sorted numbers to the output file, one number per line.

C) Random Number Generator

Then write a function generate_nums(filename, n) that makes a file named filename and writes to it n random numbers from 0 to 99, inclusive. Use generate_nums() function to generate files of different size that you would then use for testing your use_mergesort() and use_selection().

Define this function as follows:

def generate_nums(filename, n): import random random.seed(0) # you fill in the rest 

In the above, you are importing the module random and setting the random number generator seed to be 0.

Tip: The instruction

num = random.randrange(0, 10)

will generate a single random number in the range 0-9 inclusive.

Seed Explanation:

In programming there is no such thing as a true random number generator. In reality all algorithmic random number generators are "pseudo-random" number generators. Although there are efforts that go to great lengths to actually import randomness into computing systems.

Algorithmic pseudo-random number generators use complex mathematical functions to approximate random sequences of numbers. While the sequences may seem ransom, they are actually deterministic sequences generated by using a "seed" as the input value to the function. Two "random" sequences generated from the same seed will be identical. In your function, by setting the seed to be 0 you are guarantying that your function called with the same n will always return the same sequence of numbers, a great peroperty for testing and reproducibility purposes. In this application, we don't really care if the numbers are truly random, only that they are not ordered.

Development

You may develop your code in ZyBooks and while in development, you may add code to the bottom of your file outside of the functions for testing purposes. When you go to submit, remove all extraneous code (even a call to main()) as any code outside of the functions may break the ZyBooks tests.

Interactive Terminal

For this lab, an interactive terminal has been enabled for you. This is a beta feature of ZyBooks. In the terminal, you can issue the run command to run your program. You can then directly interact with your program on the terminal, entering user input as needed. You can still opt to run and test your programs the old way, by specifying all input in the "Enter program input" box and clicking on the "Run Program" button.

In the interactive terminal, if you write doctests, you can issue the run -v command to print the output of your doctests.

Is-sorted 11) 4 is File Sorted Test 4 A 0/1 Is file sorted Your output False Test feedback in file sorted() returned None Expected Fate File Contents 22 9 63 12 5 5 Is File Sorted Test 5 A 071 is file sorted Your output True File sorted() returned None Expected True Test feedback Exact File Contents Omitted from output. Pile consists of an increasing sequence of numbers. Met Sort The