Here is the **_Unsort_** function we have been using.

from random import randrange # for unsorting an array

def unsort(L):

'''Postcondition: The elements of L have been rearranged in random order.'''

# For each position, swap the element with another element.

for i in range(len(L)):

j = randrange(0,len(L))

L[i], L[j] = L[j], L[i]

Now that you are sure your code is working properly, it is time to do the analysis.

Use your program to determine the average number of comparisons performed in sorting 1000 arrays for each of the array sizes, 10, 50, 100, 500, 1000, 5000, 10,000, 50,000 and 100,000. For each size, have your code print the average number of comparisons performed on the 1000 arrays of that size and also what the predicted average-case time complexity from the formula given in section 2.4 of your text.

list_sizes = [10, 50, 100, 500, 1000, 5000, 10000, 50000, 100000]

numberOfLists = 1000 # the number of lists to sort for each list size

numbersOfComparisons = []

...