榆树快速排序的可视化

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) 

鉴于这一结果，然后你可以写一个显示在您认为合适的方式对数据的视图。