AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

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
 
#8

Re: Problem mit Quicksort-Implementierung

  Alt 10. Jun 2009, 17:25
Komischerweise funktioniert bei mir der Insertionsort, aber nicht der Quicksort :

Delphi-Quellcode:
//Insertionsort
Procedure TForm1.Insertion(Anf,Ende:integer);
var i,j: Integer;
    v:integer;
Begin
  For i:= Anf+1 To Ende Do
  Begin
    v:= Zahlen[i];
    j:= i;
    While (j > Anf) and (Zahlen[j-1] < v) Do
    Begin
      Zahlen[j]:= Zahlen[j-1]; //Kleinere Elemente werden nach rechts gerückt
      dec( j );
    End;
    Zahlen[j]:= v; //dann Elemnt in Lücke einfügen
  End;
End;

//Quicksort
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;
  j:= Ende;
  q:= Ende;
  v:= Zahlen[Ende];

  If (Ende - Anf)+1 > 20 Then
  Begin
    Repeat
      inc( i ); //inc~um 1 erhöhen
      While (Zahlen[i] > v) Do
      Begin
        inc( i );
      End;

      dec( j ); //dec~ um 1 vermindern
      While (v > Zahlen[j]) Do
      Begin
        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
    Begin
      inc( k );
      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
    QuickSort( i, Ende);
  End
  else
  begin
    Insertion(Anf,Ende); //wenn <=20 Elemente Insertionsort statt Quicksort
  end;
End;
PS: Später werden statt Integer Eigenschaften von klassen sortiert, deren zugriff schon mehr an rechenaufwand erfordert als bei Integers.
  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 20:16 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