Cannot high-speed sorting work with Ruby?

Question

I learned a peaked guide, and it really helped me pick up the language pretty quickly. After that, I started solving some coding puzzles using Ruby. It just helps many get used to the language that I feel.

I'm stuck with one such mystery. I solved it very easily, as it is pretty straight forward, but the decision is rejected (by the host site) with the error "Time Exceded"! I know that Ruby cannot compete with C / C ++ speed, but should it be able to answer a tiny puzzle on a website that makes decisions in Ruby?

the puzzle is just a normal view.

This is my decision

array ||= []
gets.to_i.times do
  array << gets
end
puts array.sort

My question is: is there any other way to achieve high-speed sorting with Ruby? I use the basic one Array#sorthere, but is there a way to do this faster, although that means it has more lines of code?

Answer 1

I solved this problem, and let me tell you, using an algorithm nlognto go through, which is almost impossible if you are not using a very optimized version of C / Assembly.

You need to learn other algorithms. Hint: O (n) The algorithm will do the trick even for ruby.

Good luck.

Answer 2

You sort strings when you should sort ints. Try:

array << gets.to_i

Answer 3

If there is no need to repeat duplicate values:

h = {}
gets.to_i.times{h[gets.to_i] = true}
(0..100000).each{|n| puts(n) if h[n]}

If duplicate values ​​need to be repeated:

h = Hash.new(0)
gets.to_i.times{h[gets.to_i] += 1}
(0..100000).each{|n| h[n].times{puts(n)}}