Ruby 冒泡排序算法中的无限循环

Question

我已经使用 Ruby 构建了基本的冒泡排序算法，没有任何问题。代码如下：

def bubble_sort(arr)
 swapped=true
 while swapped
    swapped=false
    for j in 0..arr.length-2 do
      if arr[j]>arr[j+1]
        arr[j], arr[j+1] = arr[j+1], arr[j]
        swapped=true
      end
    end
 end
arr
end

现在，我正在尝试实现同样的方法，但具有接受代码块的功能。代码块部分工作正常，但是当没有提供代码块时，该方法应该像上面那样工作，虽然在我看来逻辑上是一样的，但由于某种原因，它进入了无限循环：

在"unless"这一行，如果有必要，它会检查条件和交换位置，并跳过收益部分。我用rdebugger一步步调试，没找到原因

def bubble_sort_by(arr)
  swapped = true
  while swapped
    swapped=false
    for i in 0..arr.length-2 do
      unless block_given?
        arr[i], arr[i+1] = arr[i+1], arr[i] if arr[i] < arr[i+1]
        swapped=true
      end #unless
    if block_given?
      if yield(arr[i], arr[i+1])>0
        arr[i], arr[i+1] = arr[i+1], arr[i]
        swapped=true
      end #if yield
    end #if block_given?
    end #for
  end #while
puts arr
return arr
end

Answer 1

你的代码block_given?太多了，我不明白你为什么需要布尔变量swapped。

这是我的冒泡排序版本（因为它对数组进行就地排序，所以我在它的名字中加上了一声巨响）。

def bubble_sort!(arr, &compare)
  # Provide a default comparison algorithm
  compare ||= proc {|a, b| a <=> b}

  (1...arr.length).each do |i|
    (0...i).each do |j|
      arr[i], arr[j] = arr[j], arr[i] if compare.call(arr[i], arr[j]) < 0
    end
  end

  arr
end

Answer 2

快速回答：

arr[i], arr[i+1] = arr[i+1], arr[i] if arr[i] < arr[i+1]
swapped=true

应替换为：

if arr[i] < arr[i+1]
  arr[i], arr[i+1] = arr[i+1], arr[i]
  swapped=true
end

发生的事情是你总是将 swapped 设置为 true，即使没有交换元素。所以你陷入了无限循环。

现在进行一些代码清理...首先，而不是编写：

if(foo)
  # ...
end
unless(foo)
  # ...
end

让我们将其设为 if/else 语句：

def bubble_sort_by(arr) 
  swapped = true 

  while swapped 
    swapped=false 
    for i in 0..arr.length-2 do 
      if block_given? 
        if yield(arr[i], arr[i+1])>0 
          arr[i], arr[i+1] = arr[i+1], arr[i] 
          swapped=true 
        end 
      else 
        if arr[i] < arr[i+1] 
          arr[i], arr[i+1] = arr[i+1], arr[i] 
          swapped=true 
        end 
      end 
    end #for 
  end #while 

  return arr 
end

您可以按照@Aetherus 的建议进一步重构它以删除 while 循环，但我想您会很高兴看到实际的错误已修复。

Ruby 冒泡排序算法中的无限循环

Ruby infinite loop in bubble sort algorithm

ruby

algorithm

loops

infinite-loop

bubble-sort