气泡排序算法中的红宝石无限循环

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 

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

在“除非“，它将检查条件和交换位置，如果有必要，将跳过收益率部分。我尝试了一步一步调试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

快速回答：

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 

你可以重新因为它进一步删除while循环@Aetherus建议，但我想你会很高兴看到修复的实际错误。

Answer 2

您的代码有太多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