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 1 von 2  1 2   
Der schöne Günther

Registriert seit: 6. Mär 2013
6.093 Beiträge
 
Delphi 10 Seattle Enterprise
 
#1

Stabiles Sortieren

  Alt 24. Mai 2017, 18:13
Meistens reicht mir das Sortieren über TArray.Sort<T>(..) da man auch einen eigenen Comparer angeben kann. Laut Doku ist die Implementierung ein QuickSort, also nicht stabil - Es ist also nicht garantiert dass Elemente mit gleicher Wertigkeit nach dem Sortieren auch noch in der gleichen Reihenfolge zueinander stehen.

Gibt es in der RTL ein stabiles Sortierverfahren oder muss man das selbst machen?
  Mit Zitat antworten Zitat
Benutzerbild von Zacherl
Zacherl

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

AW: Stabiles Sortieren

  Alt 24. Mai 2017, 18:45
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.
Projekte:
- GitHub (Profil, zyantific)
- zYan Disassembler Engine ( Zydis Online, Zydis GitHub)
  Mit Zitat antworten Zitat
Benutzerbild von Uwe Raabe
Uwe Raabe

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

AW: Stabiles Sortieren

  Alt 24. Mai 2017, 18:56
Du kannst auch statt T einen Record aus T und dem Index sortieren. Der Comparer muss dann natürlich bei gleichem T den Index vergleichen.
Uwe Raabe
Certified Delphi Master Developer
Embarcadero MVP
Blog: The Art of Delphi Programming
  Mit Zitat antworten Zitat
Der schöne Günther

Registriert seit: 6. Mär 2013
6.093 Beiträge
 
Delphi 10 Seattle Enterprise
 
#4

AW: Stabiles Sortieren

  Alt 24. Mai 2017, 19:10
Danke für den Bubble Sort. Der ist mir vielleicht sogar lieber, denn Geschwindigkeit ist mir grade nicht wichtig, Speicher aber schon eher.

Ich habe einfach mal den Pseudo-Code auf Wikipedia abgetippt, noch keine vernünftigen Tests, aber im Debugger scheinen die Dinge richtig sortiert zu sein.

Delphi-Quellcode:
uses
  System.SysUtils,
  System.Generics.Collections,
  System.Generics.Defaults;

type
   _TArray = class(System.Generics.TArray)
      private
         /// <param name="input">
            /// Muss mindestens zwei Elemente enthalten
         /// </param>
         class procedure SplitValues<T>(
            const   input:   TArray<T>;
            out      left:   TArray<T>;
            out      right:   TArray<T>
         );
         class function MergeValues<T>(const left, right: TArray<T>; const Comparer:
            IComparer<T>): TArray<T>;
      public
         class procedure MergeSort<T>(var Values: TArray<T>; const Comparer:
            IComparer<T>); static;
   end;

{ _TArray }

class procedure _TArray.MergeSort<T>(var Values: TArray<T>; const Comparer:
   IComparer<T>);
var
   leftValues, rightValues: TArray<T>;
begin
    // Quelle :https://de.wikipedia.org/w/index.php?title=Mergesort&oldid=164969688#Implementierung
   if Length(Values) <= 1 then Exit;

   splitValues<T>(Values, leftValues, rightValues);
   _TArray.MergeSort<T>(leftValues, Comparer);
   _TArray.MergeSort<T>(rightValues, Comparer);

   Values := MergeValues<T>(leftValues, rightValues, Comparer);
end;

class function _TArray.MergeValues<T>(
   const left, right: TArray<T>;
   const Comparer: IComparer<T>
): TArray<T>;
var
   leftList:   TList<T>;
   rightList:   TList<T>;
   resultList:   TList<T>;

begin
    // Quelle: https://de.wikipedia.org/w/index.php?title=Mergesort&oldid=164969688#Implementierung
   resultList := TList<T>.Create();

   leftList := TList<T>.Create(); leftList.AddRange(left);
   rightList := TList<T>.Create(); rightList.AddRange(right);

   // "solange (linkeListe und rechteListe nicht leer)"
   while( (leftList.Count > 0) and (rightList.Count > 0) ) do begin
      // "falls (erstes Element der linkeListe <= erstes Element der rechteListe)"
      if (Comparer.Compare(leftList.First(), rightList.First()) <= 0) then
         // "dann füge erstes Element linkeListe in die neueListe hinten ein und entferne es aus linkeListe"
         begin
            resultList.Add(   leftList.First() );
            leftList.Delete(0);
         end
      else
         // "sonst füge erstes Element rechteListe in die neueListe hinten ein und entferne es aus rechteListe"
         begin
            resultList.Add( rightList.First() );
            rightList.Delete(0);
         end
      ;
   end;

   // "solange (linkeListe nicht leer)"
   while(leftList.Count > 0) do begin
      // "füge erstes Element linkeListe in die neueListe hinten ein und entferne es aus linkeListe"
      resultList.Add( leftList.First() );
      leftList.Delete(0);
   end;

   // "solange (rechteListe nicht leer)"
   while(rightList.Count > 0) do begin
      // "füge erstes Element rechteListe in die neueListe hinten ein und entferne es aus rechteListe"
      resultList.Add( rightList.First() );
      rightList.Delete(0);
    end;

   Result := resultList.ToArray();
end;

class procedure _TArray.SplitValues<T>(
   const input: TArray<T>;
   out left, right: TArray<T>
);
var
   inputLength:    Integer;
   leftLength:      Integer;
