AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Tutorials Delphi Tutorial: Sortier-Algorithmen I+II
Tutorial durchsuchen
Ansicht
Themen-Optionen

Tutorial: Sortier-Algorithmen I+II

Ein Tutorial von Daniel · begonnen am 28. Jun 2002 · letzter Beitrag vom 12. Okt 2015
Antwort Antwort
Seite 4 von 4   « Erste     234   
Benutzerbild von Alexander Roth
Alexander Roth

Registriert seit: 17. Mai 2004
Ort: Kenn
574 Beiträge
 
Turbo Delphi für Win32
 
#1

Re: Tutorial: Sortier-Algorithmen I+II

  Alt 4. Apr 2006, 19:59
Zitat von Daniel:
Delphi-Quellcode:
Procedure ShellSort;
var i, j, h, v : Integer;
Begin
  h:= 1;
  Repeat
    h:= (3 * h) +1;
  Until (h > N);

  Repeat
    h:= (h div 3);
    For i:= (h+1) To N Do
    Begin
      v:= Data[i];
      j:= i;

      While ((j > h) and (Data[j-h] > v)) Do
      Begin
        Data[j]:= Data[j-h];
        dec( j, h );
      End;
      Data[j]:= v;
    End;
  Until (h = 1);
End;
Unten das habe ich von Alexander Franz (http://www.alexander-franz.de):
Delphi-Quellcode:
function TMainFrm.shellSort(zahlen : IntArray): Int64;
var
  i, j, k, tmp: Integer;
  n : Int64;
const
  h : Array[0..15] of Integer = (1391376, 463792, 198768, 86961, 33936, 13776,
                                4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1);
begin
  for k:=0 to Length(h)-1 do
  begin
    for i:=h[k] to Length(zahlen) do
    begin
      j := i;
      tmp := zahlen[j];
      while ((j>h[k]) AND (tmp<zahlen[j-h[k]])) do
      begin
        zahlen[j] := zahlen[j-h[k]];
        Dec(j, h[k]);
        Inc(n);
      end;
      zahlen[j] := tmp;
    end;
  end;
  Result := n;
end;
Ich kopiere nur äußerst ungern einen Code und will ihn gern immer selbst verstehen:
Also Shellsort habe ich von der Logik her kapiert:
1. halbe Arraylänge auseinander Einträge vergleich und wenn nötig vertauschen
2. viertel Arraylänge auseinander Einträge vergleich und wenn nötig vertauschen
3.....
...

Also die 2 äußeren Schleifen sind mir klar. Aber was die innere da soll? Das ist doch einfach nur eine Bedingung, wenn die eine größer ist als die andere dann vertausche, ansonsten mache nix.
Und die Bedingung j>h[k]ist auch irgendwie komisch, man hat doch in der for schleife davor genau das festgelegt, dass diese Bedingung immer erfüllt ist.
Und es kann ja nix bingen Dec(j, h[k]); für den nächsten Durchlauf zu beschreiben, denn j wird ja wieder i zugewiesen. Es kann also nur für die innerste Schleife relevant sein. Doch was macht die da. Die macht doch die Bedingung (j>h[k]) lediglich unerfüllt. Damit läuft die innerste Schleife immer nur genau 1 mal durch. Damit kann man es auch in einer if Bedingung schreiben.

Wisst ihr eine Erklärung?
Alexander Roth
Ich bin umgestiegen auf: Lazarus und Ubuntu! Alles OpenSource!

Besuch doch mal: www.roth.us.ms
  Mit Zitat antworten Zitat
Benutzerbild von Lee500
Lee500

Registriert seit: 18. Sep 2006
39 Beiträge
 
Delphi 2010 Architect
 
#2

Re: Tutorial: Sortier-Algorithmen I+II

  Alt 29. Jun 2008, 15:19
Hiho,

Ich hab mich ma an den ShellSort algorythmus gewagt. Er sortiert jetzt wunderbar, bis auf den letzten Datensatz.
Delphi-Quellcode:
Procedure TForm1.ShellSort();
var i, j, h : Integer;
v: Trun;
Begin
  h:= 1;
  Repeat
    h:= (3 * h) +1;
  Until (h > Length(Runs)-1);

  Repeat
    h:= (h div 3);
    For i:= (h+1) To Length(Runs)-1 Do
    Begin
      v:= Runs[i-1];
      j:= i;

      While ((j > h) and (Runs[j-h-1].sumtime > v.sumtime)) Do
      Begin
        Runs[j-1]:= Runs[j-h-1];
        dec(j,h);
      End;
      Runs[j-1]:=v;
    End;
  Until (h = 1);
End;
TRun ist ein eigenes record mit ein paar variablen, wie z.B. das benutzte sumtime. Ich will also die array-Datensätze des arrays Runs nach sumtime sortieren. Er sortiert wie gesagt alles, nur den letzten Datensatz nicht. Es wäre wirklich toll wenn ihr meinen Denkfehler finden würdet.

Gruß Lee500
  Mit Zitat antworten Zitat
Larsi

Registriert seit: 10. Feb 2007
2.262 Beiträge
 
Delphi 2007 Professional
 
#3

Re: Tutorial: Sortier-Algorithmen I+II

  Alt 29. Jun 2008, 16:04
Mach ein neues Thema auf. Hier darfst du nur Fragen und Anregungen und Kritik über Daniels Tut loswerden.
Ein Tag ohne Delphi ist ein verlorener Tag!

Homepage zu meinem neuen Programm: StreamZ
  Mit Zitat antworten Zitat
Benutzerbild von Lee500
Lee500

Registriert seit: 18. Sep 2006
39 Beiträge
 
Delphi 2010 Architect
 
#4

Re: Tutorial: Sortier-Algorithmen I+II

  Alt 29. Jun 2008, 16:22
Das ist doch eine Frage zum Tut. Im Tut steht ja der ShellSort-Algorytmus, der den letzten Datensatz nicht berücksichtigt. So gesehen ist es eine Frage zum Tut.
  Mit Zitat antworten Zitat
marabu

Registriert seit: 6. Apr 2005
10.109 Beiträge
 
#5

Re: Tutorial: Sortier-Algorithmen I+II

  Alt 29. Jun 2008, 16:28
Hallo,

@Lee500: Du musst fremden Code immer an deine Bedürfnisse anpassen. Daniel verwendet ein Array Data[1..N], für dein Array hingegen gilt Low(Runs) = 0.

@Larsi: Was du da machst ist falsch. Wenn dir etwas auffällt, was nicht in Ordnung ist, dann benachrichtige einen Mod.

Freundliche Grüße
  Mit Zitat antworten Zitat
Benutzerbild von Lee500
Lee500

Registriert seit: 18. Sep 2006
39 Beiträge
 
Delphi 2010 Architect
 
#6

Re: Tutorial: Sortier-Algorithmen I+II

  Alt 29. Jun 2008, 16:33
Hi,

@marabu ich habe ja bereits überall Length(Runs)-1 und das ganze so angepasst wie im Post von Daniel mit der TListBox. Von daher müsste es so funktionieren. Wenn ich das nicht berücksichtigt hätte, wäre im übrigen der erste Datensatz der, der nicht mitsortiert würde.

Hab das Problem jetzt behoben:
Delphi-Quellcode:
Procedure TForm1.ShellSort();
var i, j, h : Integer;
v: Trun;
Begin
  h:= 1;
  Repeat
    h:= (3 * h) +1;
  Until (h > Length(Runs));

  Repeat
    h:= (h div 3);
    For i:= (h+1) To Length(Runs) Do
    Begin
      v:= Runs[i-1];
      j:= i;

      While ((j > h) and (Runs[j-h-1].sumtime > v.sumtime)) Do
      Begin
        Runs[j-1]:= Runs[j-h-1];
        dec(j,h);
      End;
      Runs[j-1]:=v;
    End;
  Until (h = 1);
End;
So funktioniert es wunderbar.

Gruß Lee500
  Mit Zitat antworten Zitat
zeustates

Registriert seit: 6. Okt 2015
2 Beiträge
 
FreePascal / Lazarus
 
#7

AW: Tutorial: Sortier-Algorithmen I+II

  Alt 12. Okt 2015, 15:59
hallo ich habe mich mal an den Mergesort gewagt.
nur leider tut er nicht. Eig sollte er nur bekomm ich in zeile 25 immer ein "sigsegev" bei einem begin. Ich werde nicht schlau daraus.

hier ist mal mein code als anhang
Angehängte Dateien
Dateityp: pas mergesort.pas (1,4 KB, 11x aufgerufen)
  Mit Zitat antworten Zitat
Delphi-Laie

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

AW: Tutorial: Sortier-Algorithmen I+II

  Alt 12. Okt 2015, 17:29
hallo ich habe mich mal an den Mergesort gewagt.
nur leider tut er nicht. Eig sollte er nur bekomm ich in zeile 25 immer ein "sigsegev" bei einem begin. Ich werde nicht schlau daraus.

hier ist mal mein code als anhang
Sigsev? Das kenne ich von Lazarus(-Compilaten). Benutzt Du Lazarus?

Mergesort benutze ich in rekursiver und "halb-rekursiver" Form in meinem Sortierkino, es läuft auch mit Lazarus-Compilaten.

Geändert von Delphi-Laie (12. Okt 2015 um 20:45 Uhr)
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 4 von 4   « Erste     234   


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:32 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