Java Code für Mergesort

mProg
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 147
Registriert: 25. Apr 2015 00:10

Java Code für Mergesort

Beitrag 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?

mProg
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 147
Registriert: 25. Apr 2015 00:10

Re: Java Code für Mergesort

Beitrag 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:

joshimoo
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 25. Apr 2015 17:16

Re: Java Code für Mergesort

Beitrag 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 :)

Antworten

Zurück zu „Archiv“