Python selectionSort, merge, and mergeSort

# - Read through Sec 1 of the lecture notes. # * Understand Selection and Merge Sort. # - Code the three functions selectionSort, merge and mergeSort # * Just as the lecture notes discuss. # * Follow the extra comments written in each function. # * mergeSort must be a recursive function to call merge # - Study the test codes to use them effectively # to check the correctness and speed. # # SUBMISSION # - Don't change the function names, and header indentaion # - File name = EX12_1.py and upload it to Vocareum # - Upload just the three functions and nothing else. #

def selectionSort(intList): n=len(intList) #code the rest of selection sort for i in range(n); for k in range(n); if intList[i]>intList[k] intList[i],intList[k]

return intlist #until here

def merge(A1, A2): #A1 and A2 are sorted list. The function merges A1 with A2 # to return a single sorted list including all elements # start code here

# until here

def mergeSort(A): # This has to be a RECURSIVE function using merge(A1, A2) # - The grading script will check if it's recursive # start code here

# until here

# Test codes ### to create a list of pseudo random numbers ### - random because no predictable patterns ### - psedo because it generates the same list every time import random random.seed(10,2) t = random.getstate() intList=list(t[1]) print("The input intList is a list of ", len(intList), " integers.") ### If you want to see the elements, remove # in the next line #print(intList) #result1 = selectionSort(intList) #print("Your result by selectionSort:", result1) #result2= mergeSort(intList) ### Correctness Check #print(" If both results are correct, it should show True here: ", result1==result2)

### To check the running time of the two algorithms: ### Run the following segment by removing # #import sys, trace #tracer = trace.Trace( # ignoredirs=[sys.prefix, sys.exec_prefix], # trace=0, # count=1) #tracer.run("selectionSort(intList)") #tracer.run("mergeSort(intList)") #r = tracer.results() #r.write_results(show_missing=True, coverdir=".") ### ### Open the created file EX1_16.cover in the same folder ### to see the #executed lines. # # Results with my answer key: # Selection sort # 1 + 626 + 196250 + 195625 + 1 = 392503 steps # # Merge sort # 624+624+3412+624+2788*3 + 1249 + 625 + 624*4 = 18018 steps # # Merge sort running in O(n log n) time is much faster than # the O(n^2) time algorithm Selection Sort.