For one of my assignment, I am asked to implement a radix sort algorithm. Here is the code that was written so far:
class RadixSort:
def __init__(self):
self.base = 7
self.bucket_list_history = []
def get_bucket_list_history(self):
return self.bucket_list_history
def sort(self, input_array):
"""
Sorts a given list using radix sort in descending order
@param input_array: list to be sorted
@returns: a sorted list
"""
self.bucket_list_history.clear() # Clear history list at the beginning of sorting
max_value = max(input_array) # Find the maximum value in the input array
exp = 1 # Current digit place
while max_value // exp > 0:
bucket_list = [[] for _ in range(self.base)] # Create empty buckets
for num in input_array:
digit = (num // exp) % self.base # Get the digit at the current place value
bucket_list[digit].append(num) # Assign the number to the respective bucket
self._add_bucket_list_to_history(bucket_list) # Add the bucket list snapshot to history
input_array = [] # Clear the input array
for bucket in bucket_list:
input_array.extend(bucket) # Reconstruct the input array from the buckets
exp *= self.base # Move to the next digit place
return input_array[::-1] # Return the sorted list in descending order
# TODO
# Helper functions
def _add_bucket_list_to_history(self, bucket_list):
"""
This method creates a snapshot (clone) of the bucket list and adds it to the bucket list history.
@param bucket_list: current bucket list after assigning elements to be sorted to the buckets
@param iteration: current iteration index
"""
print(bucket_list)
arr_clone = []
for i in range(0, len(bucket_list)):
arr_clone.append([])
for j in bucket_list[i]:
arr_clone[i].append(j)
self.bucket_list_history.append(arr_clone)
I was able to successfully sort the array in the end, however, I continuously get these errors:
[[21, 0], [], [2123], [10216, 402, 10123515], [164504, 5142], [33, 614, 21523], [6411]]
[[0], [402, 164504, 21523], [2123, 10123515], [21, 10216, 614], [33], [6411], [5142]]
[[0, 21, 33], [402, 2123], [], [], [164504, 10123515, 6411], [21523, 10216, 614], [5142]]
[[0, 21, 33, 5142], [402, 10216, 614], [10123515], [164504], [6411], [], [2123, 21523]]
[[0, 21, 33, 402, 614, 2123], [21523], [5142, 10123515, 6411], [], [10216], [164504], []]
[[0, 21, 33, 402, 614, 2123, 5142, 10123515, 6411, 10216], [21523], [164504], [], [], [], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523], [164504], [10123515], [], [], [], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523, 164504], [], [], [], [], [10123515], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523, 164504], [10123515], [], [], [], [], []]
Radix sort of input array [33, 614, 10216, 2123, 21523, 164504, 5142, 402, 6411, 21, 10123515, 0] failed in iteration 1 on bucket 0 because of wrong size
2 != 1
Expected :1
Actual :2
<Click to see difference>
Traceback (most recent call last):
File "/home/sakops/Schreibtisch/artificial intelligence/algos and datastructures/uebung/sorting/code/radix_sort/unit_test_radix_sort.py", line 97, in test_radix_sort_bucket_lists_iteration_1
self.assertEqual(1, len(bucket_list_history[it_idx][0]), err_msg + " 0 because of wrong size")
AssertionError: 1 != 2 : Radix sort of input array [33, 614, 10216, 2123, 21523, 164504, 5142, 402, 6411, 21, 10123515, 0] failed in iteration 1 on bucket 0 because of wrong size
[[21, 0], [], [2123], [10216, 402, 10123515], [164504, 5142], [33, 614, 21523], [6411]]
[[0], [402, 164504, 21523], [2123, 10123515], [21, 10216, 614], [33], [6411], [5142]]
[[0, 21, 33], [402, 2123], [], [], [164504, 10123515, 6411], [21523, 10216, 614], [5142]]
[[0, 21, 33, 5142], [402, 10216, 614], [10123515], [164504], [6411], [], [2123, 21523]]
[[0, 21, 33, 402, 614, 2123], [21523], [5142, 10123515, 6411], [], [10216], [164504], []]
[[0, 21, 33, 402, 614, 2123, 5142, 10123515, 6411, 10216], [21523], [164504], [], [], [], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523], [164504], [10123515], [], [], [], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523, 164504], [], [], [], [], [10123515], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523, 164504], [10123515], [], [], [], [], []]
Radix sort of input array [33, 614, 10216, 2123, 21523, 164504, 5142, 402, 6411, 21, 10123515, 0] failed in iteration 2 on bucket 0 because of wrong size
1 != 0
Expected :0
Actual :1
<Click to see difference>
Traceback (most recent call last):
File "/home/sakops/Schreibtisch/artificial intelligence/algos and datastructures/uebung/sorting/code/radix_sort/unit_test_radix_sort.py", line 135, in test_radix_sort_bucket_lists_iteration_2
self.assertEqual(0, len(bucket_list_history[it_idx][0]), err_msg + " 0 because of wrong size")
AssertionError: 0 != 1 : Radix sort of input array [33, 614, 10216, 2123, 21523, 164504, 5142, 402, 6411, 21, 10123515, 0] failed in iteration 2 on bucket 0 because of wrong size
[[21, 0], [], [2123], [10216, 402, 10123515], [164504, 5142], [33, 614, 21523], [6411]]
[[0], [402, 164504, 21523], [2123, 10123515], [21, 10216, 614], [33], [6411], [5142]]
[[0, 21, 33], [402, 2123], [], [], [164504, 10123515, 6411], [21523, 10216, 614], [5142]]
[[0, 21, 33, 5142], [402, 10216, 614], [10123515], [164504], [6411], [], [2123, 21523]]
[[0, 21, 33, 402, 614, 2123], [21523], [5142, 10123515, 6411], [], [10216], [164504], []]
[[0, 21, 33, 402, 614, 2123, 5142, 10123515, 6411, 10216], [21523], [164504], [], [], [], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523], [164504], [10123515], [], [], [], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523, 164504], [], [], [], [], [10123515], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523, 164504], [10123515], [], [], [], [], []]
Radix sort of input array [33, 614, 10216, 2123, 21523, 164504, 5142, 402, 6411, 21, 10123515, 0] failed in iteration 3 on bucket 0 because of wrong size
3 != 1
Expected :1
Actual :3
<Click to see difference>
Traceback (most recent call last):
File "/home/sakops/Schreibtisch/artificial intelligence/algos and datastructures/uebung/sorting/code/radix_sort/unit_test_radix_sort.py", line 172, in test_radix_sort_bucket_lists_iteration_3
self.assertEqual(1, len(bucket_list_history[it_idx][0]), err_msg + " 0 because of wrong size")
AssertionError: 1 != 3 : Radix sort of input array [33, 614, 10216, 2123, 21523, 164504, 5142, 402, 6411, 21, 10123515, 0] failed in iteration 3 on bucket 0 because of wrong size
[[21, 0], [], [2123], [10216, 402, 10123515], [164504, 5142], [33, 614, 21523], [6411]]
[[0], [402, 164504, 21523], [2123, 10123515], [21, 10216, 614], [33], [6411], [5142]]
[[0, 21, 33], [402, 2123], [], [], [164504, 10123515, 6411], [21523, 10216, 614], [5142]]
[[0, 21, 33, 5142], [402, 10216, 614], [10123515], [164504], [6411], [], [2123, 21523]]
[[0, 21, 33, 402, 614, 2123], [21523], [5142, 10123515, 6411], [], [10216], [164504], []]
[[0, 21, 33, 402, 614, 2123, 5142, 10123515, 6411, 10216], [21523], [164504], [], [], [], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523], [164504], [10123515], [], [], [], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523, 164504], [], [], [], [], [10123515], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523, 164504], [10123515], [], [], [], [], []]
Radix sort of input array [33, 614, 10216, 2123, 21523, 164504, 5142, 402, 6411, 21, 10123515, 0] failed in iteration 4 on bucket 0 because of wrong size
4 != 1
Expected :1
Actual :4
<Click to see difference>
Traceback (most recent call last):
File "/home/sakops/Schreibtisch/artificial intelligence/algos and datastructures/uebung/sorting/code/radix_sort/unit_test_radix_sort.py", line 209, in test_radix_sort_bucket_lists_iteration_4
self.assertEqual(1, len(bucket_list_history[it_idx][0]), err_msg + " 0 because of wrong size")
AssertionError: 1 != 4 : Radix sort of input array [33, 614, 10216, 2123, 21523, 164504, 5142, 402, 6411, 21, 10123515, 0] failed in iteration 4 on bucket 0 because of wrong size
[[21, 0], [], [2123], [10216, 402, 10123515], [164504, 5142], [33, 614, 21523], [6411]]
[[0], [402, 164504, 21523], [2123, 10123515], [21, 10216, 614], [33], [6411], [5142]]
[[0, 21, 33], [402, 2123], [], [], [164504, 10123515, 6411], [21523, 10216, 614], [5142]]
[[0, 21, 33, 5142], [402, 10216, 614], [10123515], [164504], [6411], [], [2123, 21523]]
[[0, 21, 33, 402, 614, 2123], [21523], [5142, 10123515, 6411], [], [10216], [164504], []]
[[0, 21, 33, 402, 614, 2123, 5142, 10123515, 6411, 10216], [21523], [164504], [], [], [], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523], [164504], [10123515], [], [], [], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523, 164504], [], [], [], [], [10123515], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523, 164504], [10123515], [], [], [], [], []]
Radix sort of input array [33, 614, 10216, 2123, 21523, 164504, 5142, 402, 6411, 21, 10123515, 0] failed in iteration 5 on bucket 0 because of wrong size
6 != 1
Expected :1
Actual :6
<Click to see difference>
Traceback (most recent call last):
File "/home/sakops/Schreibtisch/artificial intelligence/algos and datastructures/uebung/sorting/code/radix_sort/unit_test_radix_sort.py", line 246, in test_radix_sort_bucket_lists_iteration_5
self.assertEqual(1, len(bucket_list_history[it_idx][0]), err_msg + " 0 because of wrong size")
AssertionError: 1 != 6 : Radix sort of input array [33, 614, 10216, 2123, 21523, 164504, 5142, 402, 6411, 21, 10123515, 0] failed in iteration 5 on bucket 0 because of wrong size
[[21, 0], [], [2123], [10216, 402, 10123515], [164504, 5142], [33, 614, 21523], [6411]]
[[0], [402, 164504, 21523], [2123, 10123515], [21, 10216, 614], [33], [6411], [5142]]
[[0, 21, 33], [402, 2123], [], [], [164504, 10123515, 6411], [21523, 10216, 614], [5142]]
[[0, 21, 33, 5142], [402, 10216, 614], [10123515], [164504], [6411], [], [2123, 21523]]
[[0, 21, 33, 402, 614, 2123], [21523], [5142, 10123515, 6411], [], [10216], [164504], []]
[[0, 21, 33, 402, 614, 2123, 5142, 10123515, 6411, 10216], [21523], [164504], [], [], [], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523], [164504], [10123515], [], [], [], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523, 164504], [], [], [], [], [10123515], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523, 164504], [10123515], [], [], [], [], []]
Radix sort of input array [33, 614, 10216, 2123, 21523, 164504, 5142, 402, 6411, 21, 10123515, 0] failed in iteration 6 on bucket 0 because of wrong size
10 != 0
Expected :0
Actual :10
<Click to see difference>
Traceback (most recent call last):
File "/home/sakops/Schreibtisch/artificial intelligence/algos and datastructures/uebung/sorting/code/radix_sort/unit_test_radix_sort.py", line 283, in test_radix_sort_bucket_lists_iteration_6
self.assertEqual(0, len(bucket_list_history[it_idx][0]), err_msg + " 0 because of wrong size")
AssertionError: 0 != 10 : Radix sort of input array [33, 614, 10216, 2123, 21523, 164504, 5142, 402, 6411, 21, 10123515, 0] failed in iteration 6 on bucket 0 because of wrong size
[[21, 0], [], [2123], [10216, 402, 10123515], [164504, 5142], [33, 614, 21523], [6411]]
[[0], [402, 164504, 21523], [2123, 10123515], [21, 10216, 614], [33], [6411], [5142]]
[[0, 21, 33], [402, 2123], [], [], [164504, 10123515, 6411], [21523, 10216, 614], [5142]]
[[0, 21, 33, 5142], [402, 10216, 614], [10123515], [164504], [6411], [], [2123, 21523]]
[[0, 21, 33, 402, 614, 2123], [21523], [5142, 10123515, 6411], [], [10216], [164504], []]
[[0, 21, 33, 402, 614, 2123, 5142, 10123515, 6411, 10216], [21523], [164504], [], [], [], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523], [164504], [10123515], [], [], [], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523, 164504], [], [], [], [], [10123515], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523, 164504], [10123515], [], [], [], [], []]
Radix sort of input array [33, 614, 10216, 2123, 21523, 164504, 5142, 402, 6411, 21, 10123515, 0] failed in iteration 7 on bucket 0 because of wrong size
10 != 0
Expected :0
Actual :10
<Click to see difference>
Traceback (most recent call last):
File "/home/sakops/Schreibtisch/artificial intelligence/algos and datastructures/uebung/sorting/code/radix_sort/unit_test_radix_sort.py", line 320, in test_radix_sort_bucket_lists_iteration_7
self.assertEqual(0, len(bucket_list_history[it_idx][0]), err_msg + " 0 because of wrong size")
AssertionError: 0 != 10 : Radix sort of input array [33, 614, 10216, 2123, 21523, 164504, 5142, 402, 6411, 21, 10123515, 0] failed in iteration 7 on bucket 0 because of wrong size
[[21, 0], [], [2123], [10216, 402, 10123515], [164504, 5142], [33, 614, 21523], [6411]]
[[0], [402, 164504, 21523], [2123, 10123515], [21, 10216, 614], [33], [6411], [5142]]
[[0, 21, 33], [402, 2123], [], [], [164504, 10123515, 6411], [21523, 10216, 614], [5142]]
[[0, 21, 33, 5142], [402, 10216, 614], [10123515], [164504], [6411], [], [2123, 21523]]
[[0, 21, 33, 402, 614, 2123], [21523], [5142, 10123515, 6411], [], [10216], [164504], []]
[[0, 21, 33, 402, 614, 2123, 5142, 10123515, 6411, 10216], [21523], [164504], [], [], [], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523], [164504], [10123515], [], [], [], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523, 164504], [], [], [], [], [10123515], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523, 164504], [10123515], [], [], [], [], []]
Radix sort of input array [33, 614, 10216, 2123, 21523, 164504, 5142, 402, 6411, 21, 10123515, 0] failed in iteration 8 on bucket 0 because of wrong size
11 != 0
Expected :0
Actual :11
<Click to see difference>
Traceback (most recent call last):
File "/home/sakops/Schreibtisch/artificial intelligence/algos and datastructures/uebung/sorting/code/radix_sort/unit_test_radix_sort.py", line 357, in test_radix_sort_bucket_lists_iteration_8
self.assertEqual(0, len(bucket_list_history[it_idx][0]), err_msg + " 0 because of wrong size")
AssertionError: 0 != 11 : Radix sort of input array [33, 614, 10216, 2123, 21523, 164504, 5142, 402, 6411, 21, 10123515, 0] failed in iteration 8 on bucket 0 because of wrong size
[[], [], [], [], [4, 4, 4], [], [111]]
[[4, 4, 4], [111], [], [], [], [], []]
[[4, 4, 4], [], [111], [], [], [], []]
[[0], [15], [], [234], [5562], [12], []]
[[0], [12], [15], [5562], [], [234], []]
[[0, 12, 15], [5562], [], [], [234], [], []]
[[0, 12, 15, 234], [], [5562], [], [], [], []]
[[0, 12, 15, 234], [], [5562], [], [], [], []]
[[21, 0], [], [2123], [10216, 402, 10123515], [164504, 5142], [33, 614, 21523], [6411]]
[[0], [402, 164504, 21523], [2123, 10123515], [21, 10216, 614], [33], [6411], [5142]]
[[0, 21, 33], [402, 2123], [], [], [164504, 10123515, 6411], [21523, 10216, 614], [5142]]
[[0, 21, 33, 5142], [402, 10216, 614], [10123515], [164504], [6411], [], [2123, 21523]]
[[0, 21, 33, 402, 614, 2123], [21523], [5142, 10123515, 6411], [], [10216], [164504], []]
[[0, 21, 33, 402, 614, 2123, 5142, 10123515, 6411, 10216], [21523], [164504], [], [], [], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523], [164504], [10123515], [], [], [], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523, 164504], [], [], [], [], [10123515], []]
[[0, 21, 33, 402, 614, 2123, 5142, 6411, 10216, 21523, 164504], [10123515], [], [], [], [], []]
[[], [1], [], [], [], [], []]
Here is the test code:
def deduct_pts(value): global points points = points - value if points < 0: points = 0
def resolve_amount_of_pts_to_deduct(argument): pool = { "test_radix_sort_result": 3, "test_radix_sort_result_one_element": 1, "test_radix_sort_equal_elements": 1, "test_radix_sort_presorted_array": 1, "test_radix_sort_bucket_lists_iteration_1": 0.75, "test_radix_sort_bucket_lists_iteration_2": 0.75, "test_radix_sort_bucket_lists_iteration_3": 0.75, "test_radix_sort_bucket_lists_iteration_4": 0.75, "test_radix_sort_bucket_lists_iteration_5": 0.75, "test_radix_sort_bucket_lists_iteration_6": 0.75, "test_radix_sort_bucket_lists_iteration_7": 0.75, "test_radix_sort_bucket_lists_iteration_8": 0.75, } # resolve the pts to deduct from pool return pool.get(argument, 0)
class UnitTestTemplate(unittest.TestCase): def setUp(self): pass
####################################################
# Definition of test cases
####################################################
def test_radix_sort_result(self):
r = RadixSort()
result = r.sort(test_array.copy())
test_array.sort(reverse=True)
for i in range(0, len(test_array)):
self.assertEqual(test_array[i], result[i],
f"ERROR: sort with input sequence {test_array} failed at index {i}: {result}")
def test_radix_sort_result_one_element(self):
r = RadixSort()
result = r.sort([1])
self.assertEqual(1, result[0], f"ERROR: sort with input sequence [1] failed at index 1: {result}")
self.assertEqual(1, len(result), f"ERROR: sort with input sequence [1] failed because of incorrect size")
def test_radix_sort_equal_elements(self):
r = RadixSort()
result = r.sort(test_array_equals.copy())
test_array_equals.sort(reverse=True)
for i in range(0, len(test_array_equals)):
self.assertEqual(test_array_equals[i], result[i],
f"ERROR: sort with input sequence {test_array_equals} failed at index {i}: {result}")
def test_radix_sort_presorted_array(self):
r = RadixSort()
result = r.sort(test_array_presorted.copy())
test_array_presorted.sort(reverse=True)
for i in range(0, len(test_array_presorted)):
self.assertEqual(test_array_presorted[i], result[i],
f"ERROR: sort with input sequence {test_array_presorted} failed at index {i}: {result}")
def test_radix_sort_bucket_lists_iteration_1(self):
it_idx = 0
err_msg = f"Radix sort of input array {test_array} failed in iteration {it_idx + 1} on bucket"
r = RadixSort()
r.sort(test_array.copy())
bucket_list_history = r.get_bucket_list_history()
self.assertTrue(len(bucket_list_history) > 0, "ERROR: bucket_list_history is empty")
self.assertTrue(len(bucket_list_history[it_idx]) >= 7,
f"ERROR: bucket_list_history[{it_idx}] is of wrong size, must contain 7 buckets")
self.assertEqual(1, len(bucket_list_history[it_idx][0]), err_msg + " 0 because of wrong size")
self.assertTrue(10216 in bucket_list_history[it_idx][0], err_msg + " 0 because of missing element 10216")
self.assertEqual(1, len(bucket_list_history[it_idx][1]), err_msg + " 1 because of wrong size")
self.assertTrue(10123515 in bucket_list_history[it_idx][1], err_msg + " 1 because of missing element 10123515")
self.assertEqual(2, len(bucket_list_history[it_idx][2]), err_msg + " 2 because of wrong size")
self.assertTrue(614 in bucket_list_history[it_idx][2], err_msg + " 2 because of missing element 614")
self.assertTrue(164504 in bucket_list_history[it_idx][2], err_msg + " 2 because of missing element 164504")
self.assertEqual(3, len(bucket_list_history[it_idx][3]), err_msg + " 3 because of wrong size")
self.assertTrue(33 in bucket_list_history[it_idx][3], err_msg + " 3 because of missing element 33")
self.assertTrue(2123 in bucket_list_history[it_idx][3], err_msg + " 3 because of missing element 2123")
self.assertTrue(21523 in bucket_list_history[it_idx][3], err_msg + " 3 because of missing element 21523")
self.assertEqual(2, len(bucket_list_history[it_idx][4]), err_msg + " 4 because of wrong size")
self.assertTrue(5142 in bucket_list_history[it_idx][4], err_msg + " 4 because of missing element 5142")
self.assertTrue(402 in bucket_list_history[it_idx][4], err_msg + " 4 because of missing element 402")
self.assertEqual(2, len(bucket_list_history[it_idx][5]), err_msg + " 5 because of wrong size")
self.assertTrue(6411 in bucket_list_history[it_idx][5], err_msg + " 5 because of missing element 6411")
self.assertTrue(21 in bucket_list_history[it_idx][5], err_msg + " 5 because of missing element 21")
self.assertEqual(1, len(bucket_list_history[it_idx][6]), err_msg + " 6 because of wrong size")
self.assertTrue(0 in bucket_list_history[it_idx][6], err_msg + " 6 because of missing element 0")
print(len(bucket_list_history[it_idx][6]))
Since the test code hase over 300 lines, I posted the first 100
For troubleshooting purposes I print out each iteration and apparently my bucket is continuously of the wrong size, any idea on how to resolve this?
Thank you