Merge-Sort

Algorithmen, Sprachunabhängige Diskussionen zu Konzepten, Programmiersprachen-Design
Antworten
FritziFoppel
Beiträge: 101
Registriert: Sa Mär 02, 2013 6:53 pm
Wohnort: Göppingen

Merge-Sort

Beitrag von FritziFoppel » 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

Code: Alles auswählen

for(i = 0; i < (listSize+1)/2; i++) // +1 im Falle einer ungeraden Anzahl
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

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3084
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Merge-Sort

Beitrag von cloidnerux » Fr Feb 21, 2014 4:09 pm

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
Du musst die Anzahl der Elemente zählen. Entweder zählst du alle Elemente durch, oder hast einen Zähler der beim Anlegen und hinzufügen der Elemente mitzählt.
Die Angabe, wie viele Elemente du in einer Datenstruktur hast, ist sowieso eine essentielle, du wirst dieses Attribut immer haben.
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.
Wieso musst du zählen? Hast du eine verkettet Liste?
Im Grunde musst du auf Element n/2 zugreifen. Wenn du keine Möglichkeit hast das direkt zu machen, dann musst du iterieren.
Redundanz macht wiederholen unnötig.
quod erat expectandum

FritziFoppel
Beiträge: 101
Registriert: Sa Mär 02, 2013 6:53 pm
Wohnort: Göppingen

Re: Merge-Sort

Beitrag von FritziFoppel » Fr Feb 21, 2014 4:40 pm

cloidnerux hat geschrieben:Du musst die Anzahl der Elemente zählen. Entweder zählst du alle Elemente durch, oder hast einen Zähler der beim Anlegen und hinzufügen der Elemente mitzählt.
Die Angabe, wie viele Elemente du in einer Datenstruktur hast, ist sowieso eine essentielle, du wirst dieses Attribut immer haben.
Oke dann komme ich da wohl nicht drum herum.
cloidnerux hat geschrieben:Wieso musst du zählen? Hast du eine verkettet Liste?
Im Grunde musst du auf Element n/2 zugreifen. Wenn du keine Möglichkeit hast das direkt zu machen, dann musst du iterieren.
Ja, ich benutze eine linked list. Na Die Zählschleife zählt ja bis zum n/2 ten Element, also genau das was ich haben möchte. Für mich ist das zählen. :)

Code: Alles auswählen

for(i = 0; i < ((listSize+1)/2); i++)
        {
            node = node->next;
        }
Danke ;)

Antworten