Date: Tuesday, October 31, 2023.
Due Date: Tuesday, November 7, 2023.

Goal: to sort lists in Python.

Create a Python file called lab9.py and add your name and the lab number as a comment at the top.

Copy the following Python functions discussed in class into your file:

from random import *
from time import *

# Creates a list with given size and random values between 0 and bound
def makeRandomList(size, bound):
    a = []
    for i in range(size):
        a.append(randint(0, bound))
    return a

# Sorting a list using bubble sort
def bubbleSort(a):
    n = len(a)
    while n > 0:
        for i in range(n-1):
            if a[i] > a[i+1]:
                a[i], a[i+1] = a[i+1], a[i]
        n = n - 1

Also add the following code defining the main testing code for the module:

# main testing function
def main():
    # testing code to be added later

# To be executed when we run the module by itself
if __name__ == '__main__':
    main()

a. Timing the Sort

Add a function above the main called test1 with one parameter nthat will be the size of the list. In this function, call the function creating a random array with the value of n for the size and a large value for the bound (maybe 100000), and store it in a variable. Then add the following timing structure seen in class:

beforeTime = time()
functionCall()
totalTime = time() - beforeTime

where you replace the function call with a call to bubbleSort with the random list you created. Then after you compute the total time, output it and the sorted array.

Then in the main, call this function test1 with a value between 10 and 20 and test the program.

b. Improving the Bubble Sort

Make a copy of the bubble sort function and call it betterBubbleSort. In this function, add a variable called sorted that you initialize as False before the while loop. Then in the while loop, at the top, initialize it as True. Finally, in the for loop, after you make a swap, initialize the variable as False at the same level as the swap.

We still need to end the while loop when the variable becomes true. In the continuation condition for this loop, add and not sorted (before the :). Now the function should work.

Make a copy of the testing function and call it test2. The only change we need here is to call the function betterBubbleSort instead of the simple one. Add a call to this second function in the main.

Test the program again to see that both sorting functions work and to compare the timing.

c. Built-in Sort

Make another copy of the test function and call it test3. Here, replace the call to the bubble sort by a call to the built-in function sort. If a is your variable containing the list, the call would look like this:
a.sort()

Add a call to this function in the main and test the program to see the result.

d. Large List

We would like to test the three functions with a large list to be able to compare the timing. In all 3 of the testing functions, remove the list from the printed results, so that only the timing value is output.

To make sure that the 3 functions are tested on the same list, add a call to the function seed(150) before each of them. You can use another integer, as long as it's the same for each of them. Then increase the size of the lists in the function calls to 100000.

Test the program to see the result. You can repeat the experiment with another value for the seed to see what happens. Can you conclude that the built-in sort is better than the bubble sort? And is the improvement that we made efficient?

Upload the file lab9.py in Canvas, Assignments, Homework 9. You can wait until you finish the homework to upload all the files at the same time.