Please Need help with part 3 asap!!! I have the code to start it off need help please!!!!

""" * SortCount.py * * Adopted from: Computer Science E-22, Harvard University * * Modified by: , * Date modified: """

""" * This class contains implementations of various array-sorting * algorithms. All comparisons and moves are performed using helper * methods that maintain counts of these operations. Each sort method * takes an array of integers. The methods assume that all of the * elements of the array should be sorted. The algorithms sort the array * in place, altering the original list. """

from random import * import math

class SortCount():

MAX_VAL = 65536 # the integers in the test arrays are in the range 0, ..., MAX_VAL compares = 0 # total number of comparisons moves = 0 # total number of moves

# compare - a wrapper that allows us to count comparisons. def compare(comparison): SortCount.compares += 1 return comparison

# swap - swap the values of two variables. # Used by several of the sorting algorithms below. def swap(alist, a, b): alist[a], alist[b] = alist[b], alist[a] SortCount.moves += 3

# randomList- creates an list of randomly generated integers # with the specified number of elements and the specified # maximum value def randomList(n, maxVal = MAX_VAL): alist = n * [0] for i in range(len(alist)): alist[i] = randrange(0, maxVal) return alist

# Sets the counts of moves and comparisons to 0. def initStats(): SortCount.compares = 0 SortCount.moves = 0

# Prints the current counts of moves and comparisons. def printStats(): if SortCount.compares == 0: spaces = 0 else: spaces = int(math.log(SortCount.compares, 10)) for i in range(10 - spaces): print(" ", end="") print(str(SortCount.compares) + " comparisons\t");

if SortCount.moves == 0: spaces = 0 else: spaces = int(math.log(SortCount.moves, 10)) for i in range(10 - spaces): print(" ", end="") print(str(SortCount.moves) + " moves")

# selectionSort def selectionSort(alist): for i in range(len(alist)): indexMin = i # find the smallest index for j in range(i + 1, len(alist)): if SortCount.compare(alist[j]

# insertionSort def insertionSort(alist): for i in range(1, len(alist)): # save a copy of the element and index to be inserted. val = alist[i] pos = i SortCount.moves += 1 # save a copy of the element to be inserted. while pos >= 1 and SortCount.compare(alist[pos-1] > val): alist[pos] = alist[pos-1] pos = pos - 1 SortCount.moves += 1 # Put the element in place. alist[pos] = val SortCount.moves += 1

# shellSort def shellSort(alist): gap = len(alist) // 2 # calculate the gap # Do insertion sort for each gap. while gap >= 1: for start in range(gap): # modified insertion sort for i in range(start + gap, len(alist), gap): # save a copy of the element and index to be inserted. val = alist[i] pos = i SortCount.moves += 1 while pos >= gap and SortCount.compare(alist[pos-gap] > val): alist[pos] = alist[pos-gap] pos = pos - gap SortCount.moves += 1 # Put the element in place. alist[pos] = val SortCount.moves += 1 # Calculate gap for next pass. gap = gap // 2

# bubbleSort def bubbleSort(alist): for i in range(len(alist)): for j in range(len(alist)-1): if SortCount.compare(alist[j] > alist[j+1]): SortCount.swap(alist, j, j+1)

# partition - helper method for qSort def partition(alist, first, last): pivot = alist[first] SortCount.moves += 1 i = first + 1 # set index going left to right j = last # set index going right to left

while True: while i = pivot i = i + 1 while i = pivot): # find a number

# qSort - recursive method that does the work for quickSort */ def qSort(alist, first, last): split = SortCount.partition(alist, first, last) if first split + 1: SortCount.qSort(alist, split + 1, last) # right sublist(pivot:last]

