sa_sortThe original array must be sorted, and your method does not return anything.(arr: StaticArray) -> None:Write a function that receives a StaticArray and sorts its content in non-descending order.You may assume that the input array will contain at least one element and that values stored in the array are all of the same type (either all numbers, or strings, or custom objects, but never a mix of these). You do not need to write checks for these conditions.You can implement any sort method of your choice except for Bubble Sort. This is the only method in this assignment that you are allowed to implement recursively, but you are not required to.The sort does not have to be very efficient or fast; a simple insertion or selection sort will suffice for this assignment. Duplicates in the original array can be placed in any relative order in the sorted array (in other words, your sort does not have to be ‘stable’).Your implementation must be able to sort at least 5,000 elements in a reasonable amount of time (under a minute).**RESTRICTIONS: You are NOT allowed to use ANY built-in Python data structures and/or their methods in any of your solutions. This includes built-in Python lists, dictionaries, or anything else. Variables to hold a single value or a tuple holding two/three values are allowed. It is OK to use built-in Python generator functions like range().You are NOT allowed to directly access any variables of the StaticArray class (like self._size or self._data). All work must be done by using the StaticArray class methods.***Problem:Example #1:test_cases = ([1, 10, 2, 20, 3, 30, 4, 40, 5],[‘zebra2’, ‘apple’, ‘tomato’, ‘apple’, ‘zebra1’], [(1, 1), (20, 1), (1, 20), (2, 20)], [random.randint(-10**7, 10**7) for _ in range(5_000)])for case in test_cases:arr = StaticArray(len(case))for i, value arr[i] = print(arr if sa_sort(arr) print(arr ifOutput:in enumerate(case):valuelen(case) < 50 else 'Started sorting large array')len(case) < 50 else 'Finished sorting large array')STAT_ARR Size: 9STAT_ARR Size: 9STAT_ARR Size: 5STAT_ARR Size: 5STAT_ARR Size: 4STAT_ARR Size: 4Started sorting large array Finished sorting large array[1, 10, 2, 20, 3, 30, 4, 40, 5][1, 2, 3, 4, 5, 10, 20, 30, 40]['zebra2', 'apple', 'tomato', 'apple', 'zebra1'] ['apple', 'apple', 'tomato', 'zebra1', 'zebra2'] [(1, 1), (20, 1), (1, 20), (2, 20)][(1, 1), (1, 20), (2, 20), (20, 1)]class StaticArray: """ Implementation of Static Array Data Structure Implemented methods: get(), set(), length() DO NOT CHANGE THIS CLASS IN ANY WAY YOU ARE ALLOWED TO CREATE AND USE OBJECTS OF THIS CLASS IN YOUR SOLUTION """ def __init__(self, size=10): """ Create array of given size Initialize all elements with values of None If requested size is not a positive number, raise StaticArray Exception “”” if size < 1: raise StaticArrayException('Array size must be a positive integer') self._size = size self._data = [None] * size def __iter__(self): """ Disable iterator capability for StaticArray class This means loops and aggregate functions like those shown below won't work: arr = StaticArray() for value in arr: # will not work min(arr) # will not work max(arr) # will not work sort(arr) # will not work """ return None def __str__(self): """ Return content of static array in human-readable form """ out = "STAT_ARR Size: " out += str(self._size) out += " " + str(self._data) return out def get(self, index: int): """ Return value from given index position Invalid index raises StaticArrayException """ if index < 0 or index >= self.length(): raise StaticArrayException(‘Index out of bounds’) return self._data[index] def set(self, index: int, value: object) -> None: “”” Store value at given index in the array Invalid index raises StaticArrayException “”” if index < 0 or index >= self.length(): raise StaticArrayException(‘Index out of bounds’) self._data[index] = value def __getitem__(self, index): “”” Same functionality as get() method above, but called differently These snippets of code are equivalent: arr = StaticArray() arr.set(0, ‘hello’) print(arr.get(0)) arr = StaticArray() arr[0] = ‘hello’ print(arr[0]) “”” return self.get(index) def __setitem__(self, index, value) -> None: “”” Same functionality as set() method above, but called differently These snippets of code are equivalent: arr = StaticArray() arr.set(0, ‘hello’) print(arr.get(0)) arr = StaticArray() arr[0] = ‘hello’ print(arr[0]) “”” self.set(index, value) def length(self) -> int: “”” Return length of the array (number of elements) “”” return self._sizeSKELETON CODE to work off of:def sa_sort(arr: StaticArray) -> None: “”” TODO: Write this implementation “”” passComputer ScienceEngineering & TechnologyPython Programming CS 162
