The median of a list of integers is the value that would belong in the middle position of the list if the list were sorted. For example, consider the following list:

alist = [4, 18, 12, 34, 7, 42, 15, 22, 5]

The median of this list is 15, because that value would end up in the middle position if the list were sorted:

alist = [4, 5, 7, 12, 15, 18, 22, 34, 42]

If a list has an even number of elements, the median is the average of the elements that would belong in the middle two positions of the list, if the list were sorted.

In the file SortCount.py, implement a program that finds the median of a list of integers by using the partitioning approach taken by quickSort. However, for the sake of efficiency, you should not sort a sublist if it could not contain the median.

In SortCount.py, we have given you the following:

a copy of the partition() method from the quickSort The recursive method that you will write should call this method to process the necessary portions of the list (see below). You should not need to change it.

the skeleton of a method named findMedian() that will serve as a wrapper method around your recursive median-finding method, just as the quickSort() method serves as a wrapper around the recursive quickSortHelper() To implement this wrapper method, all you need to do is add an appropriate initial call to your recursive method. You should not change the header of this method in any way.

a main() method that you should fill with code that tests your median-finding algorithm. We have included sample definitions of odd- and even-length lists that you can use as you see fit. Make sure that your main() method calls the wrapper method, rather than calling the recursive method directly.

The recursive method that you write will be similar to the recursive quickSortHelper() method from the quickSort algorithm. However, you will need to modify the algorithm so that it allows you to put the median value or values in the appropriate positions without actually sorting the entire list. You are expected to only sort as much of the list as is necessary to determine the median value, and for full credit you mustavoid calling partition() on sublists that could not possibly contain the median value (see below).

Your recursive method only needs to succeed in getting the median value (or values, in the case of an even list) into the middle position (or positions, in the case of an even list). It does not need to return the median value; it may simply be a void method. Your main() method can then print the median value by looking at the value(s) in the middle position(s) of the list after your algorithm has finished.

Hints:

Your recursive method will be similar to our quickSortHelper() However, after you call partition(), you need to determine whether to make recursive call(s) to process just the left sublist, just the right sublist, or both sublists, depending on whether each sublist could contain the median value (or, in the case of an even-length list, at least one of the two median values). When making this decision, remember that after a call to partition(), everything in the left sublist is less than or equal to everything in the right sublist. Given this fact, and given the location(s) where the median value(s) must ultimately end up, you should be able to 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, its 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 quickSortHelper() are substantially longer than this, you are likely on the wrong track.USE PYTHON!!

HERE IS STARTING CODE:

""" SortCount.py """ from random import randint class SortCount: """ Part 1 """ def removeDups(alist): pass # Remove the pass command and add your solution here """ Part 2 """ """ 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 # Remove the pass command and add your "wrapper method" here. # Put the definition of your recursive median-finding method below. """ Part 3 """ # the integers in the test arrays are drawn from the range 0, ..., MAX_VAL MAX_VAL = 65536 compares = 0 # total number of comparisons moves = 0 # total number of moves """ compare - a wrapper that allows us to count comparisons. """ def compare(comparison): compares = compares + 1 return comparison """ move - moves an element of the specified array to a different location in the array. move(arr, dest, source) is equivalent to arr[dest] = arr[source]. Using this method allows us to count the number of moves that occur. """ def move(alist, dest, source): moves = moves + 1 alist[dest] = alist[source]; """ 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] moves = moves + 3 """ randomArray - creates an array of randomly generated integers with the specified number of elements and the specified maximum value """ def randomArray(n, maxVal): alist = [] for i in range(len(alist)): alist.append(random.randint(0, maxVal+1)) return alist def randomArray(n): return randomArray(n, MAX_VAL) """ almostSortedArray - creates an almost sorted array of integers with the specified number of elements """ def almostSortedArray(n): # Produce a random list and sort it. alist = randomArray(n) 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.random() * n)) displace = -5 + int((random.random() * 11)) k = j + displace if k < 0: k = 0 if k > n - 1: k = n - 1; swap(arr, j, k) return arr # Prints the current counts of moves and comparisons. def printStats(): if compares == 0: spaces = 0 else: spaces = int((math.log(compares)/math.log(10))) for i in range(10 - spaces): print(" ") print(compares + " comparisons\t"); if moves == 0: spaces = 0: else: spaces = int((math.log(moves)/math.log(10))) for i in range(10 - spaces): print(" ") print(moves + " moves") # quickSort def quickSort(alist): quickSortHelper(alist,0,len(alist)-1) def quickSortHelper(alist,first,last): if first < last: splitpoint = partition(alist,first,last) quickSortHelper(alist,first,splitpoint-1) quickSortHelper(alist,splitpoint+1,last) def partition(alist,first,last): pivotvalue = alist[first] moves = moves + 1 leftmark = first+1 rightmark = last done = False while not done: while compare(leftmark <= rightmark and alist[leftmark] <= pivotvalue): leftmark = leftmark + 1 while compare(alist[rightmark] >= pivotvalue and rightmark >= leftmark): rightmark = rightmark -1 if rightmark < leftmark: done = True else: swap(alist, leftmark, rightmark) swap(alist, first, rightmark) # Prints the specified list in the following form: [ arr[0] arr[1] ... ] def printArray(alist): # Don't print it if it's more than 10 elements. if length(alist) > 10: return print("[ ") for i in alist: print(i + " ") print("]") def main(): """ Part 1. Add your test cases for the removeDups() method here """ """ Part 2. Add your test cases for the findMedian() method here """ # 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. """ Part 3. """ a = [] # the array asave = [] # a copy of the original unsorted array # Get various parameters from the user. print() numItems = int(input(("How many items in the array? "))) arrayType = input("Random (r), almost sorted (a), or fully sorted (f)? ") print() # Create the arrays. if arrayType == "a": a = almostSortedArray(numItems); else: a = randomArray(numItems); if arrayType == "f": quickSort(a) asave = copy.copy(a) printArray(a) print("swapSort") # initStats() swapSort(a) printStats() printArray(a)