7
\$\begingroup\$

For practice, I tried implementing Bubble sort in Ruby. I wasn't very sure how nested for loops would look like in Ruby. Is this the 'right way' to do this in Ruby? I found this question, but it looks much more complicated with stacks.

def bubble_sort(list)
  n = list.length
  n.downto(2) do |i|
    0.upto(i-2) do |j|
      if list[j] > list[j+1]
        list[j],list[j+1] = list[j+1],list[j]
      end
    end
  end
  puts list
end

This is the code I wrote in Python which I then translated into Ruby code above.

def bubbleSort(alist):
    n = len(alist)
    for i in range(n, 1, -1):
        for j in range(i-1):
            if alist[j] > alist[j+1] :
                alist[j],alist[j+1] = alist[j+1],alist[j]
\$\endgroup\$
  • \$\begingroup\$ This is more complicated than needed for bubblesort. You can just loop for i in range(n-1) repeatedly until nothing gets swapped. You get the same O(N^2) average and worst case, and it means you don't need the range(n, 1, -1), which is the easiest place to introduce bugs into your implementation. (The worst case is worse by a constant factor of 2 that way, but who cares? If you really want to trade simplicity for efficiency, why are you using bubblesort?) \$\endgroup\$ – abarnert May 17 '15 at 7:11
3
\$\begingroup\$

A significant difference between your Python and Ruby implementations is that the Ruby one prints the sorted list at the end. It shouldn't, just like the Python version doesn't. The function should do just one thing, in this example just sort.

Also, I suggest to putting a space after commas separating variable lists, like this:

    list[j], list[j+1] = list[j+1], list[j]

I don't know much Ruby, but I don't think a bubble sort can get any better than this. You are using nice Ruby-like idiomatic expressions like downto and upto, and the rest is clear, straight code. Anything more clever than this would be too clever for the purpose, in my opinion.

A tiny final remark about the Python implementation: snake_case is recommended for function names instead of camelCase.

\$\endgroup\$
0
\$\begingroup\$

I loved the question, but didn't think to answer it until just a bit before I went to bed...

...So here are my two takes on the bubble sort code, including testing code.

I'll update the answer with more info after I slept a bit, but it should be quite straight forward.

I iterate the array using a numerical index until there is nothing to sort, at which point I break from the iterations. In one version I use the sorted variable, while in the next I use a temporary array (allowing me to make it a one-line implementation).

a = Array.new(100) {Random.rand 1000}


def bubble_sort!(array)
    sorted = false
    until sorted
        sorted = true
        (array.length-1).times { |i|  (sorted, array[i], array[i+1] = false, array[i+1], array[i]) if array[i] > array[i+1] }
    end 
end


def bubble_sort!(array)
    break if ((array.length-1).times.with_object([]) { |i, r| (r << (array[i], array[i+1] = array[i+1], array[i])) if array[i] > array[i+1] }).empty? while true
end


#testing

def array_sorted?(array)
    r = (array.length-1).times.with_object([]) { |i, r| (array[i] > array[i+1]) ? (r << "failed at #{i}!!!"): true}
    puts (r.empty? ? "Yes!" : "No :-(") 
end

array_sorted? a
bubble_sort! a
array_sorted? a

Good luck!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.