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.

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