Quicksort fehler

Dude566 · Verfasst: Fr 06.02.09 20:11

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.

markieren

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

_________________
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen.

Narses · Verfasst: Fr 06.02.09 20:38

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

_________________
There are 10 types of people - those who understand binary and those who don´t.

jfheins · Beiträge: 918 Erhaltene Danke: 158 Win 10 VS 2013, VS2015

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

2.

markieren

Delphi-Quelltext

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

de.wikipedia.org/wik...g_vor_Strichrechnung

Webo · Verfasst: Fr 06.02.09 21:15

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.

_________________
Man kann nur das aus dem Ärmel schütteln, was man auch vorher reingesteckt hat.

ub60 · Beiträge: 764 Erhaltene Danke: 127

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

markieren

Delphi-Quelltext

1:
2:
3:

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

ub60

jaenicke · Verfasst: Sa 07.02.09 03:02

Dude566 hat folgendes geschrieben :

markieren

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...

markieren

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 · Verfasst: Sa 07.02.09 14:20

jfheins hat folgendes geschrieben :

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

2.

markieren

Delphi-Quelltext

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

de.wikipedia.org/wik...g_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.

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.

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 :

markieren

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...

markieren

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.

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?

_________________
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen.

Thorsten83 · Beiträge: 191 Erhaltene Danke: 1

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

markieren

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 · Verfasst: Sa 07.02.09 14:44

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

_________________
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen.

Thorsten83 · Beiträge: 191 Erhaltene Danke: 1

Hey,

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

jaenicke · Verfasst: 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:

markieren

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 :

markieren

Delphi-Quelltext

1:	qsort(i,1000);

Dude566 hat folgendes geschrieben :

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?

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

markieren

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 · Beiträge: 764 Erhaltene Danke: 127

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:

;

markieren

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 · Verfasst: 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...

markieren

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.

_________________
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen.

jaenicke · Verfasst: Sa 07.02.09 15:49

Dude566 hat folgendes geschrieben :

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

markieren

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 · Beiträge: 191 Erhaltene Danke: 1

Hey,
erstmal ist der Fehler immer noch drin,

markieren

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 · Verfasst: Sa 07.02.09 15:53

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

Ja super jetzt funktioniert es!

Danke an euch.

_________________
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen.

Dude566 · Verfasst: 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.

markieren

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

Einloggen, um Attachments anzusehen!

_________________
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen.

jaenicke · Verfasst: 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:

markieren

Quelltext

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

Bzw unter älteren Versionen unter:

markieren

Quelltext

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

Zudem hier ein Beispiel zur TPaintBox selbst:
www.michael-puff.de/...ffScreenBitmap.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 · Verfasst: 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:

_________________
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen.

jaenicke · Verfasst: 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.

Einloggen, um Attachments anzusehen!

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme