visualisation Elm quicksort

Question

Je suis en train d'afficher le processus de tri de quicksort 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 ] 

En ce moment, je peux obtenir les 2 premières lignes, mais je ne suis pas sûr comment aborder cette question de manière récursive.

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

Ce sorties:

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

Answer 1

Si vous essayez d'obtenir ce genre de sortie, récursivité directe dans la vue ne va pas bien fonctionner. Au lieu de cela, je l'aborderais comme l'écriture d'une variation de quicksort qui connecte l'état en cours de route.

Voici un exemple de quicksort qui renvoie également une liste de journaux. Les alias de type sont inclus pour essayer de faire l'annotation de fonction plus claire:

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) 

Étant donné ce résultat, vous pouvez alors écrire une vue qui affiche les données de la manière bon vous semble.