Sortierverfahren

[Gast]

Hallo zusammen,

ich probiere gerade verschiedene Sortierverfahren aus, um ein String Array zu sortieren.
Nun meine Frage. Wenn ich kleine Arrays habe (z.B. mit nur zehn Strings), bin ich da in der Annahme richtig, das dabei shellSort das schnellste mit dem wenigsten Aufwand an vertauschen ist?
Falls sich jemand damit beschäftigt hat, wäre dankbar für eine Antwort. Es geht dabei ums Prinzip, da es bei zehn Einträgen ja egal wäre was ich benutze.
Danke

 

[Leroy42]

Wenn ich kleine Arrays habe (z.B. mit nur zehn Strings), bin ich da in der Annahme richtig, das dabei shellSort das schnellste mit dem wenigsten Aufwand an vertauschen ist?

Bei Arrays mit nur 10 Elementen, ist die Frage sowas von
rein akademisch, das ich besseres zu tun habe, als ihr nachzugehen. :bae:

 

[materthron]

Im Paket java.util existiert ein Klasse Arrays, die dir das Implementieren eines eigenen Sortieralgorithmus erspart.

mfg materthron

 

[SnooP]

Versteh ich nicht die Frage... - shellSort ist nicht der schnellste sortier-algorithmus - vermutlich ist shellSort gegenüber Quicksort bei sehr kleinen Listen effektiver, da der ja gegen O(n^2) geht - während shellSort bei etwa O(n^1.25) laut Wikipedia rumlümmelt... aber da die absolute Geschwindigkeit bei einer so kleinen Liste unheimlich gering sein dürfte, bringt der Wechsel zu einem etwas effektiverem Algorithmus nicht wirklich was! Es sei denn, du hast zich Millionen kleine Listen die zu sortieren sind.

Falls es sich um fixe Arrays handelt, würde ich sogar Merge-Sort vorschlagen, der ist immerhin O(n)

 

[Wildcard]

Es gibt keinen Sortieralgo mit O(n).
Mergesort ist O(n*log(n))

 

[SnooP]

sorry meinte ich auch... wollte nochmal nachgucken, hatte aber schon geclickt - ich meinte das Merge-Sort immerhin immer die gleiche Komplexität hat, also auch nicht O(n^2) werden kann, so wie der ursprüngliche Quicksort... - allerdings ist die Variante die in Java programmiert ist, glaub ich sogar etwas fixer? ... dazu steht was in der API, man möge nachschauen, wenn's beliebt

 

[Gast]

Bei Arrays mit nur 10 Elementen, ist die Frage sowas von
rein akademisch, das ich besseres zu tun habe, als ihr nachzugehen.

Ist richtig, es handelt sich auch nur um eine Auswertung der Algorithmen. Hab ja nicht verlangt, das jemand extra nachschaut, sondern gefragt ob sich zufällig jemand schon mal damit beschäftigt hat.

Versteh ich nicht die Frage... - shellSort ist nicht der schnellste sortier-algorithmus vermutlich ist shellSort gegenüber Quicksort bei sehr kleinen Listen effektiver

Habe auch effektiver gemeint.
Aber noch ne kleine Frage:
effektiv heißt doch weniger Vertauschungen.
Dies hat doch logischerweise auch Auswirkungen auf die Schnelligkeit, ist dem dann nicht so, dass er auch schneller ist?

 

[Gelöschtes Mitglied 5909]

www.sortieralgorithmen.de

 

[SnooP]

Dies hat doch logischerweise auch Auswirkungen auf die Schnelligkeit, ist dem dann nicht so, dass er auch schneller ist?

Ja sicher... allerdings beim Sortieren von 10er Listen bist du in kaum messbaren Bereichen - egal welche Komplexität du da hast...

 

[Gast]

Ja sicher... allerdings beim Sortieren von 10er Listen bist du in kaum messbaren Bereichen - egal welche Komplexität du da hast...

Ok

Vielen Dank nochmals.

Gruß Gast

 

[Leroy42]

Aber noch ne kleine Frage:
effektiv heißt doch weniger Vertauschungen.

Da fällt mir doch glatt wieder ein, was einmal mein Prof zu einem
Algorithmus von mir gesagt hat:

Ihr Algorithmus ist wirklich sehr effizient.
Leider nur nicht effektiv.

:shock:

Effektiv <==> Effizient