Problem bei selbstgeschriebenem Quicksort :(

Hallo nochmal!

Weiß nicht, ob das das passende Forum ist, aber:
Habe versucht, einen kleinen Quicksort nach Sedgewick zu schreiben.
Bei bis zu 100 Zahlen treten noch keine Probleme auf, bei 10000 bleibt leider alles unsortiert

Falls jemand Lust hat, sich durch meinen Code zu quälen, würde ich mich sehr freuen!
Anbei: Bin ein Programmierneuling und es sei vorangestellt, dass der Code wahrscheinlich nicht der empfehlenswerteste ist ^^".

Findet jemand meinen Fehler? Hab alles durchgedacht und komm nicht drauf

Vielen Dank im Voraus!!

#include <iostream>
#include <time.h>
#include <stdlib.h>

#define DIM 10000

using namespace std;

int quicksort (int* feld, int feldgroesse)
{
    if (feldgroesse <= 1)
        return 1;

    int i = 0;
    int j = feldgroesse - 2;
    int pivot = feld[feldgroesse - 1];
    int temp;

    while (i<j)
    {
          while(feld[i] < pivot && i < feldgroesse) i++;
          while(feld[j] > pivot && j >= 0) j--;

          if(i < j)
          {
               temp = feld[i];
               feld[i] = feld[j];
               feld[j] = temp;
          }

    }

    if(pivot <= feld[i])
    {   temp = feld[feldgroesse - 1];
        feld[feldgroesse - 1] = feld[i];
        feld[i] = temp;
    }

    quicksort(&feld[0], j+1);
    quicksort(&feld[i], feldgroesse - (j+1));

    return 0;

}

int main()
{
    int feld[DIM];
    int i;
    srand((unsigned) time(NULL));

    for (i=0; i<DIM; i++)
        feld[i] = rand();

    for (i = 0; i<DIM; i++)
    {
        cout << feld[i] << "\t";

        if(!((i+1)%10))
                   cout << "\n";
    }

    quicksort(feld, DIM);
    cout << "\n\n\n";

    for (i = 0; i<DIM; i++)
    {
        cout << feld[i] << "\t";

        if(!((i+1)%10))
                   cout << "\n";
    }

system("pause");
return 0;
}

_matze

Seenitall schrieb:

Hab alles durchgedacht und komm nicht drauf

Anstatt den Code nur zu betrachten und durchzudenken, solltest du die Möglichkeiten des Debuggers nutzen und den Ablauf nachvollziehen, während das Programm läuft (Haltepunkte, schrittweises Ausführen usw.). So kommt man eigentlich immer schnell auf den Fehler. Diese Möglichkeiten werden von Anfängern gerne ignoriert.

unskilled

Tip: Endlosschleife

*hust* Ja klar, dass ich an den Debugger nicht gedacht habe!

.
.
.

Was ist denn ein Debugger?

Hmmm... also ich habe davon gehört - aber geht der Debugger denn in die Details meiner Quicksortfunktion? Ich meine, der Sortiervorgang verläuft ja eh im Hintergrund. Und bei kleinen Zahlen um die 100 klappts ja prima mit dem Sortieren, nur bei den großen wird es immer unsortierter.

Kann mir da ein Debugger wirklich helfen?

Denn das Programm funktioniert ja - es ist wahrscheinlich ein Logikfehler bei meinen ganzen Indizes, oder nicht?

Und das mit der Endlosschleife versteh ich nicht? Denn das Prog kommt ja zu einem Ende und gibt die Liste aus. Oder wie ist das zu verstehen?

Tut mir Leid, wenn ich offenbar nicht mal eure Ratschläge verstehe!
Ich sollte, wohl lieber das Programmieren ganz lassen, was?!

unskilled

unskilled schrieb:

Tip: Endlosschleife

sry, ich glaub, ich hab was übersehen

ja, der debugger kann so etwas....

bb

Tobiking2

Seenitall schrieb:

Kann mir da ein Debugger wirklich helfen?

Denn das Programm funktioniert ja - es ist wahrscheinlich ein Logikfehler bei meinen ganzen Indizes, oder nicht?

Genau dafür ist der Debugger da, bei einem lauffähigen Programm die Logikfehler zu finden. Du kannst dein Programm halt während der Ausführung pausieren, dir den Inhalt sämtlicher Variablen angucken und es dann schritt für schritt laufen lassen um zu sehen was passiert.

_matze

Ich habe ja ein paar Stichwörter genannt. Denen solltest du mal nachgehen.

Hier etwas ausführlicher:
http://www.c-plusplus.net/forum/viewtopic-var-t-is-242371-and-highlight-is-.html

Seenitall schrieb:

Und das mit der Endlosschleife versteh ich nicht?

Das versteht eh keiner. Aber egal. Die Zahlen sind sortiert. Vielleicht mal die reine Ausgabe überarbeiten ?

Also ich hab's mit dem Debugger probiert (dem von Codeblocks)
aber offenbar weiß ich damit nicht richtig umzugehen.

Was ich noch rausgefunden habe ist, dass wenn ich die Größe der Zufallszahlen herunterdrehe, dass der Sortiervorgang bereits bei einer kleineren Anzahl von Zahlen (so um die 50) schiefläuft. Komisch...

Seltsam...

Naja gut, danke für Eure Hilfe!

blub* 0

Bei Codeblocks setzt du einfach mit F5 einen Breakpoint an eine Stelle. Mit F7 kannst du dann Zeile für Zeile durchgehen. Oder du drückst die Knöpfe in der Zeile mit roten X zum Abbrechen des Programms. Da ist auch ein Button mit Extra Optionen dort solltest du Watches auswählen damit du dir die ganzen Variablen im Speicher ansehen kannst.

Seenitall schrieb:

Was ich noch rausgefunden habe ist, dass wenn ich die Größe der Zufallszahlen herunterdrehe, dass der Sortiervorgang bereits bei einer kleineren Anzahl von Zahlen (so um die 50) schiefläuft. Komisch...

Schon mal ans Vorzeichen gedacht ? -> (int(!) feld)

Ans Vorzeichen?
Ich addiere und subtrahiere ja nirgends.. wo sollte ich da einen Überlauf haben?
Oder wie ist das gemeint?

Hab jetzt mit dem Debugger ein wenig rumprobiert und durch die Watches gesehen (danke für den Tipp! ), dass sich bei größeren Zahlenmengen nach einigen Schleifendruchgängen tatsächlich riesen Zahlen einschmuggeln. Komm aber nicht dahinter, woher die kommen.

Offenbar greif ich vlt während der Schleife auf Speicherelemente außerhalb meines Felds zu?! hmmm...

Tobiking2

if(pivot <= feld[i])
{  
    temp = feld[feldgroesse - 1];
    feld[feldgroesse - 1] = feld[i];
    feld[i] = temp;
}

quicksort(&feld[0], j+1);    // Eher i+1 oder besser noch i-1, da das i-te Element die endgültige Position bereits besitzt
quicksort(&feld[i], feldgroesse - (j+1)); // Beginnt dann mit i+1 und ist feldgroesse - (i+2) lang.

Vielen Dank für den Tipp und dafür dass du dich eingelesen hast!

Leider funktioniert das bei mir immer noch nicht - hab wohl noch an anderer Stelle den Wurm drin :((.

Bis zu 1000 Werte werden jetzt "nahezu" sortiert - eine Hand voll Ausreisser sind dabei.
Ab 1500 gibt er noch das unsortierte Array aus...