Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Quicksort fehler

Dude566 - Fr 06.02.09 20:11
Titel: Quicksort fehler

Also hier habe ich mal eine Prozedur die ein Array mit 1000 Speicherplätzen, welches mit Zufallszahlen im Wertebereich von 1 bis 5000 befüllt ist, sortiert.

Das Problem ist nur wenn ich sie dann Sortieren möchte, stürzt mir das Programm ohne eine Fehlermeldung ab.

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:

public
  procedure qsort (links, rechts : integer);

procedure TForm1.qsort; 
   var
      i, j, pivot, hilf : integer; // Pivot ist der Vergleichswert zum Teilen
     begin
     i := links;
     j := rechts;
       if i < j then begin
          pivot := zahlen[(links)-(rechts) div 2];
       Repeat
             while zahlen[i] < pivot do Inc(i);
             while zahlen[j] > pivot do Dec(i);
         if i <= j then
            begin
            hilf := zahlen[i];
            zahlen[i] := zahlen[j];
            zahlen[j] := hilf;
            Inc(i);
            Dec(j);
            end;
       until (i>j);
       qsort(1, j);
       qsort(1000, i );
       for i := 1 to 1000 do ListBox2.Items.Add(IntToStr(zahlen[i]));
                     end;
     end;

procedure TForm1.Button2Click(Sender: TObject);
begin
ListBox2.Clear;
qsort(1, 1000);
end;

Gruß Dude566

Narses - Fr 06.02.09 20:38
Titel: Re: Quicksort fehler

Moin!

Dude566 hat folgendes geschrieben :

Das Problem ist nur wenn ich sie dann Sortieren möchte, stürzt mir das Programm ohne eine Fehlermeldung ab.

Und, was hast du schon zur Fehlersuche unternommen? Vielleicht mal ein paar Debugausgaben und etwas weniger Elemente, um das mal Schrittweise durchzugehen? :nixweiss:

cu
Narses

jfheins - Fr 06.02.09 20:51

1. Schalte zum Debuggen bitte mal die Bereichsprüfung in den Compilieroptionen an ;)

2.

Delphi-Quelltext

1:	pivot := zahlen[(links)-(rechts) div 2];

http://de.wikipedia.org/wiki/Punktrechnung_vor_Strichrechnung ;)

Webo - Fr 06.02.09 21:15
Titel: Re: Quicksort fehler

Dude566 hat folgendes geschrieben :

stürzt mir das Programm ohne eine Fehlermeldung ab.

Hängt es sich auf oder beendet es einfach ?

Wenn es sich nur aufhängt solltest du darüber nachdenken, ob das Programm in der Zeit vielleicht einfach nur sortiert ? Je nach Code, Rechner und Inhalt kann das schon mal länger dauern.

ub60 - Sa 07.02.09 02:13

So auf den ersten Blick sehe ich 2 Fehler. Richtig ist es so:

Delphi-Quelltext

1:
2:
3:

  pivot := zahlen[(links+rechts) div 2];
  ...
  qsort(i,1000);

ub60

jaenicke - Sa 07.02.09 03:02
Titel: Re: Quicksort fehler

Dude566 hat folgendes geschrieben :

Delphi-Quelltext

1:
2:
3:
4:

public
  procedure qsort (links, rechts : integer);

procedure TForm1.qsort;

Auch wenn das leider so funktioniert:
Schreib besser die Parameter dazu, dann kommt man nicht so leicht durcheinander...

Delphi-Quelltext

1:
2:
3:
4:

public
  procedure qsort (links, rechts : integer);

procedure TForm1.qsort(links, rechts : integer);

Und eine bessere Formatierung (Einrückung) des Quelltextes wäre auch sinnvoll.

Ich weiß: Beides ist kein Fehler, trägt aber zum Machen von Fehlern bei. ;-)

Die Fehler wurden ja bereits gesagt, der letztere kam vielleicht daher, dass du nicht die Parameter dazugeschrieben hattest.

Dude566 - Sa 07.02.09 14:20

jfheins hat folgendes geschrieben :

1. Schalte zum Debuggen bitte mal die Bereichsprüfung in den Compilieroptionen an ;)

2.

Delphi-Quelltext

1:	pivot := zahlen[(links)-(rechts) div 2];

