You are given with an unsorted_ints list and max_int_limit of the list. Sort the int list in time O(n).
We can treat the max_int_limit as a constant. By doing this, we are assuming that the max_int_limit should not be volatile and be fixed for whatever values we have in the unsorted_ints list.
We will be using a counting sort.
1. We will count the unsorted_ints list in a seperate list
2. We will traverse through it in inorder step to retrieve values from the lowest int. This should automatically sort out the list.
How it works
Code
def sort_ints(unsorted_ints, max_int_limit):
# Sort the ints in O(n) time
int_count = [0] * (max_int_limit+1)
# Initialize final sorted list
sorted_ints = []
# Populate int_count
for int in unsorted_ints:
int_count[int] += 1
# Traversing through int_count to retrieve ints in inorder
for int in range(max_int_limit+1, 0, -1):
# Iterative over number of ints in the list
for repeat in range(int_count[int-1]):
# Add the int to sorted list
sorted_ints.append(int-1)
return sorted_ints
Time Complexity Analysis
Assume that n is the number of ints in unsorted_ints list and k is the max_int_limit
Creating int_count list - O(n)
Iterating over int_count list and mutiple iteration over repeated number - O(n+k)
However, if we consider O(k) to be constant, then the time complexity of this function will be
Space Complexity Analysis
The int_count list will take up O(k) and the sorted_int_list will take up O(n). Therefore, it will be O(n+k). Yet again, if we consider O(k) to be constant, then the space complexity of this function will be .
Limitations
1. Because we tried to reduce the runtime of this function, we had to use up extra O(k). This takes up a lot of space. We could probably reduce this by sacrificing a bit of our time efficiency.