count_sort (arr: StaticArray) -> StaticArray: Write a function that…

  

count_sort (arr: StaticArray) -> StaticArray: Write a function that… count_sort(arr: StaticArray) -> StaticArray:Write a function that receives a StaticArray and returns a new StaticArray with the samecontent sorted in non-ascending order. The original array must not be modified.You may assume that the input array will contain at least one element and that all elements will be integers in the range [-109, 109]. It is guaranteed that the difference between the maximum and minimum values in the input will be less than 1,000. You do not need to write checks for these conditions.Implement a FAST solution that can sort at least 5,000,000 elements in a reasonable amount of time (under a minute). Note that using a traditional sorting algorithm (even a fast sorting algorithm like merge sort, shell sort, etc.) will not pass the largest test case of 5M elements.HINT: The name of the algorithm may seem confusing if not deceptive – it’s really not a sort as you might commonly view one. While the end result is a sorted version of the original contents, the means by which we arrive at it may be a bit different.For example, a sorted array can be generated if you know what values are present and how many times they occur. Note that you’ve already written code in this assignment that will help you determine how many different values could be in the array as well as the range of possible values present.Example #1:test_cases = ([1, 2, 4, 3, 5], [5, 4, 3, 2, 1], [0, -5, -3, -4, -2, -1, 0],[-3, -2, -1, 0, 1, 2, 3], [1, 2, 3, 4, 3, 2, 1, 5, 5, 2, 3, 1], [10100, 10721, 10320, 10998], [-100320, -100450, -100999, -100001],)for case in test_cases:arr = StaticArray(len(case)) for i, value in enumerate(case):arr[i] = valueprint(arr if len(case) < 50 else 'Started sorting large array') result = count_sort(arr)print(result if len(case) < 50 else 'Finished sorting large array')Page 15 of 16CS261 Data StructuresAssignment 1: Python Fundamentals ReviewOutput:STAT_ARR Size: 5 [1, 2, 4, 3, 5]STAT_ARR Size: 5 [5, 4, 3, 2, 1]STAT_ARR Size: 5 [5, 4, 3, 2, 1]STAT_ARR Size: 5 [5, 4, 3, 2, 1]STAT_ARR Size: 7 [0, -5, -3, -4,STAT_ARR Size: 7 [0, 0, -1, -2, -3, -4, -5]STAT_ARR Size: 7 [-3, -2, -1, 0, 1, 2, 3]STAT_ARR Size: 7 [3, 2, 1, 0, -1, -2, -3]STAT_ARR Size: 12 [1, 2, 3, 4, 3, 2, 1, 5, 5, 2, 3, 1] STAT_ARR Size: 12 [5, 5, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1] STAT_ARR Size: 4 [10100, 10721, 10320, 10998] STAT_ARR Size: 4 [10998, 10721, 10320, 10100] STAT_ARR Size: 4 [-100320, -100450, -100999, -100001] STAT_ARR Size: 4 [-100001, -100320, -100450, -100999]Example #2:array_size = 5_000_000min_val = random.randint(-10**9, 10**9 - 998)max_val = min_val + 998case = [random.randint(min_val, max_val) for _ in range(array_size)] arr = StaticArray(len(case))for i, value in enumerate(case):arr[i] = valueprint(f'Started sorting large array of {array_size} elements') result = count_sort(arr)print(f'Finished sorting large array of {array_size} elements')Output:Started sorting large array of 5000000 elements Finished sorting large array of 5000000 elements**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._size skeleton code: def count_sort(arr: StaticArray) -> StaticArray:    “””    TODO: Write this implementation    “””    pass Computer Science Engineering & Technology Python Programming CS 161

Don't use plagiarized sources. Get Your Custom Essay on
count_sort (arr: StaticArray) -> StaticArray: Write a function that…
Just from $13/Page
Order Essay
  

Leave a Reply

Your email address will not be published.

Related Post

Open chat
💬 Need help?
Hello 👋
Can we help you?