Programm Quicksort Variable wird überschrieben

[VisualNero]

Hi Leute,

Ich hab folgendes Problem ich hab ein kleines Programm geschrieben mit dem Zahlen in eine Reihnfolge bringen kann das Problem ist nur wenn in der forschleife "j" größer als das Array wird, wird das Array überschrieben. Habt Ihr ne idee wie ich das weg bekomme?

#include <iostream.h>.

using namespace std;

int zahlen[] = {9,1,8,2,7,3,6,4,5,0,10,111,60};

int L1 = 0;

int R1 = 1;

int L2 = 0;

int R2 = 0;

int laeng = {sizeof(zahlen)/sizeof(zahlen[0])};

int main() {

       for (int i = 0; i < laeng; i++){

           cout << zahlen[i] << ",";

       };

       cout << "\n";

       cout << "\n";       

        for (int j = 0 ; j < (laeng*laeng); j++) {

            if (L2 > R2) {zahlen[L1] = R2,zahlen[R1] = L2;};

            if (L1 < laeng) {

                 L1++;

            }

            else {

                 L1 = 0;

            };

            if (R1 < laeng) {

                R1++;

            }

            else {

                 R1 = 0;

            };

            L2 = zahlen[L1];

            R2 = zahlen[R1];

        };

       for (int k = 0; k < laeng; k++){

           cout << zahlen[k] << ",";

       };

       cout << "\n";

       cout << "\n";

       cout << "groesse von array: "<< sizeof(zahlen)/sizeof(zahlen[0]) << "\n";

       getchar();

       return 0;

}

Ausgabe:

9,1,8,2,7,3,6,4,5,0,10,111,60,


0,1,2,3,4,5,6,7,8,9,10,13,13,


groesse von array: 13

Schon mal danke für Eure Hilfe im vorraus!

[~tine~]

Mit nur einer for-Schleife wirst du dein Array kaum sortiert bekommen, da du ja gar nicht weißt, wie oft die Schleife durchlaufen werden muss.

Einfach die doppelte Array-Größe als Abbruchbedingung zu nehmen (laeng*laeng) bringt dich da nicht ans Ziel, zumal du ja selber festgestellt hast, dass die Schleife öfter durchlaufen wird als das Array groß ist. Dadurch kommt es dann zu Fehlern.

Ich hab mal ein ähnliches Programm in Java geschrieben und die Sortierung folgendermaßen umgesetzt:

for(i=1;i<n.length;i++) 

{

  int j = i; 

  while(j > 0)	

  {

   if(n[j-1] > n[j]) 

   {

	double temp = n[j];

	n[j] = n[j-1];

	n[j-1] = temp;	

   }	

   else               

    break;

   j--; 

  }

}[/PHP]

Vielleicht hilft dir das ja weiter bei der Realisierung deines Programms.

tine

[Klotzkopp]

Habt Ihr ne idee wie ich das weg bekomme?

Ich bin mir nicht sicher, ob dir klar ist, dass der höchste gültige Index bei einem Array mit laeng Elementen laeng-1 ist. Deine Indexvariablen laufen bis einschließlich laeng, das ist eins zu weit.

Mit nur einer for-Schleife wirst du dein Array kaum sortiert bekommen

Doch, eine for-Schleife reicht in diesem Fall, die Indizes L1 und R1 werden ja in der Schleife wieder auf 0 gesetzt. Das ist zwar nicht besonders schön, sollte aber funktionieren. Ein Quicksort ist es allerdings nicht, eher ein mutierter Bubblesort, der die Anzahl der Vertauschungen am Worst-Case orientiert

[VisualNero]

Hi Leute,

danke für die Tips hab das Programm jetzt mal koplett umgeschrieben,

die Funktion ist jetzt voll da aber wollte mal wissen was Ihr vom Code haltet.

#include <iostream.h>.

using namespace std;

static int Zahlen[] = {9,1,8,2,7,3,6,4,5,0,11,15,28,10,55,23,17};

static int laenge = {sizeof(Zahlen) / sizeof(int)};

// Ausgabe vom Array Zahlen unsortiert

void start() {

    for (int k = 0; k < laenge; k++) {

    cout << Zahlen[k] << ",\n";

    }

    cout << "\n\n";

}

// Ausgabe vom Array Zahlen sortiert

void ausgabe() {

    for (int i = 0; i < laenge; i++) {

    cout << Zahlen[i] << ",\n";

    }

    cout << "\n\nmyArray has " << laenge << " elements";

}

// sortieren Zahlen

void sort() {

        int temp;

        int z;

        for (int i = 0; i < laenge -1; i++) {

            z = i + 1;

            if (z > laenge -1) {z = 0;};

            if (Zahlen[i] > Zahlen[z]) {

                temp = Zahlen[i];

                Zahlen[i] = Zahlen[z];

                Zahlen[z] = temp;

            }

        }

}

// Prüfung der Zahlenreihe und sortierungsaufruf

void test() {

    static int j = 0;

    while( j  < laenge -1) {

        j = 0;

        for (int i = 0; i < laenge -1; i++) {

            if (Zahlen[i + 1] > Zahlen[i]) {

               j++;

            };

        }     

        sort();

    }

}

int main(){

    start();

    test();

    ausgabe();

    getchar();

    return 0;

}

Schon mal danke für die Bewertung im vorraus:

[Klotzkopp]

- iostream.h ist veraltet, nimm iostream

- start() und ausgabe() unterscheiden sich nur minimal, das könnte man noch schön zusammenfassen

- Die Sonderbehandlung, ob z größer als laenge-1 ist, ist überflüssig, da dieser Fall nie eintritt. Eigentlich kannst du z komplett weglassen und statt dessen i+1 benutzen.

- deine Einrückung ist verbesserungsfähig

- das eine oder andere überflüssige Semikolon ist noch drin

- Kann es sein, dass du nicht genau weißt, was "static" bewirkt?

[VisualNero]

Ja hab mir noch mal das mit static angesehen, ist ja in dem Fall komplett überflüssig da globale Variablen sowieso immer static sind hätte nur sinn wenn sie lokal wären.

Und das mit dem z hab ich auch verstanden hatte mich da mit der funktion des programms vertan dachte das die letzte mit der ersten getausch wird aber ist ja nicht er Fall.

Jetzt möchte ich nur wissen was ich beim einrücken besser machen kann, auser bei den forschleifen von start und augabe bzw nur ausgabe da ich start jetzt weg gelassen hab?

[Klotzkopp]

Jetzt möchte ich nur wissen was ich beim einrücken besser machen kann, auser bei den forschleifen von start und augabe ?

Der gesamte Körper der Funktion sort ist anscheinend doppelt eingerückt. Das war's aber auch schon

[VisualNero]

So hab das jetzt alles schön eingerückt und noch Kommentare hinzugefügt.

Danke für deine Hilfe und bis zum nächsten mal.