Schneller Sortieralgorithmus gesucht!!!!

[BabyT24]

Hallo,

ich brauche für ein Programm einen Sortieralghorithmus, der SEHR SCHNELL arbeiten kann, da teilweise bis zu 50.000 Objekte und mehr sortiert werden müssen.

Wer kann mir da weiterhelfen?

Der Algorithmus kann auch ruhig etwas schwerer sein... :bimei

[akull82]

he,

eine frage zu deinen objkten, was unterscheidet sie von einander, also wonach soll sotiert werden ? im allg. würde ich sagen implementiere comparable und versuch Arrays.sort zu nutzen.

[BabyT24]

Sortiert wird nach einer enthaltenen Summe (long).

Den Sortieralgo kann ich nicht nutzen, weil die Objekte nicht in einem Array sondern in einem eigenständig programmierten Container enthalten sind...

Quicksort hatte ich schon probiert, allerdings braucht selbst dieser bei 25.000 Objekten schon zu lange...

[akull82]

50.000 objekte sind eine ganz menge, vielleicht sowas wie

Object[] objects = new Object[50000];

try {

int index:

for( int i=0; ; i++) {

index = getObj().getLong();

while( objects[ index ] != null )

index++;

objects[index] = getObj();

}

} catch( ArrayIndexOutOfBounds e ) {

}

wobei getObj dein einzu sotierendes object zurück gibt

[kingofbrain]

Servus,

von der Algorithmikseite ist der Quicksort schon ein sehr schneller Algorithmus, da er mit der Komplexität O(nlogn) arbeitet und somit bei steigendem n die Laufzeit nur mit logn ansteigt.

Meine Vermutung ist, das es nicht am Sortieralgorithmus liegt, aber dazu bräuchte man erstens ein wenig Code und zweitens eine genauere Definition von "zu lange".

Schnellere Sortieralgorithmen als z.B. Quicksort mit nlogn sind mir nicht bekannt bzw. gelten nur für den speziellen Einsatz bei einem bestimmten Problem.

Peter

[BabyT24]

Zu lang bedeutet, dass ich den Prozess abbrechen musste, weil er nach 15 min immer noch nicht am Ende des Sortierens angekommen war.

Den Code kann ich leider nicht rausgeben, da ich bei einer großen Firma arbeite, die darauf bestimmt gar nicht gut zu sprechen sind...

[Crush]

Je nach Datentyp der Objekte kann eine Vorsortierung den Quicksort extrem beschleunigen. Nach was für einem Objektinhalt wird denn sortiert? Einem Namen (ASCII), Multibyte/wide-characters, Zahlen (int, float) oder was? Vorher kann man eine von mir optimierte Version vom Radix-Sort drüber laufen lassen. In meinem Beispiel war das Sortierkriterium die ersten 2 Bytes. Ich bin zwar nicht so der Java-Meister, aber bestimmt kann man das dort auch irgendwie einigermaßen zügig implementieren.

[kingofbrain]

Sorry, ohne Code kann man Dir dabei nicht helfen.

Wenn Deine Problemstellung ca so aussieht, dann liegt es mit Sicherheit nicht am Quicksort:

Ein Objekt mit einem long-Wert als Klassenvariable. Dieses Objekt implementiert Comparable

Der Quicksort wurde korrekt implementiert und bekommt die Listenstruktur mit den Objekten und vergleicht mittels compareTo.

Peter

[BabyT24]

Danke euch, für eure Vorschläge, habe mir gestern Gott sei Dank noch Professionelle Hilfe holen können. Derjenige hat mir dann das Gleiche geraten wie kingofbrain.