Ruby Interrupted Bubble Sort

Question

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

Answer 1

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.

• Caridorc: 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: 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!
• Flambino: @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.
• Caridorc: 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 :)
• John Halbert: @Flambino - thanks for the detailed response. Even with the changes you suggest the test is failing for taking longer than 10 seconds to run.

Answer 2

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(" ");

• John Halbert: Thanks. Will it execute faster as well?
• Caridorc: @JohnHalbert Probable, built-ins are written in C, and are very fast to use.