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 ;)

[Noobinator]

Zitat:

Zitat von 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 ;)

Zitat:

Nein man vergleicht einen Booleanwert nie auf True oder False!

also ich Hatte noch nie Probleme damit o.O

wenn ich hingegen

Delphi-Quellcode:

while leer(mylist) do

schriebe kann jeder compiler das anderst interpretieren.

Wer sagt mir denn das es in 10 Jahren nicht ein Compiler gibt, der diesen Ausdruck standardmäßig auf false Prüft, und nicht wie Delphi auf true?

und eigentlich wollte ich meine Proggs in 10 Jahren auch noch benutzen..

daher einfach true oder false dahinter o.O

aber such mal bitte den Artikel.. bin auch auf der Suche... das Interessiert mich jetzt.

[quendolineDD]

Gesucht und gefunden :)
hier kannst du ihn begutachten

Grüße

[Apollonius]

Zitat:

Wer sagt mir denn das es in 10 Jahren nicht ein Compiler gibt, der diesen Ausdruck standardmäßig auf false Prüft, und nicht wie Delphi auf true?

Sehr witzig: was wird dieser Compiler denn dann aus if a=b machen?

[mkinzler]

Falscher Thread

[Namenloser]

Zitat:

Zitat von Noobinator

Wer sagt mir denn das es in 10 Jahren nicht ein Compiler gibt, der diesen Ausdruck standardmäßig auf false Prüft, und nicht wie Delphi auf true?

Was sagt dir, dass in 10 jahren Delphi "=" imemr noch als Gleicheitszeichen interpretiert und nciht als ungleich :roll:

Die Sache ist einfach die, das Boolean intern ein Byte groß ist. Wenn dieses Byte den Wert 0 hat, bedeutet das "Aus". Jeder Wert <> 0 bedeutet "An".
Das Problem ist, dass die Konstanten True und False als 0 und 1 festgelegt sind. Wenn du also "=True" schreibst, wird also nicht auf Wahrheit überprüft, sondern auf die Zahl 1. Da kann es passieren, dass eine Prüfung false ergibt, obwohl sie wahr gewesen wäre: In VB bedeutet True beispielsweise nicht 1, sondern -1. Wenn du nun den Rückgabewert aus einer VB-Dll prüfst, wird deine Schreibweise imemr False ergeben!
Theoretisch könnte man zumindest "variable = false" schreiben statt "not variable", aber erstens ist letzteres kürzer und zweitens ist es konsequenter.

Ein kleines Konsolenprogramm zum Beweisen:

Delphi-Quellcode:

var
  b: boolean;
  s: string; // Für Readln
begin
  b := true;
  writeln('Test 1: b='+inttostr(ord(b)));
  if b then
    writeln(' a) Wahr')
  else
    writeln(' a) Falsch');
  if b=True then
    writeln(' b) Wahr')
  else
    writeln(' b) Falsch');

  b := boolean(byte(-1));
  writeln('Test 2: b='+inttostr(ord(b)));
  if b then
    writeln(' a) Wahr')
  else
    writeln(' a) Falsch');
  if b=True then
    writeln(' b) Wahr')
  else
    writeln(' b) Falsch');
  readln(s); // Damit sich das Prrogramm nicht sofort beendet
end.

Ich hoffe, ich habe es einigermaßen verständlich rüberbringen können (Habs manchmal nicht so mit dem Erklären^^)

//Edit: kein roter Kasten... naja schadet ja nicht
//Edit²: @quendolineDD: Uppsi, sorry ._. Ich weiß wirklich nicht, wie das passiert ist^^ Hab's geändert.

[quendolineDD]

Hey du hast falsch zitiert, das habe ich nie gesagt :-\

[Dani]

Hallo, für verkettete Listen eignet sich Mergesort sehr gut. Laufzeit im worst case ist O(n*log(n)), also sehr nahe am theoretischen Minimum. Lineare Laufzeit, also O(n), wird schwer, da dein Wertebereich wahrscheinlich zu groß für Bucketsort ist.

Mergesort ist zwar ein rekursiver Algorithmus, allerdings garantiert er dir eine Rekursionstiefe von log(n). Wenn du also 1267650600228229401496703205376 Werte sortierst, hast du trotzdem nur eine Rekursionstiefe von ~100.

[Noobinator]

Zitat:

Zitat von Dani

Hallo, für verkettete Listen eignet sich Mergesort sehr gut. Laufzeit im worst case ist O(n*log(n)), also sehr nahe am theoretischen Minimum. Lineare Laufzeit, also O(n), wird schwer, da dein Wertebereich wahrscheinlich zu groß für Bucketsort ist.

Mergesort ist zwar ein rekursiver Algorithmus, allerdings garantiert er dir eine Rekursionstiefe von log(n). Wenn du also 1267650600228229401496703205376 Werte sortierst, hast du trotzdem nur eine Rekursionstiefe von ~100.

Ok danke dir erstmal =)
Werde ich mir mal zu Gemüte führen.

OT: endlich back @ Topic^^