NEED HELP ASAPPPP!!!!! ON ALL THESE QUESTIONS I have the starter code for the me
ID: 3805941 • Letter: N
Question
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: <your name>, <your e-mail address>
* Date modified: <current date>
"""
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 <= j and alist[i] <= pivot: # find a number >= pivot
i = i + 1
while i <= j and alist[j] >= pivot: # find a number <= pivot
j = j - 1
if i < j:
Sort.swap(alist, i, j) # put numbers on the correct side
i = i + 1 # keep going
j = j - 1 # keep going
else:
Sort.swap(alist, first, j) # place pivot in place
return j # index of pivot
# 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: <your name>, <your e-mail address>
* Date modified: <current date>
"""
"""
* 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 ");
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] < alist[indexMin]):
indexMin = j
SortCount.swap(alist, i, indexMin)
# 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 <= j and SortCount.compare(alist[i] <= pivot): # find a number >= pivot
i = i + 1
while i <= j and SortCount.compare(alist[j] >= pivot): # find a number <= pivot
j = j - 1
if i < j:
SortCount.swap(alist, i, j) # put numbers on the correct side
i = i + 1 # keep going
j = j - 1 # keep going
else:
SortCount.swap(alist, first, j) # place pivot in place
return j # index of pivot
# qSort - recursive method that does the work for quickSort */
def qSort(alist, first, last):
split = SortCount.partition(alist, first, last)
if first < split:
SortCount.qSort(alist, first, split - 1) # left sublist [0:pivot)
if last > 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 <= leftEnd and j <= rightEnd:
if SortCount.compare(alist[i] < alist[j]):
temp.insert(k, alist[i])
i = i + 1
else:
temp.insert(k, alist[j])
j = j + 1
k = k + 1
SortCount.moves += 1
while i <= leftEnd:
temp.insert(k, alist[i])
i = i + 1
k = k + 1
SortCount.moves += 1
while j <= rightEnd:
temp.insert(k, alist[j])
j = j + 1
k = k + 1
SortCount.moves += 1
for i in range(leftStart, rightEnd + 1):
alist[i] = temp[i]
SortCount.moves += 1
# mSort - recursive method for mergesort
def mSort(alist, temp, start, end):
if start >= 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 < 0:
k = 0
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: ")
SortCount.listCopy(asave, a)
SortCount.initStats()
SortCount.quickSort(a)
SortCount.printStats()
SortCount.printList(a)
print("mergeSort: ")
SortCount.listCopy(asave, a)
SortCount.initStats()
SortCount.mergeSort(a)
SortCount.printStats()
SortCount.printList(a)
print("shellSort: ")
SortCount.listCopy(asave, a)
SortCount.initStats()
SortCount.shellSort(a)
SortCount.printStats()
SortCount.printList(a)
print("insertionSort: ")
SortCount.listCopy(asave, a)
SortCount.initStats()
SortCount.insertionSort(a)
SortCount.printStats()
SortCount.printList(a)
print("selectionSort: ")
SortCount.listCopy(asave, a)
SortCount.initStats()
SortCount.selectionSort(a)
SortCount.printStats()
SortCount.printList(a)
print("bubbleSort: ")
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] < alist[indexMin]:
indexMin = j
Sort.swap(alist, i, indexMin)
# 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 <= j and alist[i] <= pivot: # find a number >= pivot
i = i + 1
while i <= j and alist[j] >= pivot: # find a number <= pivot
j = j - 1
if i < j:
Sort.swap(alist, i, j) # put numbers on the correct side
i = i + 1 # keep going
j = j - 1 # keep going
else:
Sort.swap(alist, first, j) # place pivot in place
return j # index of pivot
# qSort - recursive method that does the work for quickSort */
def qSort(alist, first, last):
split = Sort.partition(alist, first, last)
if first < split:
Sort.qSort(alist, first, split - 1) # left sublist [0:pivot)
if last > 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 <= leftEnd and j <= rightEnd:
if alist[i] < alist[j]:
temp.insert(k, alist[i])
i = i + 1
else:
temp.insert(k, alist[j])
j = j + 1
k = k + 1
# run out remaining elements in left list
while i <= leftEnd:
temp.insert(k, alist[i])
i = i + 1
k = k + 1
# run out remaining elelments in right list
while j <= rightEnd:
temp.insert(k, alist[j])
j = j + 1
k = k + 1
# copy temp list back to original
for i in range(leftStart, rightEnd + 1):
alist[i] = temp[i]
# mSort - recursive method for mergesort
def mSort(alist, temp, start, end):
if start >= 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: ", end="")
Sort.printList(orig)
# selection sort
Sort.copyList(orig, copy)
Sort.selectionSort(copy)
print("selection sort: ", end="")
Sort.printList(copy)
# insertion sort
Sort.copyList(orig, copy)
Sort.insertionSort(copy)
print("insertion sort: ", end="")
Sort.printList(copy)
# Shell sort
Sort.copyList(orig, copy)
Sort.shellSort(copy)
print("Shell sort: ", end="")
Sort.printList(copy)
# bubble sort
Sort.copyList(orig, copy)
Sort.bubbleSort(copy)
print("bubble sort: ", end="")
Sort.printList(copy)
# quick sort
Sort.copyList(orig, copy)
Sort.quickSort(copy)
print("quick sort: ", end="")
Sort.printList(copy)
# merge sort
Sort.copyList(orig, copy)
Sort.mergeSort(copy)
print("merge sort: ", 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!Explanation / Answer
1.)
Our list is 24 3 27 13 34 2 50 12
a)
Selection sort: So selection sort is a simple comparison based algorithm which contains the elements in the array in two parts one part of the array will be sorted part and another is unsorted. When the algorithm starts at first part smallest element in the array will come at index 0 after swapping previous sitting element at index 0 with our smallest value (or the biggest element, that completely depends on whether you want sorted array in increasing or non-increasing order). and then second part starts, when it finishes the next smallest element will come at index 1 in order to form sorted array this will run for n passes and we will have sorted array in the end.
So for the given example.
After first pass our array will look like,
2 3 27 13 34 24 50 12
Second pass
2 3 27 13 34 24 50 12
Third Pass
2 3 12 13 34 24 50 27
b)
let's run through the algorithm to identify and call the number of times in which inner while loop will be skipped as count, initially count=0
at i=1 24 and 3 will be compared inner while will be executed to swap , count=0
i=2, 24< 27 so inner while will be skipped, count=1
i=3, 27>13 so not skipped, count=1
now 24 > 13 again not skipped, count =1
now our array will look like
3 13 24 27 34 2 50 12
i=4; 27<34 it will be skipped, count=2
i= 5 34>2, not skipped count=2
2 will be shifted till the left, but still count=2
2 3 13 24 27 34 50 12
i=6 34<50, skipped, count =3
i=7, 50>12, not skipped; count=3
12 will run through the array till it is compared with 3 and now we will have sorted array
2 3 12 13 24 27 34 50
c)
Using increment of 3 the list will be divided into 3 sublists and it will look like this
sublist 1
24 3 27 13 34 2 50 12
sublist 2
24 3 27 13 34 2 50 12
sublist 3
24 3 27 13 34 2 50 12
sorted sublist will look like this:
sublist 1
13 3 27 24 34 2 50 12
sublist 2
24 3 27 13 12 2 50 34
sublist 3
24 3 2 13 34 27 50 12
and after initial phase:
13 3 2 24 12 27 50 12
d)
Bubble sort:
our array is 24 3 27 13 34 2 50 12
First pass
3 24 13 27 2 34 12 50
Second pass
3 13 24 2 27 12 34 50
Third pass
3 13 2 24 12 27 34 50
Fourth pass
3 13 12 24 27 34 50
So after fourth pass our array will look like this
3 13 12 24 27 34 50, We can clearly see here that after fifth pass the array will be sorted.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.