快速排序實現：堆棧層次過深（SystemStackError）

所以我想在Ruby中實現快速排序，我得到這個錯誤`快速排序「：堆棧層次過深（SystemStackError）快速排序實現：堆棧層次過深（SystemStackError）

def quicksort(array) 
    if array.length <= 1 
    return array 
    end 
    less = Array.new 
    greater = Array.new 
    pivot = array[array.length/2] 
    array.each do |x| 
    if x < pivot 
     less << x 
    else 
     greater << x 
    end 
    end 
    return quicksort(less) << pivot << quicksort(greater) 
end

編輯我改變else到elsif x > pivot，它似乎工作。

來源

2011-11-08 lesce

快速排序可以使用多達n個層次的堆棧（在病理情況下），其中n是輸入元素的數量。如果遇到這種情況，那麼只增加堆棧大小，選擇更好的透視方法（這隻會減少病態的壞情況），或更改快速排序實現將會修復它。如果它發生的小n，那麼終端條件是錯誤的，當然:)什麼是導致此異常的[最小]輸入？ – 2011-11-08 22:28:29

在什麼情況下你得到這個錯誤？ – Ryanmt

我改變了其他=> elsif x>支點，它似乎工作。 – lesce

您的算法正在爲我工作，即使是在生成測試數組時也是如此。

quicksort Range.new(1,1e7).to_a.shuffle

當然，這需要大約4.5 GB的RAM才能完成。至於清理輸出...

ruby-1.9.3-p0 :018 >  quicksort [1,3,2] # => [1, 2, [], 3, []] 
ruby-1.9.3-p0 :019 >  quicksort [1,4,2,3] # => [1, 2, [3, [4]]]

改變這一行：

return (quicksort(less) << pivot << quicksort(greater)).flatten.compact

它使這一切更清潔。

ruby-1.9.3-p0 :037 >  quicksort [1,3,2] # => [1, 2, 3] 
ruby-1.9.3-p0 :038 >  quicksort [1,4,2,3] # => [1, 2, 3, 4]

來源

2011-11-08 22:19:29 Ryanmt

你的函數無限遞歸。使用ruby-debug來找出原因。

EDIT1：

我想你想要的功能的最後一行是這樣的：

return quicksort(less) + quicksort(greater)

來源

2011-11-08 22:13:10

在紅寶石堆棧大小的默認設置相當小。因此，用堆大數據集來執行遞歸函數並不難。

確保不會無限遞歸的最簡單方法是在非常小的數據集上運行quicksort。如果它仍然爆炸你知道你無限遞歸。

您可以在Matz回覆的this post中找到關於堆棧大小的一些信息。

來源

2011-11-08 22:16:18 Dty

但是在Quicksort中堆棧大小應該保持非常小，除非實現在已排序的數據上出現故障。堆棧大小將在lg（n）左右 - 即使數組填滿所有內存，也小於任何腳本語言的限制！ – japreiss

你需要刪除透視出數組的，因爲你在以後的加回去，這樣，而不是

pivot = array[array.length/2]

你應該做

pivot = array.delete_at(array.length/2)

來源

2012-01-13 00:07:16 kentor

快速排序實現：堆棧層次過深（SystemStackError）

回答

相關問題