Elm 快速排序可视化

Question

我正在尝试用 Elm 显示快速排序的排序过程

[ 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 ]

现在我可以得到前两行，但我不确定如何以递归方式处理它。

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

如果您试图获得那种输出，视图内的直接递归将无法正常工作。相反，我会把它看作是编写一种快速排序的变体，它会记录整个过程中的状态。

这是一个快速排序的例子，它也是 returns 一个日志列表。包含类型别名以尝试使函数注释更加清晰：

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 )

根据该结果，您可以编写一个视图，以您认为合适的方式显示数据。

Elm 快速排序可视化

Elm quicksort visualization

haskell

quicksort

elm