the prompt:
Use the count sort algorithm to write a function that receives a StaticArray and returns a new StaticArray with the same content 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 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 or shell sort) will not pass the largest test case of 5,000,000 elements. For full credit, the function must be implemented with O(n+k) time complexity, where n is the number of elements and k is the range of values.
this is for an algo class so no built in functions allowed. Also not allowed to use for loops that iterate through an array, but a for loop to iterate through a range is fine.
my code:
low = min_max(arr)[0]
high = min_max(arr)[1]
arr_size = StaticArray.length(arr)
result = StaticArray(arr_size)
count_array = StaticArray(high - low + 1)
# initialize result and count_array to have 0 at all indices
for num in range(0, count_array.length()):
count_array[num] = 0
for num in range(0, result.length()):
result[num] = 0
# count the occurence of each item
num = 0
while num < arr_size:
pos = arr[num]
count_array[pos - low] += 1 # offset indexing
num += 1
# back sum
for j in range(1, count_array.length()):
count_array[j] += count_array[j - 1]
# place value in result array
num = arr_size - 1
while num >= 0:
result[count_array[arr[num]] - 1] = arr[num]
count_array[arr[num]] -= 1
num -= 1
return result
I cannot for the life of me figure out what I am doing wrong. It is throwing an out of bounds error.
the static_array.py file is a static_array class that essentially disables the iteration through an array and the use of built in methods.
class StaticArray:
"""
Implementation of Static Array Data Structure.
Implemented methods: get(), set(), length()
Any changes to this class are forbidden.
Even if you make changes to your StaticArray file and upload to Gradescope
along with your assignment, it will have no effect. Gradescope uses its
own StaticArray file (a replica of this one) and any extra submission of
a StaticArray file is ignored.
"""
def __init__(self, size: int = 10) -> None:
"""
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')
# The underscore denotes this as a private variable and
# private variables should not be accessed directly.
# Use the length() method to get the size of a StaticArray.
self._size = size
# Remember, this is a built-in list and is used here
# because Python doesn't have a fixed-size array type.
# Don't initialize variables like this in your assignments!
self._data = [None] * size
def __iter__(self) -> None:
"""
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) -> str:
"""Override string method to provide more readable output."""
return f"STAT_ARR Size: {self._size} {self._data}"
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) -> 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 length(self) -> int:
"""Return length of the array (number of elements)."""
return self._size
The exact error that is being given in the console is:
Traceback (most recent call last):
File "/Users/deleted for privacy/Desktop/CS261/assignment1/assignment1.py", line 414, in <module>
result = count_sort(arr)
^^^^^^^^^^^^^^^
File "/Users/deleted for privacy/Desktop/CS261/assignment1/assignment1.py", line 247, in count_sort
result[count_array[arr[num]] - 1] = arr[num]
~~~~~~~~~~~^^^^^^^^^^
File "/Users/deleted for privacy/Desktop/CS261/assignment1/static_array.py", line 87, in __getitem__
return self.get(index)
^^^^^^^^^^^^^^^
File "/Users/deleted for pr/Desktop/CS261/assignment1/static_array.py", line 73, in get
raise StaticArrayException('Index out of bounds')
static_array.StaticArrayException: Index out of bounds