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:

8 15 20 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:

5 15 20 8 12

Finally, 5 is compared to 12, and no swap occurs because 5 is already smaller 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.

On pass 1, swap sort compares the element in position 1 with the elements in positions 2 through (n 1) and performs swaps when needed. The process continues for passes 2 through (n 2), at which point the list is fully sorted.

In the file SortCount.py, add a method called swapSort() that implements the swap sort algorithm described above. Its only parameter should be a reference to a list of integers. Like the other methods in this file, your swapSort method must make use of the compare(), and swap() helper methods so that you can keep track of the total number of comparisons and moves that it performs. If you need to compare two list elements, you should use the method call compare(comparison); for example, compare(alist[0] < alist[1]). This method will return the result of the comparison (True or False), and it will increment the count of comparisons that the class maintains. If you need to swap elements i & j of alist you should use move(alist, i, j). You also need to count the number of moves by incrementing the SortCount class variable move.

Determine the big-O time efficiency of swapSort when it is applied to two types of lists: lists that are almost sorted, and lists that are randomly ordered. You should determine the big-O expressions by experiment, rather than by analytical argument.

To do so, run the algorithm on lists of different sizes (for example, n = 1000, 2000, 4000, 8000 and 16000). Modify the test code in the main() method so that it runs swapSort on the lists that are generated, and use this test code to gather the data needed to make your comparisons. (Note: you can also test the correctness of your method by running it on lists of 10 or fewer items; the sorted list will be printed in such cases.)

For each type of list, you should perform at least ten runs for each value of n and compute the average numbers of comparisons and moves for each set of runs. Based on these results, determine the big-O efficiency class to which swapSort belongs for each type of list (O(n), O(logn), O(nlogn), O(n2), etc.). Explain clearly how you arrived at your conclusions. If the algorithm does not appear to fall neatly into one of the standard efficiency classes, explain your reasons for that conclusion, and state the two efficiency classes that it appears to fall between. Put the results of your experiments, and your accompanying analysis and conclusions, in a plain-text file called ps2_experiments.txt.

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)