Doppelt verkettete Liste sortieren

[Noobinator]

Huhu ich bins mal wieder.

Ich habe ein kleines Problem.

und zwar habe ich eine Doppelt verkettete Liste of einfach verkettete Liste

Diese Doppelt verkettete Liste möchte ich nun gerne sortieren und zwar nach der Länge der einfach verketteten Listen.

Dazu haben die einfachen Listen eine

Delphi-Quellcode:

Function GetAnzahl(Anker:Tliste):integer;

Nun Suche ich einen geeigneten Algorithmus.

Anforderungen:

• max lineares Zeitverhalten (wenn es möglich ist)
• Keine Rekursionen, nur Iterationen (ganz ganz wichtig da ich mit bis zu 1 mio Werten arbeiten muss).
• für viele Werte geeignet (200k aufwärts)

Um Fragen vorzubeugen warum ich kein Array of Liste nehme:
Laufzeit mir Array: 2h
Laufzeit mit Liste: 3 min

Pointer umhängen ist nunmal einfach schneller ;)

Habe schon gegoogelt, aber entweder ich bin zu Dumm, oder es hatte noch niemand dieses Problem^^

Mfg
Noobinator

[mkinzler]

Sortierung hat ja nichts mit der Art der Speicherung der daten zu tun. alle alle Methoden QuckSort, BubbleSort, ShellSort, die bei Arraya funktionieren sollten auch in Listen möglich sein.

[DerDan]

Hi,


also spätestens wenn du wieder indiziert auf deine Liste zugreifen kannst, dann sollten alle Algos gehen.

so ganz auf die schnelle:

ein dynamisches Array (mit Zeigern) aufmachen in den du Zeiger auf deine Sortier-Elemente (deine einfach verketteten Listen) ablegst,
dann mit Quicksort sortieren und danach wieder deine Doppel-verkettet Liste bauen.

Übrigens hängt es auch davon ab inwieweit eine Menge schon sortiert ist, welches der günstigste Algo ist.


Wie stark variiert denn die "länge" deiner einfach verketteten Liste?


mfg


DerDan

[Noobinator]

Zitat:

Wie stark variiert denn die "länge" deiner einfach verketteten Liste?

zwischen 1 - x Elemente wobei x auch 500 000 Elemente sein können ;)

Zitat:

Sortierung hat ja nichts mit der Art der Speicherung der daten zu tun. alle alle Methoden QuckSort, BubbleSort, ShellSort, die bei Arraya funktionieren sollten auch in Listen möglich sein.

Nuja aber Einzelne Algorithmen benötigen einen Indizierten Zugriff wie z.B. Quicksort, und sind somit weniger für meine Absichten geeignet, da ich diesen Zugriff auch erst implementieren müsste ;)

[Sidorion]

Bau Dir einen sortierten Binärbaum auf. Jetzt kannst Du Deine Elemente der doppelten Liste eins nach dem anderen in den Baum stecken und aus diesem Baum dann wieder eine doppelte Liste zusammenstellen.
Das geht so: das erste Element der Liste wird die Wurzel. das zweite wird verglichen und wenns kleiner ist, wird es das linke Kind, ansonsten das Rechte. Ist das jeweilige Kind schon besetzt, dann wird mit diesem wieder verglichen usw.
Wenn der Baum fertig ist, fängst Du gaaaanz links an. Dies ist das kleinste Element und kommt als erstes in die neue Liste. Danach sein Elternknoten. Hat dieser ein rechtes Kind, gehst Du in diesem rechten Teilbaum gaaaanz nach links usw.

Damit die Einfügesuche beschleunigt wird, kannst Du die Tiefe des Baumes reduzieren, indem Du nach jedem Einfügen den Baum austarierst. Dazu solltest Du aber mal nach nem Tut über Binärbäume suchen, das würde hier zu weit führen.

Dieses Verfahren hätte wenigstens nur O=n*lb(n), im Gegensatz zu bubbleSort (n^2). Der ist der einzige, der mir gerade einfällt, der auch ohne Indexierung auskommt.

Ach ja: und sorge dafür dass die Anzahl der Elemente jedes Elements nur einmal berechnet wird, das spart auch ganz schön Zeit.

[Noobinator]

Ok ich habe das Ganze jetzt gelöst, indem ich einfach die Werte aus meiner Hauptliste in eine Temporäre Liste geordnet eingefügt habe.

Das ganze funktioniert einwandfrei und der Zeitaufwand geht auch noch.
Der Speicheraufwand bleibt wie vorher, da ich einsortierte Werte sofort aus der Hauptliste lösche.
die Doppelte Verkettung hat sich damit auch erledigt, da ich diese nur für Quicksort implementiert hatte ;)

Hier mein Code:

Delphi-Quellcode:

procedure sort;
var help:ptoLe; // Hilfspointer to Listenelement
    tmp:TDliste; // Hilfsliste
begin
  neu(tmp);
  while leer(mylist)=false do
    begin
      geordnet_einfuegen(tmp,mylist.Value); // werte in Hilfsliste packen
      vorne_loeschen(mylist); // aus Liste Loeschen
    end;
  mylist := tmp; // Pointer der Mainlist auf die Templiste umsetzen
end;

Delphi-Quellcode:

procedure geordnet_einfuegen(var anker:PtoLe;Value:TsetOfReal);
var help,tmp:PtoLe;
begin
   if leer(anker) = true then // 1. Sonderfall: Liste Leer
     hinten_anfuegen(anker,Value)
   else
     begin
        help := anker; // Hilfspointer setzen
        if help.Value.Getanzahl >= Value.Getanzahl then // 2. Sonderfall: an erster Stelle muss eingefügt werden
          begin
              new(tmp);
              tmp.Value := Value;
              tmp.next := anker;
              anker := tmp;
          end
        else
          begin
            while (help.next <> nil) and (help.next.Value.Getanzahl < Value.Getanzahl) do
              help := help.next; // Ansonsten durchgehen und schauen wo man einfügen kann
                if help.next <> nil then
                  begin
                     new(tmp);
                     tmp.Value := Value;
                     tmp.next := help.next;
                     help.next := tmp;
                  end
                else
                  hinten_anfuegen(anker,Value); // Sonderfall: letzte Stelle
          end;
     end;
end;

Somit wäre das erledigt.
Bin aber immer noch für Verbesserungen offen.

[quendolineDD]

Delphi-Quellcode:

while leer(mylist)=false do

ändern in

Delphi-Quellcode:

while not leer(mylist) do

[Noobinator]

Zitat:

Zitat von quendolineDD

Delphi-Quellcode:

while leer(mylist)=false do

ändern in

Delphi-Quellcode:

while not leer(mylist) do

Grund?

ist doch das selbe^^

[mkinzler]

Nein man vergleicht einen Booleanwert nie auf True oder False!

[quendolineDD]

Irgendwo gab es mal einen Thread, wo sehr gut beschriebn wird, wie gefährlich das ist, so auf boolsche Ausdrücke hin zu überprüfen. Habe den aber eben nicht gefunden :-\

An sich scheint es das gleiche zu sein, aber deine Abfrage kann auch mal dicke in die Hose gehen ;)