榆樹快速排序的可視化

Question

我試圖用榆樹

顯示快速排序的排序過程

[ 5, 8, 6, 2, 4, 1, 0, 3, 10, 7, 9 ] 
[2,4,1,0,3]  5  [8,6,10,7,9] 
[1,0] 2 [4,3]   [6,7] 8 [10,9] 
[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] 

現在，我可以拿到第2行，但我不能確定如何在遞歸的方式接近這一點。

list_to_html : List (List Int) -> Html msg 
list_to_html x = 
    div [] [ x |> toString |> text ] 

quicksort_partition : List Int -> Html msg 
quicksort_partition list = 
    case list of 
     x :: xs -> 
      let 
       lower = 
        List.filter ((>=) x) xs 

       higher = 
        List.filter ((<) x) xs 
      in 
      list_to_html [ lower, [ x ], higher ] 

     [] -> 
      list_to_html [] 

此輸出：

[ 5, 8, 6, 2, 4, 1, 0, 3, 10, 7, 9 ] 
[2,4,1,0,3]  [5]  [8,6,10,7,9] 

Answer 1

如果您想獲得該類型的輸出，在視圖中直接遞歸是不會工作。相反，我會把它寫成一種記錄狀態的快速排序變體。

下面是一個quicksort的例子，它也返回一個日誌列表。該類型別名包括試圖使功能註釋更加清晰：

type alias Depth = 
    Int 


type alias Log comparable = 
    (Depth, List comparable, comparable, List comparable) 


quicksortLog : Depth -> List comparable -> (List comparable, List (Log comparable)) 
quicksortLog depth list = 
    case list of 
     [] -> 
      ([], []) 

     x :: xs -> 
      let 
       (lower, lowerLog) = 
        quicksortLog (depth + 1) (List.filter ((>=) x) xs) 

       (higher, higherLog) = 
        quicksortLog (depth + 1) (List.filter ((<) x) xs) 

       log = 
        (depth, lower, x, higher) 
      in 
       (lower ++ [ x ] ++ higher, log :: lowerLog ++ higherLog) 

鑑於這一結果，然後你可以寫一個顯示在您認爲合適的方式對數據的視圖。