Probleme mit Quicksort

[micha_at_info]

Hallo,

ich bin neu hier im Forum und auch Programmieren ist für mich Neuland.

Nun habe ich ein Problem beim Implementieren von Quicksort. Den Algorithmus habe ich ja verstanden, aber irgendwie sortiert mein Programm nicht richtig, findet jemand den Fehler?

#include<iostream>

    using namespace std;


    int quicksort(int* Array, int l, int r)

    {

    int i,j,t,q,v;

       if(r>l)

       {


              i=l-1;

              j=r-1;

              v=Array[r-1];

            while(1)

              {

                      do i++; while(Array[i]<v);

                      do j--; while(Array[j]>v);

                      if(i>=j) 

                      {

                      goto pivot;

                      }

                      else 

                      {

                      t=Array[i];

                      Array[i]=Array[j];

                      Array[j]=t;

                      }

              } 

              pivot: 

              {

              q=Array[i];

              Array[i]=Array[r-1];

              Array[r-1]=q;              

              quicksort(Array,l,i-1);

              quicksort(Array,i+1,r); 

              }

        }

     return 0;

    }


    int main()

    {

      //Erzeuge benutzerdefiniertes Array

      int i,j,n;

      cout<<"Bitte geben sie die Laenge der Zahlenfolge ein: ";

      cin>>n;


      int Array[n];


      for(i=0;i<n;i++)

      {

        cout<<"Zahl eingeben: ";

        cin>>Array[i];                

      }


      //unsortierte Ausgabe

      for(i=0;i<n;i++)

      {

        cout<<Array[i]<<" ";

      }

      cout<<endl;


      //quicksort funktionsaufruf

      quicksort(Array,1,n);



      //sortierte Ausgabe

      for(int i=0;i<n;i=i+1)

      {

        cout<<Array[i]<<" ";

      }

      cout<<endl; 


      system("pause");

    }

[flashpixx]

GoTo verwendet man heute nicht mehr ! Es ist definitiv sehr verpönt in höheren Programmiersprachen. Quicksort ist ein Divide-and-Conquer Verfahren. Ich bin bereit mir den Code anzuschauen, wenn Du es ordentlich ohne Goto programmierst und zusätzlich erklärst warum Deine quicksort-Funktion einen Returnwert hat, der immer "0" ist. Ebenso solltest Du einmal überdenken, was Call-By-Reference bzw Call-By-Value bezügl. Deines Arrays ist

Phil

[micha_at_info]

Hallo,

vielen dank für die schnelle Antwort. Ich versuche es ohne goto hinzubekommen, obwohl ich leider nicht genau weiss wie.

Zu der "return 0" Rückgabe: Ich habe gelesen, dass eine Funktion immer ein return benötigt und eigentlich macht das auch keine Probleme. Am liebsten würde ich ja return Array schreiben, aber das geht ja nicht.

Ich weiss auch, dass das Problem irgendwie mit diesem "goto pivot" zusammenhängt. Wenn ich das rausnehme macht das Programm ja genau das, was der Algorithmus sagt, wenn sich i und j nicht überschneiden. Also muss ich irgendwie den divide Teil richtig implementieren.

Ach so, was ich noch anmerken möchte ist, dass es sich hier nicht um eine Hausaufgabe handelt oder ähnliches, sondern ich bereite mich auf eine Prüfung vor und möchte alles verstehen. Mir ist schon klar, dass es fertige Implementierungen und Vereinfachungen gibt und ich bitte auch nicht darum, dass einer eine fertige Lösung präsentiert, sondern so ein Tip wie von flshpixx ist wirklich Klasse.

Ich mach mich jetzt über dieses goto her.

cya

Bearbeitet 9. Mai 2009 von micha_at_info

[flashpixx]

Danke für das Lob.

Evtl als Tipp: Schreibe das ganze als Klasse, dann hast Du das ganze als ordentliche Kapselung. An die Klasse übergibst Du die Größe des Arrays und führst intern Dein Array als Matrix, in der Du zeilenweise das (halb)sortierte Array ablegst (spaltenweise die Elemente), um jeden Sortierschritt zu sehen, ebenso das Pivotelement. Überlade dann cout noch und Du kannst die Ausgabe ordentlich machen

Phil

[micha_at_info]

Ich habe jetzt erst versucht das goto durch eine Funktion zu ersetzen. Aber es gibt irgendeinen Fehler.

    #include<iostream>

    using namespace std;



    int pivot(int* Array, int i, int r);

    int quicksort(int* Array, int l, int r)

    {

    int i,j,t,v;

       if(r>l)

       {


              i=l-1;

              j=r-1;

              v=Array[r-1];

            while(1)

              {

                      do i++; while(Array[i]<v);

                      do j--; while(Array[j]>v);

                      if(i>=j) 

                      {

                      pivot(Array,i,r);

                      }

                      else 

                      {

                      t=Array[i];

                      Array[i]=Array[j];

                      Array[j]=t;

                      }

              } 


        }

    }


    int pivot(int* Array, int i, int r)

    {

              int q;

              int l=0;


              q=Array[i];

              Array[i]=Array[r-1];

              Array[r-1]=q;              

              quicksort(Array,l,i-1);

              quicksort(Array,i+1,r); 


    }


    int main()

    {

      //Erzeuge benutzerdefiniertes Array

      int i,j,n;

      cout<<"Bitte geben sie die Laenge der Zahlenfolge ein: ";

      cin>>n;


      int Array[n];


      for(i=0;i<n;i++)

      {

        cout<<"Zahl eingeben: ";

        cin>>Array[i];                

      }


      //unsortierte Ausgabe

      for(i=0;i<n;i++)

      {

        cout<<Array[i]<<" ";

      }

      cout<<endl;


      //quicksort funktionsaufruf

      quicksort(Array,1,n);



      //sortierte Ausgabe

      for(int i=0;i<n;i=i+1)

      {

        cout<<Array[i]<<" ";

      }

      cout<<endl; 


      system("pause");

    }

[Klotzkopp]

Aber es gibt irgendeinen Fehler.

Ein wichtiger Tipp für die Zukunft: Mit "irgendein Fehler" kann niemand etwas anfangen. Mag ja sein, dass dir die Fehlermeldungen des Compilers nicht viel sagen, aber den Helfern hier vielleicht schon, deswegen wäre es besser, wenn du den Wortlaut der Fehlermeldung nicht verschweigst.

Und zum goto-Problem:

Da du einfach nur aus der Schleife rausspringst, reicht es, wenn du dein goto durch ein einfaches break ersetzt.

[micha_at_info]

Hallo,

der Compiler gibt ja keine Fehlermeldung, sonst würde ich ja nicht den Code posten, aber trotzdem danke. Werde es mal mit break probieren.

[Klotzkopp]

der Compiler gibt ja keine Fehlermeldung, sonst würde ich ja nicht den Code posten,

Aber es geht doch kein Fenster auf mit dem Text "Es ist irgendein Fehler aufgetreten", oder?

Je genauer du das Fehlverhalten beschreibst, desto besser können wir dir helfen.