在SML中使用Foldl或Foldr書寫氣泡排序

是否有一種方法可以使用SML中提供的Foldl或Foldr方法來實現氣泡排序？任何指導都會有所幫助。在SML中使用Foldl或Foldr書寫氣泡排序

2014-03-13 Rootkit32

我相信你可以。使用foldl做它可能會要求您每次遍歷列表時都要顛倒這個列表的順序，所以您必須跟蹤它所處的方向，以便在必要時最後一次將其撤消。 –

您持有「持有價值」的狀態必須跟蹤累積的已排序元素和標記是否已更改此通行證中的列表。（並且，正如前面提到的，可能是否這個列表在這個過程中是相反的。） –

我剛剛在OCaml中寫了一個實現來演示我自己滿意的技術。

我把排序過程分成兩部分。一種是通過fold_left（foldl）調用的比較和交換功能。這個函數的類型（與布爾是是否發生了這種掃描交換）：

bool * 'a list -> 'a -> bool * 'a list

每次運行時，它做了交換，如果合適，建立了在由其結果一個新的列表時與輸入相反的順序。（由於foldl的從左到右，尾遞歸的行爲，這是必要的。）它還跟蹤是否在此掃描列表中進行了任何交換（必要時我們知道何時停止排序）。

其他功能是遞歸的，只是保持調用掃描，直到沒有改變。該函數還有一個布爾值，它在每次調用時切換以跟蹤列表當前是否被反轉。當它看到最近一次掃描沒有進行交換時，它會返回結果列表。如果列表當前被反轉，那麼它在最後一次返回之前將其反轉。

這是第二個函數的類型（這裏的布爾是名單是否正在反轉）：

bool -> 'a list -> 'a list

應該也同樣可以寫一個冒泡排序使用foldr相似。它不會是尾遞歸的（因爲foldr不是），並且由於它從右到左掃描列表，因此不必處理foldl帶來的逆向問題。

來源

2014-03-13 01:56:48

所以你幾乎寫了兩個函數，一個用於跟蹤交換是否已經發生並且交換，另一個用於調用交換和a布爾值來查看交換是否發生。如果沒有交換，則返回列表。你也確定'Foldl'從左到右，它看起來像是從右到左的文檔，而'Foldr'從左到右。這可能只是我分析它的錯誤。這裏是：[列表結構SML參考]（http://www.standardml.org/Basis/list.html#SIG:LIST.foldr:VAL） – Rootkit32

@ Rootkit32：我想這取決於你的定義「對」。我敢肯定的是foldl在尾巴之前處理列表的頭部。 Foldr首先處理尾部，然後回到頭部。實際上，我有三個函數：有一個「主」函數，它只需要一個列表作爲參數，它所做的就是在我的答案中調用函數＃2並帶有適當的開始參數。 –

我知道這是來不及回答你的問題，但希望這將幫助：

fun bsort [] = [] 
| bsort [x] = [x] 
| bsort (x::y::xs) = 
        if(y<x) then 
         y::bsort(x::xs) 
        else 
         x::bsort(y::xs); 

fun bubblesort [] = [] 
| bubblesort (x::xs) = bsort(x::(bubblesort(xs)));

記住，我們要做的冒泡排序，直到列表被完全排序。

來源

2014-05-12 12:44:57

在SML中使用Foldl或Foldr書寫氣泡排序

回答

相關問題