AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Stabiles Sortieren

Ein Thema von Der schöne Günther · begonnen am 24. Mai 2017 · letzter Beitrag vom 26. Mai 2017
Antwort Antwort
Seite 2 von 2     12
gammatester

Registriert seit: 6. Dez 2005
999 Beiträge
 
#11

AW: Stabiles Sortieren

  Alt 24. Mai 2017, 23:19
Sie sind zufällig, aber sie ändern sich aber nicht plötzlich zwischen zwei Sortierdurchläufen. Hier müsste man vielleicht genauer definieren, was man unter "stabil" versteht.
Allerdings müßten sie zu Anfang strikt monoton sein (kein Problem bei Arrays, aber da kan mann gleich die Indices nehmen).
  Mit Zitat antworten Zitat
Namenloser

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

AW: Stabiles Sortieren

  Alt 24. Mai 2017, 23:25
Ja ok, du hast streng genommen recht. Allerdings habe ich stabile Sortierverfahren bisher eigentlich immer nur gebraucht, wenn ich nicht wollte, dass die Einträge bei wiederholtem Sortieren zufällig hin- und herspringen. Ich hatte jetzt von der Ecke aus gedacht.
  Mit Zitat antworten Zitat
Amateurprofi

Registriert seit: 17. Nov 2005
Ort: Hamburg
1.057 Beiträge
 
Delphi XE2 Professional
 
#13

AW: Stabiles Sortieren

  Alt 25. Mai 2017, 12:14
Hatte das gleiche Problem und in der RTL leider nichts gefunden. Habe mir dann eine einfache BubbleSort Implementation in meine Array-Helper Klasse eingebaut:
Delphi-Quellcode:
class procedure TArrayHelper.Exchange<T>(var A: TArray<T>; Index1, Index2: Integer);
var
  Temp: T;
begin
  Temp := A[Index1];
  A[Index1] := A[Index2];
  A[Index2] := Temp;
end;

class procedure TArrayHelper.BubbleSort<T>(var A: TArray<T>; const Comparer: IComparer<T>);
var
  I: Integer;
  Done: Boolean;
begin
  repeat
    Done := true;
    for I := Low(A) to High(A) - 1 do
    begin
      if (Comparer.Compare(A[I], A[I + 1]) > 0) then
      begin
        Exchange<T>(A, I, I + 1);
        Done := false;
      end;
    end;
  until Done;
end;
Ist bei vielen Werten natürlich fürchterlich langsam. Wollte bei Gelegenheit mal MergeSort implementieren.
Ich verwende ein etwas anderes BubbleSort.
Hintergrund:
Nach dem Durchlauf der For ... Schleife steht das größte Element am Ende des Arrays.
Also muss beim nächsten Durchlauf das vorletzte Element nicht mehr mit dem letzten Element verglichen werden.
Das verringert die Anzahl der zu vergleichenden Elemente bei jedem Durchlauf um 1.


Delphi-Quellcode:
class procedure TArrayHelper.BubbleSort<T>(var A: TArray<T>; const Comparer: IComparer<T>);
var
  I,Last: Integer;
  Done: Boolean;
begin
  Last:=High(A);
  repeat
    Dec(Last)
    Done := true;
    for I := Low(A) to Last do
    begin
      if (Comparer.Compare(A[I], A[I + 1]) > 0) then
      begin
        Exchange<T>(A, I, I + 1);
        Done := false;
      end;
    end;
  until Done;
end;
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat
Benutzerbild von Zacherl
Zacherl

Registriert seit: 3. Sep 2004
4.629 Beiträge
 
Delphi 10.2 Tokyo Starter
 
#14

AW: Stabiles Sortieren

  Alt 26. Mai 2017, 14:12
Ich verwende ein etwas anderes BubbleSort.
Hintergrund:
Nach dem Durchlauf der For ... Schleife steht das größte Element am Ende des Arrays.
Also muss beim nächsten Durchlauf das vorletzte Element nicht mehr mit dem letzten Element verglichen werden.
Das verringert die Anzahl der zu vergleichenden Elemente bei jedem Durchlauf um 1.
Guter Einwand Sollte dann aber am Anfang vermutlich Last := High(A) - 1 sein, sonst kracht es beim Zugriff auf A[I + 1] .
Projekte:
- GitHub (Profil, zyantific)
- zYan Disassembler Engine ( Zydis Online, Zydis GitHub)
  Mit Zitat antworten Zitat
Amateurprofi

Registriert seit: 17. Nov 2005
Ort: Hamburg
1.057 Beiträge
 
Delphi XE2 Professional
 
#15

AW: Stabiles Sortieren

  Alt 26. Mai 2017, 15:21
Ich verwende ein etwas anderes BubbleSort.
Hintergrund:
Nach dem Durchlauf der For ... Schleife steht das größte Element am Ende des Arrays.
Also muss beim nächsten Durchlauf das vorletzte Element nicht mehr mit dem letzten Element verglichen werden.
Das verringert die Anzahl der zu vergleichenden Elemente bei jedem Durchlauf um 1.
Guter Einwand Sollte dann aber am Anfang vermutlich Last := High(A) - 1 sein, sonst kracht es beim Zugriff auf A[I + 1] .
Nein, beachte das Dec(Last) am Anfang der Repeat Schleife.
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat
Benutzerbild von Zacherl
Zacherl

Registriert seit: 3. Sep 2004
4.629 Beiträge
 
Delphi 10.2 Tokyo Starter
 
#16

AW: Stabiles Sortieren

  Alt 26. Mai 2017, 15:41
Nein, beachte das Dec(Last) am Anfang der Repeat Schleife.
Stimmt, das hatte ich in der Tat übersehen
Projekte:
- GitHub (Profil, zyantific)
- zYan Disassembler Engine ( Zydis Online, Zydis GitHub)
  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 07:56 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz