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

[alzaimar]

Zitat von glkgereon:

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

Hinterher auch nicht.
Du wirst es nicht schaffen, ein Array mit beliebigem Schlüssel mit einem Aufwand von weniger als O(n log n) zu sortieren. Aber ich lass mich gerne überraschen.

[glkgereon]

Zitat von alzaimar:

Zitat von glkgereon:

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

Hinterher auch nicht.
Du wirst es nicht schaffen, ein Array mit beliebigem Schlüssel mit einem Aufwand von weniger als O(n log n) zu sortieren. Aber ich lass mich gerne überraschen.

Die idee ist einfach...ich werde versuchen, jeden beliebigen schlüsseltypen in einen Integer umzuformen...ob das klappt, keine Ahnung^^