AGB  ·  Datenschutz  ·  Impressum  







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

Problem mit Quicksort-Implementierung

Ein Thema von Shimau · begonnen am 10. Jun 2009 · letzter Beitrag vom 15. Jun 2009
 
Shimau

Registriert seit: 8. Jun 2009
Ort: Leipzig
14 Beiträge
 
Delphi 7 Personal
 
#5

Re: Problem mit Quicksort-Implementierung

  Alt 10. Jun 2009, 17:11
Der Zugriff ist auch extrem langsam, nur ich wollts zum verständniss und Probe ma mit Integerwerten machen. Also ma noch was zum Algo: Es ist ein rekursiver:

Delphi-Quellcode:
Procedure TForm1.QuickSort(Anf,Ende:integer);
var i, j, p, q, k: Integer;
    tausch: integer;{für Dreieckstausch} 
    v: integer;
Begin
  i:= Anf-1;
  p:= Anf-1; //Anfangsdekl.
  j:= Ende;
  q:= Ende;
  v:= Zahlen[Ende];

    Repeat
      inc( i ); //inc~um 1 erhöhen
      While (Zahlen[i] > v) Do
      Begin
        inc( i );
      End;

      dec( j ); //dec~ um 1 vermindern //Die Schleife ist ähnlich wie bei Satty67
      While (v > Zahlen[j]) Do //nur mit Dreieckstausch statt Swap(), macht
      Begin //aber genau dasselbe
        dec( j );
        If (j < Anf) Then Break; //Break~Verlasse die Schleife
      End;

      If (i >= j) Then Break;

      Zahlen[i]:=tausch; //Dreieckstausch
      Zahlen[i]:=Zahlen[j];
      Zahlen[j]:=tausch;

      If (Zahlen[i] = v) Then
      Begin
        inc( p );
        Zahlen[i]:=tausch;
        Zahlen[i]:=Zahlen[p];
        Zahlen[p]:=tausch;
      End;

      If (Zahlen[j] = v) Then
      Begin
        dec( q );
        Zahlen[q]:=tausch;
        Zahlen[q]:=Zahlen[j];
        Zahlen[j]:=tausch;
      End;
    until (j < i);

    Zahlen[i]:=tausch;
    Zahlen[i]:=Zahlen[Ende];
    Zahlen[Ende]:=tausch;
    j:= i-1;
    inc( i );

    k:= Anf;
    While (k < p) Do //hier werden gleiche Werte wie der Pivot
    Begin // einfach vor/hinter den Pivot sortiert
      inc( k ); //weil man sie ja nicht mehr mitsortieren muss
      dec( j );
      Zahlen[k]:=tausch;
      Zahlen[k]:=Zahlen[j];
      Zahlen[j]:=tausch;
    End;

    k:= Ende-1;
    While (k > q) Do
    Begin
      dec( k );
      inc( i );
      Zahlen[i]:=tausch;
      Zahlen[i]:=Zahlen[k];
      Zahlen[k]:=tausch;
    End;

    QuickSort( Anf, j); //Aufspaltung 2 Teilmengen, Rekursion
    QuickSort( i, Ende);
  End;
PS: Und ich meinte mit ich glaub dass es stimmt die Vergleichsoperatoren und wollte ausdrücklen, dass ich nciht mehr weiter weiss.
  Mit Zitat antworten Zitat
 


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 22:42 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