Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)?

[glkgereon]

Zitat von alzaimar:

Zitat von glkgereon:

mein Algo kann Ganze Zahlen in linearer Zeit sortieren.

Klappt nicht.

Delphi-Quellcode:

Type
  TIntegerArray = Array Of Integer;

Var
  A : TIntegerArray;

Begin
  SetLength (A,2);
  A[0] := 0; A[1] :=maxint;
  Sort (A); // <- peng
End;

Zitat von glkgereon:

Mit anderen Typen als ganzen Zahlen... Theoretisch ist es möglich.

Praktisch wohl kaum.

Du machst, wie ich bereits sagte, starke Einschränkungen bezüglich des Schlüssels. Die Schlüssel sind abhängig vom vorhandenen Speicher, was nun wirklich nicht praktikabel ist. Die Laufzeit ist abhängig von der Verteilung der Schlüssel sowie von den Schlüsseln selbst.

Wenn Du schon (annähernd) linear sortieren willst, dann wenigstens mit einem praktikablen Verfahren, als dem hier. Z.B. Bucketsort. Das geht aber auch nur mit Schlüsseln, die einigermaßen gleichmäßig verteilt sind.

Im Übrigen ist Quicksort bei Arrays bis 2,5Mio Elementen immer noch wesentlich schneller.

wie ich bereits sagte^^

aber es geht ja ums prinzip

BTW behaupte ich, das man die Einschränkungen bezügklich des Schlüssels aufheben kann...aber nicht vor Sylvester^^