Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

My tests for sorting algorithms are not working. sorting.py has 6 sorting algorithms and test_sorting.py has test cases to run those algorithms, but test cases

My tests for sorting algorithms are not working. sorting.py has 6 sorting algorithms and test_sorting.py has test cases to run those algorithms, but test cases are not working. please correct the errors in test_sorting.py file so that it can test all the sorting algorithms. sorting.py # 1. selection sort # 2. insertion sort # 3. shell sort # 4. heap sort # 5. merge sort # 6. quick sort import random import time import unittest import matplotlib matplotlib.use('TkAgg') import matplotlib.pyplot as plt class Sorting(object): """Sorting class """ def __init__(self): self.id = [] self.size = 0 def sort_init(self, N): '''try: self.id = random.sample(range(1, N ** 3), N) except ValueError: print('Sample size exceeded population size.')''' self.id = [random.randint(0, N - 1) for i in range(N)] self.size = len(self.id) def get_id(self): return self.id def printArray(self): print(self.get_id()) def selection_sort(self): """Selection sort algorithm is an in-place comparison sort. It has O(n^2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort """ for i_idx, i_item in enumerate(self.id): min = i_idx for j_idx in range(i_idx + 1, len(self.id)): if (self.id[j_idx] < self.id[min]): min = j_idx # swap temp = self.id[i_idx] self.id[i_idx] = self.id[min] self.id[min] = temp def insertion_sort(self): """Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. More efficient in practice than most other simple quadratic (i.e., O(n^2)) algorithms such as selection sort or bubble sort specifically an """ # size is a global variable which contains the length of the array size = self.size for i in range(1, size): temp = self.id[i] j = i - 1 while j >= 0 and temp < self.id[j]: self.id[j + 1] = self.id[j] j -= 1 self.id[j + 1] = temp def callInsertionSort(self): self.insertion_sort() def shell_sort(self): size = len(self.id) gap = size // 2 while gap > 0: for i in range(gap, size): temp = self.id[i] j = i while j >= gap and self.id[j - gap] > temp: self.id[j] = self.id[j - gap] j -= gap self.id[j] = temp gap //= 2 return 1 def callShellSort(self): self.shell_sort() def heapify(self, arr, n, i): largest = i left = 2 * i + 1 right = 2 * i + 2 if left < n and arr[i] < arr[left]: largest = left if right < n and arr[largest] < arr[right]: largest = right if largest != i: # swap arr[i], arr[largest] = arr[largest], arr[i] self.heapify(arr, n, largest) # all the way to bot def heap_sort(self, arr): n = len(arr) for x in range(n - 1, -1, -1): self.heapify(arr, n, x) # heapify from the bottom up for x in range(n - 1, -1, -1): # swap bot for top, then heapify from 0 passed in for i arr[x], arr[0] = arr[0], arr[x] self.heapify(arr, x, 0) def callHeapSort(self): self.heap_sort(self.get_id()) def merge_sort(self, arr): """Merge sort is a divide and conquer algorithm that was invented by John von Neumann in 1945. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. """ if len(arr) > 1: mid = len(arr) // 2 LeftSubArray = arr[:mid] RightSubArray = arr[mid:] self.merge_sort(LeftSubArray) self.merge_sort(RightSubArray) # now we merge i = j = k = 0 while (i < len(LeftSubArray) and j < len(RightSubArray)): if LeftSubArray[i] < RightSubArray[j]: arr[k] = LeftSubArray[i] i += 1 else: arr[k] = RightSubArray[j] j += 1 k += 1 while (i < len(LeftSubArray)): arr[k] = LeftSubArray[i] k += 1 i += 1 while (j < len(RightSubArray)): arr[k] = RightSubArray[j] k += 1 j += 1 def callMergeSort(self): self.merge_sort(self.get_id()) def partition(self, arr, low, high): pivot = arr[high] i = low - 1 for j in range(low, high): # low to high NOT 0,high if (arr[j] <= pivot): i = i + 1 arr[i], arr[j] = arr[j], arr[i] # now swap the last 2 elements arr[i + 1], arr[high] = arr[high], arr[i + 1] return i + 1 def quick_sort(self, arr, low, high): if (low < high): # base case part = self.partition(arr, low, high) self.quick_sort(arr, low, part - 1) self.quick_sort(arr, part + 1, high) def callQuickSort(self): self.quick_sort(self.id, 0, len(self.id) - 1) def shuffleArray(self): random.shuffle(self.id) '''if __name__ == "__main__": obj = Sorting() obj.sort_init(10) obj.printArray() obj.callQuickSort() obj.printArray()''' if __name__ == "__main__": # iteration iteration = 0 obj = Sorting() # declaring the sorting object while iteration < 6: # change to 6 when including shell size_array = []; timing = [] x = 1 t0 = 0 temp = [] degree = 3 # replace to 6 in final while x <= degree: # x goes up to 10^X # p0=time.time() obj.sort_init(pow(10, x)) set_szs = [pow(10, x)] # 10^x, all the way up to 10^6 t0 = time.time() if iteration == 0: LineType = "Selection Sort" obj.selection_sort() elif iteration == 1: # Insertion Sort LineType = "Insertion Sort" obj.callInsertionSort() elif iteration == 2: # Merge Sort LineType = "Shell Sort" obj.callShellSort() elif iteration == 3: # Merge Sort LineType = "Merge Sort" obj.callMergeSort() elif iteration == 4: # Heap Sort LineType = "Heap Sort" obj.callHeapSort() elif iteration == 5: LineType = "Quick Sort" obj.callQuickSort() t1 = time.time() obj.shuffleArray() # t1 = time.time() #Put it back to the top total_time = t1 - t0 print("Iteration", " ", iteration, " ", "Time", LineType, total_time, "DEGREE", x) timing.append(total_time) size_array.append(set_szs) x = x + 1 iteration = iteration + 1 plt.plot(size_array, timing, label=LineType) # this plots things in log scale (pls google it), you need to add matplotlib to your virtualenv first! plt.xscale('log') plt.yscale('log') plt.legend(loc='upper left') plt.xlabel('Number of Objects') plt.title('log') plt.ylabel('Time') plt.show() 

