# Ruby Interrupted Bubble Sort

Working through CodeEval's Interrupted Bubble Sort, I have a working algorithm, but there's a speed issue. I'm trying to do this with Ruby and I keep getting an error that it's timing out after 10 seconds. I'm not sure what else I could be doing here to speed things up.

def bubble(arr, interrupt)

i = 0
while i < interrupt
for x in 1..arr.length-1
if arr[x-1] > arr[x]
arr[x-1], arr[x] = arr[x], arr[x-1]
end
end
i += 1
end

end

File.open(ARGV[0]).each_line do |line|

line = line.chomp.split(" ");
interrupt = line.pop.to_i
line.pop

line.map do |x| x = x.to_i end
bubble(line, interrupt)
puts line.join(" ")

end


There shouldn't be a speed issue (so far as I can tell), but there is an outright bug:

line.map do |x| x = x.to_i end


You're not storing the result of the map, you're just throwing it away. So line doesn't change, and you end up comparing the elements lexicographically, i.e. as strings. So "48" ends up being less "5" and such.

Other notes:

• The Ruby convention is to use 2 spaces for indentation. Not 4 spaces, not tabs.

• You don't need semicolons.

• When writing a single line block, use {..} instead of do..end

• When simply invoking the same single method on all elements in an array, you can use a shortcut: line.map(&:to_i)

• You can exclude the last element in a range with 3 dots (...), so 1..arr.length-1 becomes just 1...arr.length

With that and a few other things you get:

def bubble(array, iterations)
iterations.times do
(1...array.length).each do |i|
if array[i-1] > array[i]
array[i-1], array[i] = array[i], array[i-1]
end
end
end
end

File.open(ARGV[0]).each_line do |line|
line = line.chomp.split(" ")
iterations = line.last.to_i

values = line[0...-2].map(&:to_i)
bubble(values, iterations)

puts values.join(" ")
end


Now, this is just a challenge, but for production code, I'd avoid the side-effects of bubble, and return a new array instead. But that's a different story.

Edit: Since it's still too slow, maybe it's because the input is crafted to trick you. For instance, a line that calls for billions of iterations on a relatively small set of values will, with the code above, cause waaay too many pointless iterations. I.e. the list may be sorted already, but the algorithm will keep loop through it the specified number of times.

A pretty simple solution would be something like:

def bubble(array, iterations)
iterations.times do
sorted = true
(1...array.length).each do |i|
if array[i-1] > array[i]
sorted = false
array[i-1], array[i] = array[i], array[i-1]
end
end
break if sorted
end
end


Additionally, you can skip stuff by checking the number of iterations before calling bubble. If it's zero, there's no need for the map:

File.open(ARGV[0]).each_line do |line|
line = line.chomp.split(" ")
iterations = line.last.to_i

unless iterations.zero?
values = line[0...-2].map(&:to_i)
bubble(values, iterations)
end

puts values.join(" ")
end


Now of course it may just be that the input is just huge, and Ruby isn't the fastest thing. But one has to assume that the challenge can actually be solved.

• Our answers are similar, but yours is more in-depth, you are missing a ! on your map as it should work in-place. I really like the point about avoiding side-effects – Caridorc Sep 1 '15 at 17:38
• Edit: the ! Is not missing as the map does not work in place, I misread :). Still a literal bug-fix would use the in-place map! – Caridorc Sep 1 '15 at 17:40
• @Caridorc Yeah, you can just use the map-bang method instead. I just tend to avoid those. I prefer to assign stuff to a new variable since it's been transformed; keep input and output separate, so to speak. On the other hand, the code already uses pop, so the "damage" is done, I suppose. Meh, I'll change that, actually. And yeah, the answers are similar. I was writing mine in an editor, so I didn't see yours until I'd already written it. – Flambino Sep 1 '15 at 17:52
• I also tend to avoid in-place operations, if memory-usage were such a concern, I would not be using Ruby in the first place. About the similarity, great minds think alike :) – Caridorc Sep 1 '15 at 17:54
• @Flambino - thanks for the detailed response. Even with the changes you suggest the test is failing for taking longer than 10 seconds to run. – John Halbert Sep 2 '15 at 9:01

while with manual incrementing should be avoided at all costs in Ruby, the following reads much more easily:

interrupt.times do
for x in 1..arr.length-1
if arr[x-1] > arr[x]
arr[x-1], arr[x] = arr[x], arr[x-1]
end
end
end


You can simplify this line:

line.map!(&:to_i)


As ! Makes methods work in place. &: converts a method to a block.

(minor) remove that semicolon, it is really weird:

line = line.chomp.split(" ");

• Thanks. Will it execute faster as well? – John Halbert Sep 1 '15 at 17:27
• @JohnHalbert Probable, built-ins are written in C, and are very fast to use. – Caridorc Sep 1 '15 at 17:28