Doppelt verkettete Liste sortieren

[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^^