test_sorting.py

import unittest import copy import sys sys.path.append('C:/Users/akash/PycharmProjects/student_check/venv/Lib/sorting.py') class Test_UF(object): @classmethod def setup_class(klass): """This method is run once for each class before any tests are run""" print(" ##### Start Function Tests ##### ") def test_one(self): pass def test_two(self): expected = (1, 2, 3) actual = (1, 2, 3) assert expected == actual def test_single_item(self): expected = [1] actual = self.sort(expected) self.assertEqual(expected, actual) def test_two_items_sorted(self): expected = [1, 2] actual = self.sort(expected) self.assertEqual(expected, actual) def test_two_items_unsorted(self): expected = [2, 1] actual = self.sort(expected) self.assertEqual(actual, [1, 2]) def test_zero_in_list(self): expected = [10, 0] actual = self.sort(expected) self.assertEqual(actual, [0, 10]) def test_odd_number_of_items(self): expected = [13, 7, 5] actual = self.sort(expected) self.assertEqual(actual, [5, 7, 13]) def test_even_number_of_items(self): expected = [23, 7, 13, 5] actual = self.sort(expected) self.assertEqual(actual, [5, 7, 13, 23]) def test_duplicate_integers_in_list(self): expected = [1, 2, 2, 1, 0, 0, 15, 15] actual = self.sort(expected) self.assertEqual(actual, [0, 0, 1, 1, 2, 2, 15, 15]) def test_larger_integers(self): expected = [135604, 1000000, 45, 78435, 456219832, 2, 546] actual = self.sort(expected) self.assertEqual(actual, [2, 45, 546, 78435, 135604, 1000000, 456219832]) def test_selection_sort_0(self): # initialize testbed arr_under_test = Sorting() arr_under_test.sort_init(10) # test against built in python sorted() function. # expected = sorted(copy.deepcopy(arr_under_test.get_id())) expected = sorted(arr_under_test.get_id()) actual = arr_under_test.selection_sort() assert expected == actual def test_insertion_sort_0(self): # initialize testbed arr_under_test = Sorting() arr_under_test.sort_init(10) expected = sorted(arr_under_test.get_id()) actual = arr_under_test.insertion_sort() assert expected == actual def test_shell_sort_0(self): # initialize testbed arr_under_test = Sorting() arr_under_test.sort_init(10) expected = sorted(arr_under_test.get_id()) actual = arr_under_test.shell_sort() assert expected == actual def test_heap_sort_0(self): # initialize testbed arr_under_test = Sorting() arr_under_test.sort_init(10) expected = sorted(arr_under_test.get_id()) actual = arr_under_test.heap_sort() assert expected == actual def test_merge_sort_0(self): # initialize testbed arr_under_test = Sorting() arr_under_test.sort_init(10) expected = sorted(arr_under_test.get_id()) actual = arr_under_test.merge_sort() assert expected == actual def test_quick_sort_0(self): # initialize testbed arr_under_test = Sorting() arr_under_test.sort_init(10) expected = sorted(arr_under_test.get_id()) actual = arr_under_test.quick_sort() assert expected == actual if __name__== '__main__': unittest.main() 

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

More Books

Students also viewed these Databases questions