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
Delphi-Laie

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

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

  Alt 8. Sep 2017, 18: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 18:28 Uhr)
  Mit Zitat antworten Zitat
Caspar
(Gast)

n/a Beiträge
 
#2

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

  Alt 8. Sep 2017, 18: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
 
#3

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

  Alt 8. Sep 2017, 18: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 18:36 Uhr)
  Mit Zitat antworten Zitat
Caspar
(Gast)

n/a Beiträge
 
#4

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

  Alt 8. Sep 2017, 18: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
 
#5

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

  Alt 8. Sep 2017, 18: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
 
#6

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

  Alt 8. Sep 2017, 18: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
 
#7

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

  Alt 8. Sep 2017, 19: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
Antwort Antwort

 
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 09:17 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz