Haskell Liste

Erste Frage Aufrufe: 1025     Aktiv: 26.07.2021 um 22:18
0

Sei folgende Funktionsdefinition des BubbleSort-Algorithmus: bubbleSort :: (Ord a) => [a] -> [a] bubbleSort xs | isSorted (<=) xs = xs otherwise = bubbleSort (moveBubble xs) where moveBubble [] = [] moveBubble [x] = [x] moveBubble (x:y:rest) | (<=) x y = x: moveBubble (y:rest) | otherwise = y: moveBubble (x:rest) Definieren Sie eine traceBubbleSort-Funktion, die nach jedem Aufruf der moveBubbleFunktion den Zwischenzustand der zu sortierenden Liste in einer Liste von Listen speichert, so dass am Ende des Sortieralgorithmus der Verlauf als Ergebnis angegeben wird. Anwendungsbeispiele: traceBubbleSort [0,1,3,8,0] => [[0,0,1,3,8], [0,1,0,3,8], [0,1,3,0,8], [0,1,3,8,0]]

Wie löse ich diese Aufgabe? Ich weiß leider nicht was ich machen soll.

Diese Frage melden
gefragt

Student, Punkte: 10

 
Kommentar schreiben
1 Antwort
0

Hier die Lösung:

traceBubbleSort :: (Ord a) => [a] -> [[a]]
traceBubbleSort xs
 | isSorted (<=) xs = [xs]
 | otherwise        = traceBubbleSort (moveBubble xs) ++ [xs]
 where
  moveBubble []  = [] 
  moveBubble [x] = [x] 
  moveBubble (x:y:rest) 
   | x <= y    = x: moveBubble (y:rest) 
   | otherwise = y: moveBubble (x:rest)
  isSorted f (x:y:xs)
    | f x y     = isSorted f (y:xs)
    | otherwise = False
  isSorted _ _ = True
Diese Antwort melden
geantwortet

Punkte: 35

 

Kommentar schreiben