Suche rekursiven Sortier Algorithmus

Werbeanzeige

marioschluse

Frischling

Beiträge: 25

14.01.2012, 15:57

Suche rekursiven Sortier Algorithmus

Hallo Leute,
für ein Problem brauche ein rekursiven Algorithmus, der folgendes tut:

Aus einem Array mit int a[]={1,2,3,4,5,6,7,}
Diese Reihenfolge ausgibt: 4,2,1,3,6,5,7,

Der Algorithmus müsste dann
erst mal die Mitte finden, dann die Mitte zwischen Anfang und der neuen Mitte usw.
Und wenn man dann nicht mehr die Mitte bilden kann, weil Anfang und ende gleich sind,
muss man neu Mitte finden.

Meine einzige Idee ist das Prinzip der binären Suchen.
Allerdings weiß ich nicht, wie man am Ende alle Elemente finden soll

Hoffentlich hab ich mein Problem verständlich formuliert...
Kann mir jemand vielleicht helfen? Wär auch froh,
wenn jeman einen rekursiven algorithums hätte, der fast die gleiche Folge ausgeben würde.
Vielen Dank schon einmal im Voraus

Zum Seitenanfang

Jonathan_Klein

Community-Fossil

Beiträge: 3 820

14.01.2012, 16:47

Moment, die Eingabeliste ist schon sortiert? Dann kannst du doch einfach auf das mittlere Arrayelement zugreifen. Die Indexberechnung könnte halt interessant werden, je nachdem ob es eine gerade oder ungerade Anzahl an Elementen gibt, aber das muss man (da er ja rekursiv ist) nur an einer Stelle beachten und einmal testen (gibt ja nur 2 Fälle). Ansonsten hast du den ALgorithmus doch schon in Worten erklärt, das kann man 1zu1 in Code umsetzen.

Wofür ist denn die Ausgabe?

Lieber dumm fragen, als dumm bleiben!

Zum Seitenanfang

marioschluse

Frischling

Beiträge: 25

14.01.2012, 17:06

Hi,
danke für die Antwort.
Wirklich? Ich kann das, was ich in Worten geschrieben habe, leider
trotzdem nicht implementieren...

Du kennst du bestimmt binäre such Bäume oder?
Nun ja, ich hab ne Aufgabe, wo
ich Zahlen aus einem Array in einen Baum einfügen muss.
Und diese bestimmte Reihenfolge ist gewollte, damit der "Baum" ausgeglichen wird.

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »marioschluse« (14.01.2012, 17:36)

Zum Seitenanfang

drakon

Supermoderator

Beiträge: 6 513

Wohnort: Schweiz

Beruf: Entrepreneur

14.01.2012, 17:49

Das ist recht einfach.
Schreib zuerst mal eine Funktion, die dir das mittlere Element ausgibt für eine beliebig lange Liste von Zahlen. Beachte dann aber was passieren soll, wenn die Liste leer ist, nur ein Element enthalten ist oder es kein exakt mittleres Element gibt. Wenn du das hast, dann rufst du die gleiche Funktion nochmal auf alle Elemente Links von dem mittleren Element auf und auf die Elemente, die rechts sind (natürlich nur, wenn es noch Elemente auf der entsprechenden Seite gibt).

http://www.drakon.ch | Weltweit 31. Bester Solitär Spieler (Standard XP)

Zum Seitenanfang

Jonathan_Klein

Community-Fossil

Beiträge: 3 820

14.01.2012, 18:32

http://de.wikipedia.org/wiki/AVL-Baum

Da sollten eigentlich alle Baumalgorithmen beschrieben sein. Das wäre etwas eleganter, als erst eine solche Liste aufzubauen (zumal du zur Laufzeit neue Elemente einfügen und löschen kannst).

Ansonsten: Probier doch mal Pseudocode zu schreiben, den du in einigen Schritten immer mehr zu echten Code umformst. Wenn du dabei nicht weiter kommst, kannst du ja die Zwischenschritte hier zeigen und nachfragen.

Lieber dumm fragen, als dumm bleiben!

Zum Seitenanfang

drakon

Supermoderator

Beiträge: 6 513

Wohnort: Schweiz

Beruf: Entrepreneur

14.01.2012, 18:43

Nein. Das macht schon Sinn. Es gibt Fälle, wo man alles bereits sortiert hat und dann nur einen perfekten AVL Baum aufbauen will. Und genau dafür kann man den Algorithmus brauchen, welcher btw. auf der Seite nicht beschrieben wird. Das von einem AVL Baum machen zu lassen (was natürlich geht) ist sehr ineffizient.
Im übrigen ist ein AVL Baum zu implementieren nicht ganz so trivial, wie das aufbauen eines Baumes, wenn man die Liste sortiert hat. Ich bezweifle, dass er dazu im Moment in der Lage ist (nicht persönlich nehmen marioschluse).

http://www.drakon.ch | Weltweit 31. Bester Solitär Spieler (Standard XP)

Zum Seitenanfang

marioschluse

Frischling

Beiträge: 25

14.01.2012, 19:10

Zitat von »drakon«

Ich bezweifle, dass er dazu im Moment in der Lage ist (nicht persönlich nehmen marioschluse).

Ja, da hast du recht, ich weiß wie schlecht ich c++ bin, kein Problem

So sieht zurzeit meine Funktion aus:

C-/C++-Quelltext

void rekursion (int array2[], int anfang, int ende)
{
    if (anfang!=ende)
    {
    int mitte=0;
    mitte=(anfang+ende)/2;
    cout<<array2[mitte]<<endl;
    rekursion (array2, anfang, mitte); //Hier soll die Rekursion anfangen, mit der Mitte, als neues Ende...
    }
    else
    {
        ???
    }
}

Kurze erläuterung:
Es wird das vorgegebene array, den Anfang des Arrays (natürlich 0) und das Ende des Arrays an die Funktion übergeben.
Solange Anfang ungleich Ende ist ist,
wird das mittlere Element berechnet und ausgegeben.
Danach wird die eigene Funktion in sich selbst aufgerufen, mit dem Unterschied, dass die Mitte diesmal das letzte Element ist.

Wenn aber Anfang gleich Ende ist,
brauche ich auf jedenfall einen neuen Wert für das Ende... (das möchte ich in der else-konstrukt machen)
Leider kann ich das Ende nicht mehr mit sizeof(array2)/sizeof(int) berechnen, da das ja nur zeiger sind.
Außerdem kann ich das Ende auch nicht irgendwie zwischenspeichern, weil die Variable dann bei jedem Funktionsaufruf wieder überschrieben werden würde....

hat jemand ne idee?
Ein kleines Beispielcode wäre sehr hilfreich.

Zum Seitenanfang

drakon

Supermoderator

Beiträge: 6 513

Wohnort: Schweiz

Beruf: Entrepreneur

14.01.2012, 19:48

Nein. Wenn der Anfang gleich dem Ende ist bedeutet das, dass du keine Werte mehr drin hast.
Du brauchst eigentlich nur noch eine zweite Rekursion, wo du von der Mitte bis zum Ende gehst. Dann hast du die Aufteilung Anfang-Mitte und Mitte-Ende. Somit ist die Mitte für einen Zweig dort das Ende und für den anderen der Anfang.

http://www.drakon.ch | Weltweit 31. Bester Solitär Spieler (Standard XP)