Top scores
Write a function that takes:
- a list of unsorted_scores
- the highest_possible_score in the game
and returns a sorted list of scores in less than O(n*log n) time.
Example
i/p: [3,4,3,2,4,3,5,6,7,5,6,7,1,2,8,9,9]
o/p: [1,2,2,3,3,3,4,4,5,5,6,6,7,7,8,9,9]
Solution
- Hint: To get better than O(nlogn) performance use counting sort
- Another indication to use counting sort is, we're provided with the highest possible score, which can be used to created a counting array and keep track of element counts
Code
def top_scores(scores, max_score)
# Count number of times a score has been seen
scores_count = [0] * max_score
# Count
scores.each do |score|
scores_count[score] += 1
end
sorted_scores = []
# Print in sorted order
scores_count.each_with_index do |count, i|
count.times { sorted_scores << i }
end
sorted_scores
end
Time complexity
- O(n) to count
- O(n) to construct the sorted result
- This is less than ideal since we are using up extra space for storing score counts, but if the highest_possible_score is not a very large number, then its a great trade-off to achieve O(n) sorting time.