MergeSort und QuickSort

Snej
Neuling
Neuling
Beiträge: 5
Registriert: 27. Jul 2011 16:00

MergeSort und QuickSort

Beitrag von Snej »

MergeSort und QuickSort

Bei diesen beiden rekursiven Sortieralgorithmen haben wir immer das Problem das eine Eingabesequenz geteilt wird und darauf bezieht sich meine Frage:

der einfachhalt halber betrachten wir immer alle Teilsequenz parallel.

Bsp.:

MergeSort bisher:

S={21,4,8,24,12,22,1}

S1={21,4,8,24} S2={12,22,1}

S1.1={21,4} S1.2={8,4} S2.1={12,22} S2.2={1}

S1.1.1={21} S1.1.2={4} S1.2.1={8} S1.2.2={4} S2.1.1={12} S2.1.2={22}

MergeSort tatsächlich:

S={21,4,8,24,12,22,1}

S1={21,4,8,24} S2={12,22,1}

S1.1={21,4} S1.2={8,4}

S1.1.1={21} S1.1.2={4}

merge(S1.1.1 , S1.1.2)

Da wir für die Aufgaben einen Rekursionsschritt vorgegeben bekommen, ist nun die Frage ob wir nach dem tatsächlichem Ablauf des Algorithmus vorgehen, also erst bis zur einelementigen Sequenz auf der linken Seite runtergehen ,weil

Aufruf kann so aussehen:

// linke Seite (wird in diesem Fall ja bis zur Abbruchbedingung immer zuerst abgearbeitet)
S1 = mergeSort( S1 );
// rechte Seite
S2 = mergeSort( S2 );

... später ...
merge(S1, S2);

und dann immer einen Schritt höher gehen. Der tatsächliche Ablauf hat dabei wesentlich mehr Schritte abzulaufen, welche berücksichtig werden müssen.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: MergeSort und QuickSort

Beitrag von Prof. Karsten Weihe »

Snej hat geschrieben: Bei diesen beiden rekursiven Sortieralgorithmen haben wir immer das Problem das eine Eingabesequenz geteilt wird und darauf bezieht sich meine Frage:
Ich fürchte, ich habe in Ihrem Thread keine explizite Frage gefunden - was genau ist denn Ihre Frage :?:

KW

edmolf
Erstie
Erstie
Beiträge: 19
Registriert: 15. Okt 2010 13:35

Re: MergeSort und QuickSort

Beitrag von edmolf »

Die Frage sollte wohl lauten welche der beiden Betrachtungsweisen die Richtige ist?

student1
Erstie
Erstie
Beiträge: 22
Registriert: 29. Mai 2012 10:14

Re: MergeSort und QuickSort

Beitrag von student1 »

*push* Wir würden die Frage auch gerne beantwortet bekommen

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: MergeSort und QuickSort

Beitrag von JannikV »

Grundsätzlich heißt Rekursionsebene 3 oder Rekursionstiefe 3 dass alles auf der gleichen Ebene gemeinsam betrachtet wird, also so wie du es unter "bisher" aufgeschrieben hast.

Allerdings weiß ich nicht ob sich diese Frage überhaupt stellt. In den Aufgabenstellungsmustern steht doch bei rekursiven Algorithmen "... speziell den Rekursionsschritt, der auf Input Z arbeitet ...".. Da wird keine Rekursionsebene angegeben sondern der Input eines konkreten Aufrufs. Damit sollte klar sein um was es in dem Moment geht.

VG

Antworten

Zurück zu „Archiv“