AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Algorithmen, Datenstrukturen und Klassendesign Hab ein Stack Overflow, wenn ich mein Quicksort ausprobiere :(

Hab ein Stack Overflow, wenn ich mein Quicksort ausprobiere :(

Ein Thema von Caspar · begonnen am 8. Sep 2017 · letzter Beitrag vom 25. Sep 2017
Antwort Antwort
Seite 1 von 2  1 2   
Caspar
(Gast)

n/a Beiträge
 
#1

Hab ein Stack Overflow, wenn ich mein Quicksort ausprobiere :(

  Alt 8. Sep 2017, 19:13
Hey, ich bin relativ neu auf dem Forum, also seid ein wenig nachsichtig

Ich habe ein kleines Sortierprogramm geschrieben und habe ein klein Stack-Overflow, wenn ich auf den Knopf drücke.
ich habe ein String Grid, wo auf der einen Seite die Zufälligen Zahlen stehen und auf der anderen Seite die Sortierten.

Hier mein Code:

Code:
procedure Quicksort(l,r: Integer);
  var
    i,j,Mitte,Merke: Integer;

  begin
    i:=0;
    j:=999;
   Mitte:=Zahl[(0+999) div 2];
    repeat
      while Zahl[i]<Mitte do Inc(i);

      while Mitte<Zahl[j] do Dec(j);

      if i<=j then
        begin
          Merke:=Zahl[i];
          Zahl[i]:=Zahl[j];
          Zahl[j]:=Merke;
          Inc(i);
          Dec(j);
        end;
    until i>j;
    if 0<j then Quicksort(0,j);

    if i<999 then Quicksort(i,999);

  end;


 procedure TForm1.Button5Click(Sender: TObject);
 var a:integer;
begin
   Quicksort(0,999) ;

   For a:=0 to 999 do
 begin
  StringGrid1.Cells[1,a] := inttostr(Zahl[a]);
 end;


end;
Als Globale Variable habe ich "Zahl" als Array von 0 bis 999.

Zahl : Array[0..999] of Integer;


Ich bin noch recht unerfahren in Delphi, also bitte es leicht erklären

Geändert von Caspar ( 8. Sep 2017 um 19:15 Uhr)
  Mit Zitat antworten Zitat
Delphi-Laie

Registriert seit: 25. Nov 2005
1.474 Beiträge
 
Delphi 10.1 Berlin Starter
 
#2

AW: Hab ein Stack Overflow, wenn ich mein Quicksort ausprobiere :(

  Alt 8. Sep 2017, 19:24
Das ist kein Quick-, sondern ein Circlesort. Woher hast Du den Algorithmus? Edit: Das mit dem Circlesort nehme ich evtl. zurück....

Und der Stack wird erschöpft, weil die Rekursion nicht abbricht, sondern gegen unendlich strebt.

Geändert von Delphi-Laie ( 8. Sep 2017 um 19:28 Uhr)
  Mit Zitat antworten Zitat
Caspar
(Gast)

n/a Beiträge
 
#3

AW: Hab ein Stack Overflow, wenn ich mein Quicksort ausprobiere :(

  Alt 8. Sep 2017, 19:26
Ich habe das aus meinem Schulbuch, wo es auch als Quicksort beschrieben wurde
  Mit Zitat antworten Zitat
Delphi-Laie

Registriert seit: 25. Nov 2005
1.474 Beiträge
 
Delphi 10.1 Berlin Starter
 
#4

AW: Hab ein Stack Overflow, wenn ich mein Quicksort ausprobiere :(

  Alt 8. Sep 2017, 19:31
Ich habe das aus meinem Schulbuch, wo es auch als Quicksort beschrieben wurde
Ja, zog es auch schon vorsichtig zurück. Das Pivotelement läßt sich meinetwegen auch aus der Mitte entnehmen / gewinnen.

Die Prozedur ruft sich immer und immer wieder selbst auf, anstatt daß sich dieses Vorgehen irgendwann beendet. Deshalb ist der Stack irgendwann erschöpft.

j muß sich im Verlaufe der Aufrufe immer mehr 0, i immer mehr 999 annähern. Tut es das? Höchstwahrscheinlich nicht.

Edit: nimm mal statt

Mitte:=Zahl[(0+999) div 2];

besser

Mitte:= (i+j) div 2; (und nicht "Zahl[(i+j)"!)

Geändert von Delphi-Laie ( 8. Sep 2017 um 19:36 Uhr)
  Mit Zitat antworten Zitat
Caspar
(Gast)

n/a Beiträge
 
#5

AW: Hab ein Stack Overflow, wenn ich mein Quicksort ausprobiere :(

  Alt 8. Sep 2017, 19:40
Ne, das hat leider nicht funktioniert.
Es kommt immer noch die Fehlermeldung des Stackoverflow.
  Mit Zitat antworten Zitat
nahpets
(Gast)

n/a Beiträge
 
#6

AW: Hab ein Stack Overflow, wenn ich mein Quicksort ausprobiere :(

  Alt 8. Sep 2017, 19:53
Quicksort wird mit den Parametern l und r aufgerufen. Die werden innerhalb der Routine aber nie benutzt. Das kann so nicht stimmen, da sie den Bereich bestimmen, der sortiert werden soll.

Dashier ist mit an Sicherheit grenzender Wahrscheinlichkeit falsch:
Delphi-Quellcode:
i := 0;
j := 999;
Mitte := Zahl[(0+999) div 2];
i müsste eher = l sein und j = r.
Mitte muss die Mitte zwischen l und r sein.

eventuell etwa so?
Delphi-Quellcode:
i := l;
j := r;
Mitte := Zahl[(i + j) div 2];
  Mit Zitat antworten Zitat
Caspar
(Gast)

n/a Beiträge
 
#7

AW: Hab ein Stack Overflow, wenn ich mein Quicksort ausprobiere :(

  Alt 8. Sep 2017, 19:57
Ja, 0 ist im Prinzip l, da es auf dem String Grid ja kein Links und Rechts gibt ist Links dann oben, also 0.
Rechts / r ist dann unten, ergo 999.
  Mit Zitat antworten Zitat
nahpets
(Gast)

n/a Beiträge
 
#8

AW: Hab ein Stack Overflow, wenn ich mein Quicksort ausprobiere :(

  Alt 8. Sep 2017, 20:07
Nein, nur beim ersten Aufruf, danach wird jeweils neu entschieden, welcher Bereich sortiert werden soll. Das ist jeweils entweder die obere Hälfte des noch nicht sortierten Bereiches oder die untere Hälfte.

So wie Du das machst, wird bei jedem Aufruf immer alles sortiert und das rekursive, also mit jedem Aufruf immer alles und mit dem nächsten Aufruf wieder alles ... - daraus resultiert dann der Stackoverflow, weil die Rekursion nie beendet wird.

Ändere Deine Routine bitte mal entsprechend meines Vorschlages und prüfe, ob der Fehler weg ist, dann prüfe, ob die Sortierung korrekt ist, wenn nein, dann beschreibe uns bitte die aufgetretenen Fehler, damit wir weiterschauen können.

Das Ignorieren der Werte von l und r ist aber auf jeden Fall falsch.
  Mit Zitat antworten Zitat
Delphi-Laie

Registriert seit: 25. Nov 2005
1.474 Beiträge
 
Delphi 10.1 Berlin Starter
 
#9

AW: Hab ein Stack Overflow, wenn ich mein Quicksort ausprobiere :(

  Alt 8. Sep 2017, 20:36
Delphi-Quellcode:
i:=l
j:=r
am Prozeduranfang oder gleich l und r in der Prozedur verwenden.
  Mit Zitat antworten Zitat
Caspar
(Gast)

n/a Beiträge
 
#10

AW: Hab ein Stack Overflow, wenn ich mein Quicksort ausprobiere :(

  Alt 8. Sep 2017, 20:54
Ok, ich habe jetzt wie @nahpets gesagt hat alle "0" und "999" durch l und r ersetzt. Also für 0 l und für 999 l und es funktioniert!

Vielen Dank an euch alle, das ihr mir einerseits geholfen habt und anderseits so schnell geantwortet habt
Ich bin mir noch nicht ganz sicher warum es jetzt auf einmal klappt, aber ich glaube ich komme bald dahinter

Ich hoffe ich werde irgendwann auch mal so gut in Informatik, damit ich dann auch Anfängern, wie mir, helfen kann

Ich wünsche euch noch ein Angenehmen Abend!
Lg, Caspar
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 11:27 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz