d_zero d_zero - 7 months ago 15
Ruby Question

How can I pass in a block to my "bubble sort" method?

The below code is my newbie take on a bubble sort method.

#For each element in the list, look at that element and the element
#directly to it's right. Swap these two elements so they are in
#ascending order.

def bubble_sort (array)
a = 0
b = 1
until (array.each_cons(2).all? { |a, b| (a <=> b) <= 0}) == true do
sort = lambda {array[a] <=> array[b]}
sort_call = sort.call
loop do
case sort_call
when -1 #don't swap
a += 1
b += 1
break
when 0 #don't swap
a += 1
b += 1
break
when 1 #swap
array.insert(a,array.delete_at(b))
a += 1
b += 1
break
else #end of array, return to start
a = 0
b = 1
break
end
end
end
puts array.inspect
end

array = [4, 2, 5, 6, 3, 23, 5546, 234, 234, 6]
bubble_sort(array)


I want to be able to alter this method so that it takes a block of code as an argument and uses this to determine how it sorts.

For example:
array = ["hello", "my", "name", "is", "daniel"]
bubble_sort(array) {array[@a].length <=> array[@b].length}


(When I've tried this I've turned
a
and
b
into instance variables throughout the code.)

I have tried using
yield
but I get
undefined method 'length' for nil:NilClass
once the end of the array is reached. I've tried adding in things such as

if array[@b+1] == nil
@a = 0
@b = 1
end


This helps but I still end up with weird problems like infinite loops or not being able to sort more than certain amount of elements.

Long story short, I have been at this for hours. Is there a simple way to do what I want to do? Thanks.

Answer

The way you're calling your lambda is a bit odd. It's actually completely unnecessary. I refactored your code and cleaned up a bit of the redundancy. The following works for me:

def sorted?(arr)
  arr.each_cons(2).all? { |a, b| (a <=> b) <= 0 }
end

def bubble_sort (arr)
  a = 0
  b = 1
  until sorted?(arr) do
    # The yield call here passes `arr[a]` and `arr[b]` to the block.
    comparison = if block_given? 
               yield(arr[a], arr[b])
             else
               arr[a] <=> arr[b]
             end

    if [-1, 0, 1].include? comparison
      arr.insert(a, arr.delete_at(b)) if comparison == 1

      a += 1
      b += 1
    else
      a = 0
      b = 1
    end
  end

  arr
end

sample_array = [4, 2, 5, 6, 3, 23, 5546, 234, 234, 6]

# Sanity check:
100.times do
  # `a` is the value of `arr[a]` in our function above. Likewise for `b` and `arr[b]`.
  print bubble_sort(sample_array.shuffle) { |a, b| a <=> b }, "\n"
end

EDIT

A cleaner version:

  # In place swap will be more efficient as it doesn't need to modify the size of the arra
def swap(arr, idx)
  raise IndexError.new("Index #{idx} is out of bounds") if idx >= arr.length || idx < 0

  temp         = arr[idx]
  arr[idx]     = arr[idx + 1]
  arr[idx + 1] = temp
end

def bubble_sort(arr)
  loop do
    sorted_elements = 0

    arr.each_cons(2).each_with_index do |pair, idx|
      comparison = if block_given?
                     yield pair.first, pair.last
                   else
                     pair.first <=> pair.last
                   end

      if comparison > 0
        swap(arr, idx)
      else
        sorted_elements += 1
      end
    end

    return arr if sorted_elements >= arr.length - 1
  end
end

# A simple test

sample_array     = [4, 2, 2, 2, 2, 2, 5, 5, 6, 3, 23, 5546, 234, 234, 6]
sample_str_array = ["a", "ccc", "ccccc"]

100.times do
  print bubble_sort(sample_array.shuffle) { |a, b| a <=> b }, "\n"
  print bubble_sort(sample_str_array.shuffle) { |a, b| a.length <=> b.length }, "\n"
end