Merge-Sort
Verfasst: Fr Feb 21, 2014 3:57 pm
Tach,
Ich versuch in letzter Zeit ein paar Algorithmen zu verstehen und anschließend auch nachzuprogrammieren. Gerade bin ich dabei, Merge-Sort zu implementieren, allerdings stellen sich mir einige Fragen.
Wer nicht weiß worum es dabei geht, siehe Wikipedia: http://de.wikipedia.org/wiki/Mergesort
Mir geht es weniger um die Logik, sondern um das Aufspalten der Liste.
Angenommen man hat n Elemente in einer Liste. Wie soll ich dann die Liste zur Hälfte aufspalten wenn ich nicht weiß was n ist.
Die einzige Möglichkeit, die ich mir überlegt habe ist beim Hinzufügen eines Knotens einen Zähler mitzählen zu lassen. Danach soll mit einer Zählschleife
bis zur Hälfte von n gezählt werden um dann den Anfang der zweiten Liste zu bestimmen.
Ist das die einzige Möglichkeit? Das erscheint mir bei einer großen Anzahl von n ein wenig unsinnig, auch wenn Rechner das heutzutage schnell hinbekommen.
Grüße Chris
Ich versuch in letzter Zeit ein paar Algorithmen zu verstehen und anschließend auch nachzuprogrammieren. Gerade bin ich dabei, Merge-Sort zu implementieren, allerdings stellen sich mir einige Fragen.
Wer nicht weiß worum es dabei geht, siehe Wikipedia: http://de.wikipedia.org/wiki/Mergesort
Mir geht es weniger um die Logik, sondern um das Aufspalten der Liste.
Angenommen man hat n Elemente in einer Liste. Wie soll ich dann die Liste zur Hälfte aufspalten wenn ich nicht weiß was n ist.
Die einzige Möglichkeit, die ich mir überlegt habe ist beim Hinzufügen eines Knotens einen Zähler mitzählen zu lassen. Danach soll mit einer Zählschleife
Code: Alles auswählen
for(i = 0; i < (listSize+1)/2; i++) // +1 im Falle einer ungeraden Anzahl
Ist das die einzige Möglichkeit? Das erscheint mir bei einer großen Anzahl von n ein wenig unsinnig, auch wenn Rechner das heutzutage schnell hinbekommen.
Grüße Chris