NEED HELP ASAPPPP!!!!! ON ALL THESE QUESTIONS I have the starter code for the median, sort count and sort.

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

from Sort import *

class Median(): # partition - helper method for your recursive median-finding method */ def partition(alist, first, last): pivot = alist[first] 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

# findMedian - "wrapper" method for your recursive median-finding method. # It just makes the initial call to that method, passing it # whatever initial parameters make sense. def findMedian(alist): pass # add an appropriate call to your recursive method # Put the definition of your recursive median-finding method below. # the median of this array is 15 oddLength = [4, 18, 12, 34, 7, 42, 15, 22, 5] # the median of this array is the average of 15 and 18 = 16.5 evenLength = [4, 18, 12, 34, 7, 42, 15, 22, 5, 27] # Put code to test your method here.

""" * 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()

""" * Sort.py * * Adopted from: omputer Science E-22, Harvard University * * Your solution to programming problem 1 should go in this file. * * IMPORTANT: Your solution to programming problem 3 should go in * SortCount.py, rather than in this file. * * To call one of these methods from another class, precede its name * by the name of the class. For example: * * Sort.bubbleSort(arr) */

/** * Sort - a class containing implementations of various array-sorting * algorithms. Each sorting method takes an array of ints, and * assumes that the array is full. The methods sort the array in place, * altering the original array. """ from random import *

class Sort(): # swap - swap the values of two variables. # Used by several of the sorting algorithms below. def swap(alist, i, j): alist[i], alist[j] = alist[j], alist[i] # 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 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 # save a copy of the element to be inserted. while pos >= 1 and alist[pos-1] > val: alist[pos] = alist[pos-1] pos = pos - 1 # Put the element in place. alist[pos] = val

# 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 # save a copy of the element to be inserted. while pos >= gap and alist[pos-gap] > val: alist[pos] = alist[pos-gap] pos = pos - gap # Put the element in place. alist[pos] = val # 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 alist[j] > alist[j+1]: Sort.swap(alist, j, j+1)

# partition - helper method for qSort def partition(alist, first, last): pivot = alist[first] 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 = Sort.partition(alist, first, last) if first split + 1: Sort.qSort(alist, split + 1, last) # right sublist(pivot:last]

# quicksort def quickSort(alist): Sort.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 # merge the two lists as long as both lists have elements while i = end: return mid = (start + end) // 2 # split the list in half Sort.mSort(alist, temp, start, mid) # sort left half Sort.mSort(alist, temp, mid + 1, end) # sort the right half Sort.merge(alist, temp, start, mid, mid + 1, end) # merge the two halfs # mergesort def mergeSort(alist): temp = [] Sort.mSort(alist, temp, 0, len(alist) - 1) # printList - prints the specified array in the following form: # { alist[0] alist[1] ... } def printList(alist): print("{ ", end="") for i in range(len(alist)): print(str(alist[i]) + " ", end="") print("}") # coptList - copies one list to another def copyList(source, dest): for i in range(len(source)): dest[i] = source[i] def main(): NUM_ELEMENTS = 10 NUM_VARS = 5 orig = [] copy = [] for i in range(NUM_ELEMENTS): temp = randint(0, NUM_ELEMENTS * NUM_VARS) orig.append(temp) copy.append(temp)

# original list print("original list:\t", end="") Sort.printList(orig)

# selection sort Sort.copyList(orig, copy) Sort.selectionSort(copy) print("selection sort:\t", end="") Sort.printList(copy)

# insertion sort Sort.copyList(orig, copy) Sort.insertionSort(copy) print("insertion sort:\t", end="") Sort.printList(copy)

# Shell sort Sort.copyList(orig, copy) Sort.shellSort(copy) print("Shell sort:\t", end="") Sort.printList(copy)

# bubble sort Sort.copyList(orig, copy) Sort.bubbleSort(copy) print("bubble sort:\t", end="") Sort.printList(copy)

# quick sort Sort.copyList(orig, copy) Sort.quickSort(copy) print("quick sort:\t", end="") Sort.printList(copy)

# merge sort Sort.copyList(orig, copy) Sort.mergeSort(copy) print("merge sort:\t", end="") Sort.printList(copy)

main()

Problem Set 2 Part I: Short-Answer (written') Problems (30 points total) Submit your answers to part I in a plain-text file called ps2 parti. txt, and put your name and email address at the top of the file. Important: When big-o expressions are called for, please use them to specify tight bounds, as explained in the lecture notes. 1. Sorting practice (12 points; 2 points for each part) Given the following list: 24 3 27 13 34 2 50 12 a. If the list were sorted using selection sort, what would the list look like after the third pass of the algorithm e., after the third time that the algorithm performs a pass or partial pass through the elements of the list)? b. If the list were sorted using insertion sort, on how many iterations of the outer loop would the inner while loop be skipped? c. If the list were sorted using Shell sort, what would the list look like after the initial phase of the algorithm, if you assume that it uses an increment of 3? The method presented in lecture would start with an increment of 7, but you should assume that it uses an increment of 3 instead.) d. If the list were sorted using bubble sort, what would the list look like after the fourth pass of the algorithm? e. If the list were sorted using the version of quicksort presented in lecture, what would the list look like after the initial partitioning phase? f. If the list were sorted using the version of mergesort presented in lecture, what would the list look like after the completion of the fourth call to the mergeC) method the method that merges two sublists? Note: the merge method is the helper method; is not the recursive msort method. There will be no partial credit on the above questions, so please check your answers carefully