氣泡排序算法中的紅寶石無限循環

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