begin
   inputLength := Length(input);
   leftLength := inputLength div 2;

   SetLength(left, leftLength);
   SetLength(right, inputLength - leftLength);

   TArray.Copy<T>(input, left, Low(input), 0, leftLength);
   TArray.Copy<T>(input, right, Low(input)+leftLength, 0, inputLength - leftLength);
end;
Ich glaube ich nehme trotzdem deinen BubbleSort


Das mit dem Wrapper-Record und Comparer der zusätzlich noch über den Index vergleicht ist (typisch Uwe) ziemlich tricky, da wäre ich nie drauf gekommen.


PS: Und ja, in jedem MergeValues neue TList-Instanzen erstellen (Bonus: Und niemals freigeben) ist vielleicht auch nicht so dolle. Ich will aber langsam Feierabend haben...
  Mit Zitat antworten Zitat
Benutzerbild von Zacherl
Zacherl

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

AW: Stabiles Sortieren

  Alt 24. Mai 2017, 20:05
Du kannst auch statt T einen Record aus T und dem Index sortieren. Der Comparer muss dann natürlich bei gleichem T den Index vergleichen.
Kannst du das evtl. anhand von etwas Code nochmal erläutern? Das klingt interessant, aber ich bin grade nicht sicher, ob du das gleiche meinst, was ich mir darunter vorstelle
Projekte:
- GitHub (Profil, zyantific)
- zYan Disassembler Engine ( Zydis Online, Zydis GitHub)
  Mit Zitat antworten Zitat
Benutzerbild von p80286
p80286

Registriert seit: 28. Apr 2008
Ort: Stolberg (Rhl)
6.659 Beiträge
 
FreePascal / Lazarus
 
#6

AW: Stabiles Sortieren

  Alt 24. Mai 2017, 21:46
es soll allerdings auch schnellere Sortierverfahren, die stabil sind z.b. BinaryTree...

Gruß
K-H
Programme gehorchen nicht Deinen Absichten sondern Deinen Anweisungen
R.E.D retired error detector
  Mit Zitat antworten Zitat
Namenloser

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

AW: Stabiles Sortieren

  Alt 24. Mai 2017, 21:58
es soll allerdings auch schnellere Sortierverfahren, die stabil sind z.b. BinaryTree...
Die einfachste Variante ist immer noch, einfach einen aufsteigenden Index an das Sortierkriterium anzuhängen, sodass die Sortierung immer eindeutig ist. So bekommt man jedes Sortierverfahren stabil, selbst Quicksort.

Oder wenn du Objekte sortierst (also Pointer), dann kannst du auch einfach gleich die Pointer vergleichen.

Also in der Art:
Delphi-Quellcode:

TRecord = record
  Name: String;
  Id: Integer;
end;

function Compare(const a, b: TRecord): integer;
begin
  Result := StrCompare(a.Name, b.Name);
  if (Result = 0) then
    Result := b.Id - a.Id;
end;
  Mit Zitat antworten Zitat
Benutzerbild von p80286
p80286

Registriert seit: 28. Apr 2008
Ort: Stolberg (Rhl)
6.659 Beiträge
 
FreePascal / Lazarus
 
#8

AW: Stabiles Sortieren

  Alt 24. Mai 2017, 22:30
dann kannst du auch einfach gleich die Pointer vergleichen.
Ausgerechnet das funktioniert nicht, da Du Dich nicht darauf verlassen kannst, daß Pointer(Speicheradressen) nicht zufällig sind. Du brauchst immer eine Relation zwischen den Daten(sätzen) sei es .next/.last oder der Index eines Arrays.

Gruß
K-H
Programme gehorchen nicht Deinen Absichten sondern Deinen Anweisungen
R.E.D retired error detector
  Mit Zitat antworten Zitat
Delphi-Laie

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

AW: Stabiles Sortieren

  Alt 24. Mai 2017, 22:47
es soll allerdings auch schnellere Sortierverfahren, die stabil sind z.b. BinaryTree...
Binarytreesort benötigt nach meinem Wissen erheblich zusätzlichen Speicher und ist zudem kompliziert. Das Gefummel mit den dynamischen Datenstrukturen ist sogar bei Informatikern fehleranfällig und zurecht die "Königsdisziplin".

Wenn es denn ein einfacher ("elementarer") Sortieralgorithmus sein soll, dann rate ich statt zu Bubblesort dann eher zu Insertionsort, das ist ein Quentchen schneller.

Wenn man es komplizierter akzeptiert und / oder zusätzlicher Speicher keine Rolle spielt (i.d.R. benötigt man aber dann maximal den Speicher, den die zu sortierende Elementemenge benötigt, noch einmal zusätzlich), dann stehen einem eine schier unglaubliche Fülle an Sortierverfahren zur Verfügung, auch stabile, die zudem fast alle schneller als Bubble- bzw. Insertionsort sind.
  Mit Zitat antworten Zitat
Namenloser

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

AW: Stabiles Sortieren

  Alt 24. Mai 2017, 23:08
Ausgerechnet das funktioniert nicht, da Du Dich nicht darauf verlassen kannst, daß Pointer(Speicheradressen) nicht zufällig sind. Du brauchst immer eine Relation zwischen den Daten(sätzen) sei es .next/.last oder der Index eines Arrays.
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.
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2   

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 05:45 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