# quicksort def quickSort(alist): SortCount.qSort(alist, 0, len(alist)-1) # merge - helper method for mergesort def merge(alist, temp, leftStart, leftEnd, rightStart, rightEnd): i = leftStart j = rightStart k = leftStart while i = end: return mid = (start + end) // 2 # split the list in half SortCount.mSort(alist, temp, start, mid) # sort left half SortCount.mSort(alist, temp, mid + 1, end) # sort the right half SortCount.merge(alist, temp, start, mid, mid + 1, end) # merge the two halfs # mergesort def mergeSort(alist): temp = [] SortCount.mSort(alist, temp, 0, len(alist) - 1) # almostSortedArray - creates an almost sorted array of integers # with the specified number of elements def almostSortedList(n): # Produce a random array and sort it. alist = SortCount.randomList(n) SortCount.quickSort(alist) # Move one quarter of the elements out of place by between 1 # and 5 places for i in range(n // 8): j = int(random() * n) displace = -5 + int(random() * 11) k = j + displace if k n - 1: k = n - 1 SortCount.swap(alist, j, k) return alist

# Copys the src list to the dest list def listCopy(source, dest): for i in range(len(source)): dest[i] = source[i] # Prints the specified list in the following form: # { lista[0] lista[1] ... } def printList(alist): # Don't print it if it's more than 10 elements. if len(alist) > 10: return print("{ ", end="") for i in range(len(alist)): print(str(alist[i]) + " ", end="") print("}")

def main():

# Get various parameters from the user. numItems = eval(input("How many items in the list? ")) listType = input("Random (r), almost sorted (a), or fully sorted (f)? ") print("")

a = numItems * [0] # initialize the list asave = numItems * [0] # and a copy of it # Create the lists. if listType in "Aa": a = SortCount.almostSortedList(numItems) else: a = SortCount.randomList(numItems) if listType in "Ff": SortCount.quickSort(a)

SortCount.listCopy(a, asave) SortCount.printList(a)

# Try each of the various algorithms, starting each time # with a fresh copy of the initial array. print("quickSort:\t\t") SortCount.listCopy(asave, a) SortCount.initStats() SortCount.quickSort(a) SortCount.printStats() SortCount.printList(a)

print("mergeSort:\t\t") SortCount.listCopy(asave, a) SortCount.initStats() SortCount.mergeSort(a) SortCount.printStats() SortCount.printList(a)

print("shellSort:\t\t") SortCount.listCopy(asave, a) SortCount.initStats() SortCount.shellSort(a) SortCount.printStats() SortCount.printList(a)

print("insertionSort:\t\t") SortCount.listCopy(asave, a) SortCount.initStats() SortCount.insertionSort(a) SortCount.printStats() SortCount.printList(a)

print("selectionSort:\t\t") SortCount.listCopy(asave, a) SortCount.initStats() SortCount.selectionSort(a) SortCount.printStats() SortCount.printList(a)

print("bubbleSort:\t\t") SortCount.listCopy(asave, a) SortCount.initStats() SortCount.bubbleSort(a) SortCount.printStats() SortCount.printList(a)

main()

determine whether you need to make a recursive call on a particular sublist. Tracing through some concrete examples may help you to discover the logic. Note: Rather than checking to see whether a given recursive call is needed, it's also possible to defer this checking to the start of the next invocation of the method. In other words, the recursive method could begin by checking to see if the current sublist could contain one or more of the median values, and, if it could not, the method could return without doing anything. You should be able to accomplish this task with only 4-10 lines worth of changes/additions to the standard quicksort algorithm. If your modifications to the code in qsortO are substantially longer than this, you are likely on the wrong track. 3. Implementation and experimental analysis of swap sort (30 points total; 15 points each part) Swap sort is another sorting algorithm based on exchanges. Like bubble sort, swap sort compares pairs of elements and swaps them when they are out of order, but swap sort looks at different pairs of elements than bubble sort does. On pass i of swap sort, the element in position i of the list is compared with the elements in all positions to the right of position i, and pairs of elements are swapped as needed. At the end of pass i, the element in position i is where it belongs in the sorted list. For example, let's say that we have the following initial list 15 8 20 5 12 On pass 0, swap sort compares the element in position 0 with the elements in positions 1 through n 1, where n is the number of elements in the list. First, 15 is compared to 8, and because 8 is less than 15, the two elements are swapped: 15 200 5 12 Next, 8 (which is now in position 0 is compared to 20, and no swap occurs because 8 is already smaller than 20. Then 8 is compared with 5, and the two elements are swapped: 15 20 8 12 s compared to 12, and no swap occurs because 5 is already smaller Finally, 5 than 12. At this point, pass 0 is complete, and the element in position 0 (the 5 is where it belongs in the sorted list