Sortieralgorithmus

[Streeber]

Hallo.

Ich suche den Algorithmus, der am Besten geeignet ist für Folgendes:
Ich habe eine ArrayList<MyData>
MyData ist eine Klasse, die einen String und 2 Integer enthält.

Es gibt ca. 50.000 Einträge. Die MyData-Einträge sollen nun nach dem String sortiert werden.
Mit welchem Algorithmus sind diese wohl am Besten zu sortieren?

Ich habe schon Shellsort ausprobiert und das dauert eewig (ich habe es noch kein Mal bis zum Ende durchlaufen lassen...).

Hat jemand hier Erfahrung mit sowas?

Wäre Merge- oder Quicksort besser geeignet?


Desweiteren könnte ich die Sache auch ganz anders angehen.
Die ArrayList wird kurz vorher generiert. Ich könnte auch sofort beim Einfügen die ArrayList sortieren. Somit müsste ich nur checken an welchen Indexplatz das neue Element soll.
Gibt es eine einfache Funktion, die dann alle anderen Elemente nach hinten verschiebt?

Danke für Hinweise und Ansätze.

 

[0x7F800000]

Ich habe schon Shellsort ausprobiert und das dauert eewig (ich habe es noch kein Mal bis zum Ende durchlaufen lassen...).

wo hast du denn den Algo her?

Wäre Merge- oder Quicksort besser geeignet?

definitiv. O(n log(n)) ist auf jeden fall in O(n^(1+eps)).

Die ArrayList wird kurz vorher generiert. Ich könnte auch sofort beim Einfügen die ArrayList sortieren. Somit müsste ich nur checken an welchen Indexplatz das neue Element soll.
Gibt es eine einfache Funktion, die dann alle anderen Elemente nach hinten verschiebt?

was ist das? insertsort? O(n^2)? In der plauderecke gibt's grad zufälligerweise einen Algo der in O(n!) läuft, damit lässt sich auch ganz gut bis zum BigRip warten

Faule & einigermaßen gute Lösung: den normalen merge-sort aus der API nehmen.
Falls es nicht reicht: RadixSort. Läuft in O(n) [vorausgesetzt deine Strings beinhalten nicht allzu abartig viele verschiedene buchstaben, sondern zB. nur ASCII o.ä.] Der ist lustig, den würd ich grad sogar recht gerne implementieren^^

 

[Streeber]

wo hast du denn den Algo her?

Shell sort - Algorithm wiki

definitiv. O(n log(n)) ist auf jeden fall in O(n^(1+eps)).

Sorry, wenn ich frage, aber was bedeutet das O eigentlich?

was ist das? insertsort? O(n^2)?

^^ Hast Recht. Wald vor lauter Bäumen nicht mehr gesehen...

In der plauderecke gibt's grad zufälligerweise einen Algo der in O(n!) läuft, damit lässt sich auch ganz gut bis zum BigRip warten

Hö?

Faule & einigermaßen gute Lösung: den normalen merge-sort aus der API nehmen.

Konnte in der API nichts finden. Wie greife ich auf diese sort-Methode zu?

 

[Der Müde Joe]

>Konnte in der API nichts finden.

Collections.sort(List)

 

[0x7F800000]

Oder auch
Collections (Java Platform SE 6)
wenn deine Klasse Comparable nicht implementiert. Da musst du nur noch einen comparator übergeben, er von deiner klasse den string rausgreift, und dann nur die strings miteinander vergleicht.

O
BigRip
ooh man, so verläuft doch der ganze sarkasmus voll im Sand^^ Insertion Sort ist sau lahm, mehr wollte ich nicht sagen^^

 

[Leroy42]

O
BigRip
ooh man, so verläuft doch der ganze sarkasmus voll im Sand^^ Insertion Sort ist sau lahm, mehr wollte ich nicht sagen^^

Bei mir ist er angekommen!

(Danke für den Hinweis auf The Big Rip. Interessant!)

Aber eine ArrayList würde ich zum Sortieren nicht nehmen.

Wäre da nicht
1. eine Überführung in ein Array
2. Sortierung des Arrays
3. Rücküberführung in eine ArrayList

wesentlich schneller? ???:L

 

[maki]

Bei mir ist er angekommen!

(Danke für den Hinweis auf The Big Rip. Interessant!)

Aber eine ArrayList würde ich zum Sortieren nicht nehmen.

Wäre da nicht
1. eine Überführung in ein Array
2. Sortierung des Arrays
3. Rücküberführung in eine ArrayList

wesentlich schneller? ???:L

Ja, und die API macht genau das, Collections.sort ruft Arrays.sort auf

 

[0x7F800000]

Solche feinheiten müsste die API selbst erledigen, dazu ist sie ja da... Außerdem macht das hinundherkopieren keinen sinn, da im ArrayList sowieso intern schon ein Array gespeichert ist. Und überhaupt: wenn es wegen dem overhead der methodenaufrufe um Faktor 2 langsamer läuft, ist das im vergleich zum falschen sortieralgorithmus vernachlässigbar:

50 000 / ln(50 000) = 4 621.16678 > 2

 

[Leroy42]

Ja, und die API macht genau das, Collections.sort ruft Arrays.sort auf

Ahh? Interessant.