Haskell-Forum
Gepostet: |
BubbleSort ??? | ||||||||||
| Hi Also das ist die Aufgabe: Das Sortierverfahren 'Bubblesort' arbeitet wie folgt: * Beim Durchlaufen einer Liste werden jeweils die Paare unmittelbar aufeinanderfolgender Elemente miteinander verglichen und, falls sie nicht in der richtigen Reihenfolge bezüglich der verwendeten Ordnung sind, miteinander vertauscht. * Das Durchlaufen wird solange wiederholt, bis die Liste vollständig geordnet ist. 1. Definieren Sie eine Haskell-Funktion bubble (inklusive Signatur), die einmaliges Durchlaufen einer Liste mit Vertauschen wie oben beschrieben realisiert. Die Lösung dafür ist diese: bubble:: Ord a => [a] -> [a] bubble [x] = [x] bubble (x:y:ys) |x<=y = x: bubble (y:ys) |otherwise = y: bubble (x:ys) Nun ist jedoch die weitere Aufgabe: Definieren Sie eine Haskell-Funktion bubbleK (inklusive Signatur), die wie bubble arbeitet, aber abhängig vom Wert eines zusätzlichen Arguments k für die Anzahl bereits erfolgter Durchläufe den dann sicher bereits sortierten Teil der Liste nicht mehr erneut bearbeitet. Achten Sie auf eine möglichst effiziente Lösung. Jedoch verstehe ich davon nicht ganz worum es da geht. Habe zwar die Lösung hier aber ich verstehe die nicht ganz. Hoffe mir kann einer mal alles schnell erklären. bubbleK :: Ord a => [a] -> Int -> [a] bubbleK s@(x:y:ys) k = help s k (length s) help [x] k l = [x] help z@(x:y:ys) k l | k == l = z | x < y = x: help (y:ys) (k+1) l | otherwise = y: help (x:ys) (k+1) l Danke |
|||||||||||
| Zum Seitenanfang | ICQ | ||||||||||
Gepostet: |
|||||||||||
| Hallo, also bei der Funktion bubble wird in einem Durchlauf ja immer das größte Element nach ganz hinten in die Liste geschoben, während kleinere Elemente sich immer nur um eine Position nach vorn bewegen. Das kann man ausnutzen, indem man alle "größten" Elemente im hinteren Bereich der Liste beim erneuten Durchlauf gar nicht mehr betrachtet, weil man weiß, dass sie schon richtig sortiert sind. Nach k Durchläufen sind also die letzten k Elemente schon korrekt sortiert. Und genau dieses k soll in der Funktion bubbleK beachtet werden. In deiner Hilfsfunktion help ist k also die Anzahl der bereits sortierten Elemente am Ende der Liste und l die Länge der Liste. Also müssen nur noch l-k Listenelemente sortiert/geprüft werden. Die Funktion arbeitet daher wie bubble, nur dass nach jedem Sortierschritt k um eins erhöht wird. Wenn k = l ist, wird abgebrochen und die aktuelle Liste (z) als Ergebnis zurückgegeben. z stellt dann genau die letzten k Elemente der Originalliste dar. Viele Grüße, Siracusa |
|||||||||||
| Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
| hmm also ok das verstehe ich ja soweit... Aber ich verstehe irgendwie die erbnise nich ganz von bubbleK Main> bubbleK [3,1,7,4,2] 1 [1,3,4,2,7] Main> bubbleK [3,1,7,4,2] 2 [1,3,4,7,2] Main> bubbleK [3,1,7,4,2] 3 [1,3,7,4,2] Main> bubbleK [3,1,7,4,2] 4 [1,3,7,4,2] Main> bubbleK [3,1,7,4,2] 5 [3,1,7,4,2] Main> bubbleK [3,1,7,4,2] 6 [1,3,4,2,7] Main> bubbleK [3,1,7,4,2] 7 [1,3,4,2,7] Die liste sieht bei k 1,6,7...usw gleich aus aber why?? für K 3,4,5 sieht es auch gleich aus und für k 2 anders... aber why ich verstehe den zusammenhang irgendwo nicht? danke |
|||||||||||
| Zum Seitenanfang | ICQ | ||||||||||
Gepostet: |
|||||||||||
| Ok hab dir ganze Sache schon verstanden danke... | |||||||||||
| Zum Seitenanfang | ICQ | ||||||||||
