AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Thema durchsuchen
Ansicht
Themen-Optionen

Quicksort-Rätsel

Ein Thema von striderx · begonnen am 12. Nov 2014 · letzter Beitrag vom 13. Nov 2014
Antwort Antwort
Namenloser

Registriert seit: 7. Jun 2006
Ort: Karlsruhe
3.724 Beiträge
 
FreePascal / Lazarus
 
#1

AW: Quicksort-Rätsel

  Alt 12. Nov 2014, 21:49
case aData[X].RecType of
Bist du sicher, dass RecType einen der Werte hat, die du im Case behandelst? Möglicherweise tritt keiner der Fälle dort ein, sodass für alle Vergleiche False zurückgeliefert wird. Da QuickSort kein stabiles Verfahren ist, werden dabei die Einträge durcheinandergewirbelt.
  Mit Zitat antworten Zitat
striderx

Registriert seit: 11. Feb 2007
Ort: Bergisch Gladbach
207 Beiträge
 
Delphi 10.4 Sydney
 
#2

AW: Quicksort-Rätsel

  Alt 12. Nov 2014, 21:58
Ja, da bin ich sicher.

Und: Mit dem Insertion-Sort, der ja dieselbe Vergleichs-Funktion benutzt, klappt es ohne Probleme.
  Mit Zitat antworten Zitat
Namenloser

Registriert seit: 7. Jun 2006
Ort: Karlsruhe
3.724 Beiträge
 
FreePascal / Lazarus
 
#3

AW: Quicksort-Rätsel

  Alt 12. Nov 2014, 22:02
Hmm, okay, auf den zweiten Blick:

Delphi-Quellcode:
    while Less(tStart, 0) do Inc(tStart);
    while Less(0, tStop) do Dec(tStop);
Fehlt da nicht jeweils eine Abbruchbedingung gegen das Überschreiten der Array-Grenzen?

Edit: Außerdem:

aData[0] := aData[(tStart + tStop) DIV 2];
Da wird das erste Element ja einfach überschrieben. Wenn dann müsstest du die beiden Elemente vertauschen. Oder du lässt dieses Implementierungsdetail einfach weg und speicherst das Pivot-Element in einer lokalen Variable zwischen.

Geändert von Namenloser (12. Nov 2014 um 22:05 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von Uwe Raabe
Uwe Raabe

Registriert seit: 20. Jan 2006
Ort: Lübbecke
11.752 Beiträge
 
Delphi 12 Athens
 
#4

AW: Quicksort-Rätsel

  Alt 12. Nov 2014, 22:14
Hmm, okay, auf den zweiten Blick:

Delphi-Quellcode:
    while Less(tStart, 0) do Inc(tStart);
    while Less(0, tStop) do Dec(tStop);
Fehlt da nicht jeweils eine Abbruchbedingung gegen das Überschreiten der Array-Grenzen?

Edit: Außerdem:

aData[0] := aData[(tStart + tStop) DIV 2];
Da wird das erste Element ja einfach überschrieben. Wenn dann müsstest du die beiden Elemente vertauschen. Oder du lässt dieses Implementierungsdetail einfach weg und speicherst das Pivot-Element in einer lokalen Variable zwischen.

Ist zwar mächtig unsauber, aber das 0-Element wird offensichtlich nicht benutzt. Aus diesem Grund sollte auch die Abbruchbedingung erfüllt sein, da in dem 0-Element das Pivot-Element steht, und spätestens wenn die Schleife diese erreicht, bricht sie ab.
Uwe Raabe
Certified Delphi Master Developer
Embarcadero MVP
Blog: The Art of Delphi Programming
  Mit Zitat antworten Zitat
Namenloser

Registriert seit: 7. Jun 2006
Ort: Karlsruhe
3.724 Beiträge
 
FreePascal / Lazarus
 
#5

AW: Quicksort-Rätsel

  Alt 12. Nov 2014, 22:30
Das gilt aber nur für die eine Richtung, oder?

Und überhaupt: Fehlt da nicht irgendwie das „Herz“ von Quicksort, nämlich, dass die Elemente, die kleiner sind als das Pivot-Element, auf die eine Seite und alle anderen Elemente auf die andere Seite gepackt werden? Je länger ich auf diesen Code draufschaue, desto unklarer wird er mir.

Geändert von Namenloser (12. Nov 2014 um 22:44 Uhr)
  Mit Zitat antworten Zitat
striderx

Registriert seit: 11. Feb 2007
Ort: Bergisch Gladbach
207 Beiträge
 
Delphi 10.4 Sydney
 
#6

AW: Quicksort-Rätsel

  Alt 12. Nov 2014, 23:17
>>Fehlt da nicht irgendwie das „Herz“ von Quicksort ...<<

Das passiert m. E. hier:

Delphi-Quellcode:
    while Less(tStart, 0) do Inc(tStart);
    while Less(0, tStop) do Dec(tStop);
Mit der 0 wird der Pivot-Record referenziert, der in dem Array-Element 0 enthalten ist.
  Mit Zitat antworten Zitat
striderx

Registriert seit: 11. Feb 2007
Ort: Bergisch Gladbach
207 Beiträge
 
Delphi 10.4 Sydney
 
#7

AW: Quicksort-Rätsel

  Alt 12. Nov 2014, 23:34
Ich habe den Fehler gefunden - wie so oft lag er dort, wo man am wenigsten sucht:

Schuld war der Rückgabewert der Funktion 'GetArtistSurname', welche nicht alle Datensätze bis zum Ende durchlaufen und daher in einigen Fällen einen leeren String zurückgegeben hat.


Vielen Dank für Eure Bemühungen, das Brett vor meinem Kopf zu entfernen!!!

Geändert von striderx (12. Nov 2014 um 23:44 Uhr)
  Mit Zitat antworten Zitat
Namenloser

Registriert seit: 7. Jun 2006
Ort: Karlsruhe
3.724 Beiträge
 
FreePascal / Lazarus
 
#8

AW: Quicksort-Rätsel

  Alt 12. Nov 2014, 23:53
Das passiert m. E. hier:

Delphi-Quellcode:
    while Less(tStart, 0) do Inc(tStart);
    while Less(0, tStop) do Dec(tStop);
Okay, mag sein. Ich gebe zu, ich habe mir diese „iterative“ Quicksort-Variante bisher nie so genau angeschaut, weil ich das schon immer etwas verwirrend fand.

Wie auch immer, freut mich, dass du den Fehler trotzdem gefunden hast.
  Mit Zitat antworten Zitat
Antwort Antwort


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 20:03 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