http://de.wikipedia.org/wiki/Punktrechnung_vor_Strichrechnung ;)

Ja, ich weis das Punkt vor Strich geht, aber es stand genau so an der Tafel, hatte aber vergessen zu Fragen ob es wirklich so ist.

Und wo schalte ich die Bereichsprüfung an? Schritte? Ich finde es so nicht.

Webo hat folgendes geschrieben :

Dude566 hat folgendes geschrieben :

stürzt mir das Programm ohne eine Fehlermeldung ab.

Nein es hängt sich wirklich auf, und dauert nicht einfach nur lange.
Und beenden will es sich dann auch nicht mehr lassen.

jaenicke hat folgendes geschrieben :

Dude566 hat folgendes geschrieben :

Delphi-Quelltext

1:
2:
3:
4:

public
  procedure qsort (links, rechts : integer);

procedure TForm1.qsort;

Auch wenn das leider so funktioniert:
Schreib besser die Parameter dazu, dann kommt man nicht so leicht durcheinander...

Delphi-Quelltext

1:
2:
3:
4:

public
  procedure qsort (links, rechts : integer);

procedure TForm1.qsort(links, rechts : integer);

Ok das mit der Übersichtlichkeit ist wahr, da habe ich manchmal meine Probleme und bin
mir nicht sicher wo ich wie einrücken sollte.

Gibt es da irgendwelche Regeln oder Vorlagen die weit verbreitet sind?

Edit: Nach den vorgeschlagenen Verbesserungen funktioniert es immer nocht nicht, wie schalte ich denn die Bereichsprüfung ein?

Thorsten83 - Sa 07.02.09 14:38

Hey,
hab zwar nicht die ganz große Ahnung von Delphi, aber

Quelltext

1:
2:

while zahlen[i] < pivot do Inc(i);
while zahlen[j] > pivot do Dec(i);

sieht auf jeden Fall nicht richtig aus :)

Dude566 - Sa 07.02.09 14:44

Wieso das ist der Vergleich und das eventuelle Weiterrücken im Teilarray.

Thorsten83 - Sa 07.02.09 14:51

Hey,

ja, aber du benutzt beide Male i, was dazu führen müsste dass du einfach endlos da hängen bleibst...

jaenicke - Sa 07.02.09 14:53

Dude566 hat folgendes geschrieben :

Und wo schalte ich die Bereichsprüfung an? Schritte? Ich finde es so nicht.

Projekt --> Optionen... --> Compiler --> Laufzeitfehler --> Bereichsüberprüfung

Dude566 hat folgendes geschrieben :

Nein es hängt sich wirklich auf, und dauert nicht einfach nur lange.
Und beenden will es sich dann auch nicht mehr lassen.

Naja, aufhängen heißt vermutlich Endlosschleife...

Und das ist ja auch kein Wunder:

Delphi-Quelltext

1:
2:

while zahlen[j] > pivot do 
  Dec(i);

Wie soll durch eine Änderung von i die Bedingung anders werden? :gruebel:

Das hattest du aber behoben?

ub60 hat folgendes geschrieben :

Delphi-Quelltext

1:	qsort(i,1000);

Dude566 hat folgendes geschrieben :

Sicher:
http://dn.codegear.com/article/10280
http://www.delphi-treff.de/delphi-styleguide/
Hier wäre das so übersichtlicher (dein Originalquelltext ohne Korrekturen):

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:

procedure TForm1.qsort(links, rechts : integer);
var
  i, j, pivot, hilf : integer; // Pivot ist der Vergleichswert zum Teilen
begin
  i := links;
  j := rechts;
  if i < j then
  begin
    pivot := zahlen[(links)-(rechts) div 2];
    repeat
      while zahlen[i] < pivot do
        Inc(i);
      while zahlen[j] > pivot do 
        Dec(i);
      if i <= j then
      begin
        hilf := zahlen[i];
        zahlen[i] := zahlen[j];
        zahlen[j] := hilf;
        Inc(i);
        Dec(j);
      end;
    until (i>j);
    qsort(1, j);
    qsort(1000, i );
    for i := 1 to 1000 do
      ListBox2.Items.Add(IntToStr(zahlen[i]));
  end;
end;

Dann kommst du beim end auch wieder vorne an...

ub60 - Sa 07.02.09 14:57

