def verifySorted(A):

for i in range(len(A)-1):

if A[i] > A[i+1]:

print(f"A[{i}]=={A[i]} is greater than A[{i+1}]=={A[i+1]}")

return

print("Array is sorted!")

# Input:

# array A from which to find a pivot

# Return:

# value of the pivot

def pickPivot(A):

return(A[-1]) # always use the last value of the array A

# Input:

# A is the array to be partitioned

# pivotvalue is the value around which to pivot (assumes at least one element

# has value not less than pivotvalue)

# Return:

# returns an index in A

# A has been reordered such that every element below the index is less than

# the pivotvalue, every element above the index is not less than the

# pivotvalue, and there are no elements in A that are less than the element

# at the index that are not less than the pivotvalue

def partitionInPlace(A,pivotvalue):

lowindex = 0

highindex = len(A)-1

closestindex = len(A)-1

# loop invariant:

# every element located lower than lowindex is less than pivotvalue

# every element located higher than highindex is not less than pivotvalue

# closestindex element is a smallest element not less than pivotvalue

while(True):

#

# TO DO

#

# Input:

# an array A to be sorted

# Returns:

# A has been sorted

def quicksort(A):

# manual sort for small arrays

if len(A)

#

# TO DO

# return

# set up recursions

pivotvalue = pickPivot(A)

partitionindex = partitionInPlace(A,pivotvalue)

# call recursions

#

# TO DO

#

4. This is a coding problem. You will implement a version of Quicksort. You must submit a Python 3 source code file with a quicksort and a partitionInPlace function as specified below. You will not receive credit if we cannot call your functions. The quicksort function should take as input an array (numpy array), and for large enough arrays pick a pivot value, call your partition function based on that pivot value, and then recursively call quicksort on resulting partitions that are strictly smaller in size than the input array in order to sort the input. Additionally, your quicksort should transition from recursive calls to manual sorting (via if statements or equivalent) when the arrays become small enough. The partitionInPlace function should take as input an array (numpy array) and pivot value, partition the array (in at most linear amount of work and constant amount of space), and return an index such that (after returning) no further swaps need to occur between elements below and elements above the index in order for the array to be sorted. You are provided with a scaffold python file that you may use, which contains some suggested function behavior and loop invariants, as well as a simple testing driver. You may alter anything within or ignore it altogether so long as you maintain the function prototypes specified above. In particular, the suggestions are meant to allow the pivot value to not be in the array, which is NOT a requirement for Quicksort. 4. This is a coding problem. You will implement a version of Quicksort. You must submit a Python 3 source code file with a quicksort and a partitionInPlace function as specified below. You will not receive credit if we cannot call your functions. The quicksort function should take as input an array (numpy array), and for large enough arrays pick a pivot value, call your partition function based on that pivot value, and then recursively call quicksort on resulting partitions that are strictly smaller in size than the input array in order to sort the input. Additionally, your quicksort should transition from recursive calls to manual sorting (via if statements or equivalent) when the arrays become small enough. The partitionInPlace function should take as input an array (numpy array) and pivot value, partition the array (in at most linear amount of work and constant amount of space), and return an index such that (after returning) no further swaps need to occur between elements below and elements above the index in order for the array to be sorted. You are provided with a scaffold python file that you may use, which contains some suggested function behavior and loop invariants, as well as a simple testing driver. You may alter anything within or ignore it altogether so long as you maintain the function prototypes specified above. In particular, the suggestions are meant to allow the pivot value to not be in the array, which is NOT a requirement for Quicksort