## DEV Community

Arjun Rajkumar

Posted on • Updated on

# Write better code: Day 4 - Sorted scores

This post originally appeared on Arjun Rajkumar's blog. Arjun is a web developer based in Bangalore, India.

--

### Day 4: Question 2

Write a method that takes:

an array of unsorted_scores and the highest_possible_score in the game
and returns a sorted array of scores in less than O(nlgn) time.

``````For example:
unsorted_scores = [37, 89, 41, 65, 91, 53]
HIGHEST_POSSIBLE_SCORE = 100

sort_scores(unsorted_scores, HIGHEST_POSSIBLE_SCORE)
# returns [91, 89, 65, 53, 41, 37]
``````

We’re defining nn as the number of unsorted_scores because we’re expecting the number of players to keep climbing.

And, we'll treat highest_possible_score as a constant instead of factoring it into our big O time and space costs because the highest possible score isn’t going to change. Even if we do redesign the game a little, the scores will stay around the same order of magnitude.

-

This problem is from InterviewCake.

Arjun Rajkumar

The problem asked to do this in lesser than O[nlogn] time.
Counting sort has O[n] time, so applied that straight.

``````def sort_scores(unsorted_scores, highest_score)
counts = [0] * (highest_score + 1)

unsorted_scores.each do |score|
counts[score] += 1
end

sorted_score = []
highest_score.downto(1).each do |score|
count = counts[score]

(0...count).each do |i|
sorted_score << score
end
end

sorted_score
end
``````