So, heute nacht war ich wohl doch etwas müde, so dass mir eine Menge Fehler nicht aufgefallen sind. :roll:

Bei der zweiten Schleife hattest Du i dekrementiert, da muss j hin.
Die if-then-Anweisungen müssen vor den Aufruf von Quicksort, damit wird gleichzeitig die Abbruchbedingung gesichert. Am Anfang bringt das nichts.
Die 1 und die 1000 im rekursiven Aufruf sind zwar für den ersten Aufruf sinnvoll, später müssen sie aber durch die jeweilige linke und rechte Grenze ersetzt werden.
Die Schleife mit der Ausgabe hat in Quicksort überhaupt nichts zu suchen! Die Ausgabe sollte erst nach dem Aufruf von Quicksort erfolgen.

So sollte es jetzt wirklich funktionieren :wink: ;

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:

procedure TForm1.qsort(links, rechts : Integer);
var i, j, pivot, hilf : integer; // Pivot ist der Vergleichswert zum Teilen
begin
  i := links;
  j := rechts;
  pivot := zahlen[(links+rechts) div 2];
  Repeat
    while zahlen[i] < pivot do Inc(i);
    while zahlen[j] > pivot do Dec(j);
    if i <= j then
      begin
        hilf := zahlen[i];
        zahlen[i] := zahlen[j];
        zahlen[j] := hilf;
        Inc(i);
        Dec(j);
      end;
  until (i>j);
  if links<j then qsort(links, j);
  if i<rechts then qsort(i, rechts );
end;

ub60

Dude566 - Sa 07.02.09 15:38

Oh man waren da schusselige Fehler drin, man merkt mir fehlt die Praxis.^^

Aber funktionieren will es immer noch nicht....ich suche und suche...

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:

// Quicksort
procedure TForm1.qsort (links, rechts : integer);
var
   i, j, pivot, hilf : integer;
begin
     i := links;
     j := rechts;
       if i < j then begin
          pivot := zahlen[(links+rechts) div 2];    // Pivotwert zuweisen
       Repeat
             while zahlen[i] < pivot do Inc(i);    // Vergleich
             while zahlen[j] > pivot do Dec(i);
         if i <= j then
            // Dreieckstausch
            begin
            hilf := zahlen[i];
            zahlen[i] := zahlen[j];
            zahlen[j] := hilf;
            Inc(i);
            Dec(j);
            end;
       until (i>j);
       // rekursiver Aufruf
       if links < j then qsort(links, j);
       if rechts > i then qsort(i, rechts);
                     end;
end;


// Randomize
procedure TForm1.FormCreate(Sender: TObject);
begin
     randomize;
end;


// Zahlen erzeugen & ausgeben
procedure TForm1.Button1Click(Sender: TObject);
var
   i : integer;
begin
ListBox1.Clear;
     for i := 1 to 1000 do
         begin
         zahlen[i] := random(5001)+1;
         ListBox1.Items.Add(IntToStr(zahlen[i]));
         end;
end;


// Aufruf qsort & Ausgabe
procedure TForm1.Button2Click(Sender: TObject);
var
   i : integer;
begin
ListBox2.Clear;
qsort(1, 1000);
         for i := 1 to 1000 do ListBox2.Items.Add(IntToStr(zahlen[i]));
end;

end.

jaenicke - Sa 07.02.09 15:49

Dude566 hat folgendes geschrieben :

Aber funktionieren will es immer noch nicht....ich suche und suche...

Delphi-Quelltext

1:
2:

             while zahlen[i] < pivot do Inc(i);    // Vergleich
             while zahlen[j] > pivot do Dec(i);

Das Thema hatten wir doch schon... :roll:

Thorsten83 - Sa 07.02.09 15:50

Hey,
erstmal ist der Fehler immer noch drin,

Quelltext

1:	while zahlen[j] > pivot do Dec(i);

Überleg mal was dein Programm macht, wenn i=j ist :)
edit: also in der "repeat (...) until(...)"-Schleife

Dude566 - Sa 07.02.09 15:53

F*** vergessen...is mir das peinlich. :oops:

Ja super jetzt funktioniert es!

Danke an euch.

Dude566 - Mi 11.02.09 21:05

So läuft alles prima, habe noch eine grafische Darstellung des Sortiervorgangs gemacht.

