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.

-

If you want to follow along, feel free to post your answers in the comment.

My answers are in the comments.
This problem is from InterviewCake.

Comments

[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