Seite 1 von 1

Java Code für Mergesort

Verfasst: 19. Sep 2015 23:03
von mProg
In dem Java Code für Mergesort http://wiki.algo.informatik.tu-darmstad ... esort#Java wird beim spalten einer Liste in zwei auf

Code: Alles auswählen

 i <= liste.size() / 2 
geprüft. Das hat zu Folge, dass z.B. eine zweielementige Liste in eine Liste mit zwei Elementen und eine leere Liste geteilt wird. Ist der Algorithmus auch so gedacht, oder ist der Code falsch?

Re: Java Code für Mergesort

Verfasst: 20. Sep 2015 18:28
von mProg
Jetzt ist mir auch aufgefallen, dass dieser Code in eine endlose Schleife geraten müsste. Wenn ich eine Liste mit zwei Elemente eingebe, kommt in der Zerlegung eine Liste mit zwei Elementen und eine leere Liste, was widerum von Merge aufgerufen wird, was nie zum Anker kommt. :roll:

Re: Java Code für Mergesort

Verfasst: 20. Sep 2015 19:15
von joshimoo
Hallo falls jemand eine einfache und schöne Referenz Implementierung von MergeSort sucht könnte ich euch diese anbieten.
https://github.com/joshimoo/JLib/blob/m ... eSort.java

Die Implementierung hat eine Laufzeit von O(n*log(n)) sowie O(n) Memory für die Merge Routine.
Der extra speicher kann weiter optimiert werden, macht die Implementierung allerdings weit hässlicher :)

Dort findet ihr auch viele weitere Implementierungen, der in der GDI2 vorgestellten Algorithmen/Datenstrukturen.
Bei der Implementierung habe ich darauf geachtet, das diese Generisch sind.
Außerdem findet ihr der lib auch für jede Implementierungen Unit Tests die eine 100% Code Abdeckung der relevanten Teile erreicht.

Vielleicht hilft dies ja jemandem :)