Das Programm läuft aber nur stabil und hängt sich nicht auf, wenn man nebenbei nach dem Start kein anderes Programm oder Fenster in Benutzung hat.

Wenn man dies nicht beachtet, bleibt es scheinbar hängen, schaut man nach kurzer Zeit wieder darauf ist einfach garnichts gezeichnet, obwohl es schon damit angefangen hatte.

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:

// Quicksort
procedure TForm1.qsort (links, rechts : integer);
var
   i, j, pivot, hilf : integer;
begin
     i := links;
     j := rechts;
       if i < j then begin
          pivot := zahlen[(links+rechts) div 2];    // Pivotwert zuweisen
       Repeat
             while zahlen[i] < pivot do Inc(i);    // Vergleich
             while zahlen[j] > pivot do Dec(j);
         if i <= j then
            // Dreieckstausch
            begin
            hilf := zahlen[i];
            zahlen[i] := zahlen[j];
            zahlen[j] := hilf;
            Inc(i);
            Dec(j);
            end;
       until (i>j);
       // rekursiver Aufruf
       if links < j then qsort(links, j);
       if rechts > i then qsort(i, rechts);
                     end;
       paint;
end;

// Zeichnen
procedure TForm1.paint;
var
   i, j, k : integer;
   punkt, punkt2, posi : integer;
begin
PaintBox1.Refresh;
punkt  := 0;
punkt2 := 0;
posi := 0;
PaintBox1.Canvas.Pen.Color := clRed;
for k := 1 to 200 do
    begin
    posi := posi +2;
    PaintBox1.Canvas.MoveTo (posi, 400);
    PaintBox1.Canvas.LineTo (posi, 400 - (zahlen[k]));
    sleep(1);
    end;

PaintBox1.Canvas.Pen.Color := clBlack;
     PaintBox1.Canvas.MoveTo (0,0);
     PaintBox1.Canvas.LineTo (0,400);
     PaintBox1.Canvas.LineTo (400,400);
for i := 1 to 40 do begin
                    punkt := punkt + 10;
                    PaintBox1.Canvas.MoveTo (punkt,400);
                    PaintBox1.Canvas.LineTo (punkt,395);
                    end;
for j := 1 to 40 do begin
                    punkt2 := punkt2 + 10;
                    PaintBox1.Canvas.MoveTo (0, punkt2);
                    PaintBox1.Canvas.LineTo (5, punkt2);
                    end;
end;


// Randomize
procedure TForm1.FormCreate(Sender: TObject);
begin
     randomize;
end;


// Zahlen erzeugen & ausgeben
procedure TForm1.Button1Click(Sender: TObject);
var
   i : integer;
begin
ListBox1.Clear;
     for i := 1 to 200 do
         begin
         zahlen[i] := random(401)+1;
         ListBox1.Items.Add(IntToStr(zahlen[i]));
         end;
paint;
end;


// Aufruf qsort & Ausgabe
procedure TForm1.Button2Click(Sender: TObject);
var
   i : integer;
begin
ListBox2.Clear;
qsort(1, 200);
         for i := 1 to 200 do ListBox2.Items.Add(IntToStr(zahlen[i]));
end;



end.

Im Anhang ist das fertige Programm zum Testen.

Gruß Dude566

jaenicke - Mi 11.02.09 21:24

Ist paint das OnPaint der PaintBox? Dann wäre es kein Wunder, denn du rufst darin PaintBox1.Refresh; auf. Und das wiederum ruft ja Paint auf --> Endlosschleife.

Zudem: Wozu zeichnest du jedesmal alles neu, das flackert doch nur, wenn du das ohne Hintergrundbitmap machst. Schau dir einmal die mitgelieferte Demo zu Threads und Sortieren an. ;-)
Die liegt bei Turbo Delphi unter:

Quelltext

1:	C:\Program Files\Borland\BDS\4.0\Demos\DelphiWin32\VCLWin32\Threads

Bzw unter älteren Versionen unter:

Quelltext

1:	C:\Program Files\Borland\DelphiX\Demos\Threads

Zudem hier ein Beispiel zur TPaintBox selbst:
http://www.michael-puff.de/Developer/Delphi/Code-Snippets/OffScreenBitmap.shtml

