Haskell-Forum
Gepostet: |
Bottom-Up MergeSort | ||||||||||
| Hallo. Wir sollen ein Bottom-Up MergeSort in Haskell schreiben. Wir wissen zwar, dass wir die Listen in 1-elementige Teillisten teilen müssen, aber wie wir die zwei aufeinanderfolgenden Listen dann nacheinander vergleichen wissen wir einfach nicht. Anschließend müssen die Listen wieder zusammengefügt werden zu 2-elementigen Listen und dann müssen auch wieder die Elemente einzeln (1. Element mit 1. Element und 2. Element mit 2. Element) verglichen werden, usw., oder? Hilfe wäre echt klasse. Danke schonmal |
|||||||||||
| Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
| Hallo, Mergesort funktioniert ja in zwei Stufen. Erst wird die Liste in der Hälfte geteilt und beide Teillisten wieder rekursiv mit Mergesort sortiert. Das passiert solange, bis die Liste leer ist oder nur ein Element enthält. Im zweiten Schritt werden dann die beiden gesplitteten Listen wieder mit einer Hilfsfunktion zusammen"gemergt". Diese Hilfsfunktion weiß, dass die beiden Eingabelisten schon sortiert sind und kann somit leicht wieder eine sortierte Liste erzeugen, indem jeweils die ersten Elemente beider Listen betrachtet werden, das kleinere von beiden in die Ausgabeliste kommt und dann aus der entsprechenden Eingabeliste entfernt wird. Das wird solange wiederholt bis beide Listen leer sind. Das ist das allgemeine Verfahren (sofern "Bottom-Up Mergesort" nicht noch irgendwas anderes ist); bei konkreten Problemen bitte Quellcode-Fragmente posten, bei denen es hakt. Viele Grüße, Siracusa |
|||||||||||
| Zum Seitenanfang | |||||||||||