Dein Beispiel sieht bei mir ohnehin seltsam aus. Die Titelleiste sieht uralt aus, ich weiß nicht genau warum, aber die neue Oberfläche funktioniert bei deinem Programm nicht.

Dude566 - Mi 11.02.09 23:46

Ja, aber wenn ich das Refresh wegnehme überzeichnet er mir ja alles, und so sehe ich dann ja während des Sortieren nicht die Veränderungen in der PaintBox.

Zitat:

Dein Beispiel sieht bei mir ohnehin seltsam aus. Die Titelleiste sieht uralt aus, ich weiß nicht genau warum, aber die neue Oberfläche funktioniert bei deinem Programm nicht.

Was meinst du damit? Ich habe nichts am Borderstyle verändert. :shock:

jaenicke - Do 12.02.09 00:53

Dude566 hat folgendes geschrieben :

Ja, aber wenn ich das Refresh wegnehme überzeichnet er mir ja alles, und so sehe ich dann ja während des Sortieren nicht die Veränderungen in der PaintBox.

Zeichne doch einfach ein Rechteck und lösche damit den Inhalt. Eigentlich wäre es aber besser bei einem Austausch nur diesen direkt darzustellen.

Dude566 hat folgendes geschrieben :

Zitat:

Dein Beispiel sieht bei mir ohnehin seltsam aus. Die Titelleiste sieht uralt aus, ich weiß nicht genau warum, aber die neue Oberfläche funktioniert bei deinem Programm nicht.

Was meinst du damit? Ich habe nichts am Borderstyle verändert. :shock:

Siehe Anhang, so sieht dein Programm bei mir aus, ganz oben ist das normale Aussehen zu sehen (Standard-Systemstil), davor dein Programm. Die Scrollbars sind auch zu sehen, weil unter Vista der Rand breiter ist und damit bei gleicher Breite weniger Platz ist.

Dude566 - Do 12.02.09 17:06

Zur Titelleiste: Und woran kann das liegen, ich habe nichts verändert?

Zur PaintBox: Aber wenn ich jedes mal ein Rechteck darüber zeichne flackert es doch auch oder etwa nicht?

Edit: Es flackert auch.

Borderstyle:
user defined image

jaenicke - Do 12.02.09 18:49

Dude566 hat folgendes geschrieben :

Zur Titelleiste: Und woran kann das liegen, ich habe nichts verändert?

Keine Ahnung, ich kenne das eigentlich nur von 16-Bit-Programmen und Delphi 1, was bei dir ja nicht der Fall ist. :nixweiss:

Dude566 hat folgendes geschrieben :

Zur PaintBox: Aber wenn ich jedes mal ein Rechteck darüber zeichne flackert es doch auch oder etwa nicht?

Edit: Es flackert auch.

Setz in FormCreate einmal DoubleBuffered auf True. ;-)

Dude566 - Fr 13.02.09 00:21

Ok, es flackert nicht mehr so schnell, und es stürzt jetzt wenn ich ein anderes Fenster nebenbei öffne nicht mehr ab.

Und was bewirkt dieses DoubleBuffered?
Würde mich mal interessieren. :)

jaenicke - Fr 13.02.09 00:39

Das bewirkt die Zwischenspeicherung in einer Hintergrundbitmap, wie dir die Hilfe auch verrät, drück doch einfach mal F1...

Zitat:

When DoubleBuffered is false, the windowed control paints itself directly to the window. When DoubleBuffered is true, the windowed control paints itself to an in-memory bitmap that is then used to paint the window. Double buffering reduces the amount of flicker when the control repaints, but is more memory intensive.

Dude566 - Fr 13.02.09 14:36

Muss ich das ganze dann nachher besser nicht wieder auf Free setzen um kein Arbeitsspeicher zu verschwenden?

jaenicke - Fr 13.02.09 15:35

Mit dieser Hintergrundzwischenspeicherung hast du nichts zu tun, das passiert alles automatisch.

Nebenbei macht Vista das für alle Anwendungen noch einmal. Deshalb kann Vista bei einem Absturz auch das letzte Bild der Anwendung zeigen und aufhellen statt wie unter XP nur eine weiße Fläche.

Dude566 - Fr 13.02.09 15:51

Ok, wenn noch Probleme auftreten sollten melde ich mich wieder hier.

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!