Java Array Copy

[1668mib]

Naja aber ist die Zahl der Vertauschungen zwangsläufig denn der ausschlaggebende Punkt für die Laufzeit? Das hängt vom Algorithmus ab...

Wenn ich dir einen Alogirthmus schreiben würde, welcher erst mal schaut, mit welchem anderen Wert er den aktuellen am besten vertauscht komme ich vielleicht auf wenig Vertauschungen, aber das Finden der richtigen Position wird verdammt lange dauern in der Summe...

im Grunde solltest du also die Zahl von Schleifendurchläufen irgendeiner Art zählen...

Oder einfach die Laufzeit messen :-)

 

[ice-breaker]

Ich sollte ja irgendwie ein Gefühl für diese Algorithmen bekommen..
Das Ziel ist ja nicht dass ich jeweils den Worst-Case auswendig lerne, sondern dass ich verstehen kann weshalb ein Algorithmus n^2 ist, oder wieso auch nicht..
Klar beim BubbleSort ist das ja auch noch einfach zu sehen (2 Schleifen inneinander = n^2), aber es gibt ja auch schwierigere.. Ich muss dass ja auch für solche können die ich nicht gelernt habe..

neija aber tut mir leid, du wirst durch Testen nicht rausfinden können, warum ein Quicksort im Worst-Case O(n^2) ist, denn dafür wird ein ganz bestimmter Worst-Case benötigt.

im Grunde solltest du also die Zahl von Schleifendurchläufen irgendeiner Art zählen...

es gibt Algorithmen, bei denen Schleifendurchläufe nicht alleine zur Laufzeit beitragen.
z.B. Bucket-Sort

Oder einfach die Laufzeit messen :-)

Microbenchmarks eignen sich nicht um Sortieralgorithmen zu bewerten.



Eigentlich werden, wenn in einem Programm bekannt ist, dass Sortieren ein wichtiger Zeitfaktor ist, Sortieralgorithmen nach ihrer Laufzeit und nach ihrem Speicherplatzverhalten ausgewählt, denn je nach Bedingung eignet sich jedesmal ein anderer Sortieralgorithmus am besten.

 

[1668mib]

Und auch vor allem danach was man sortieren will...
Da spielen auch Faktoren eine Rolle, ob man davon ausgehen kann, ob die Liste schon überwiegend vorsortiert ist oder nicht...

Und Bucketsort ist für sich alleine auch kein Sortieralgorithmus...

 

[Boeby]

Okay, ihr habt ja recht.. Trotzdem wollte ich die mal "selber" programmieren um sie zu verstehen und evtl. was in Bezug auf die Performance/Laufzeit zu erfahren.. Aber wie ich bereits geschrieben bin ich bei der Rekursion stehen geblieben..
(Ich bin mit diesem Thema noch nicht durch, muss es mir also nochmals anschauen..)

Die verschiedenen Fälle von sortierer Liste, bzw. nicht sortierer Liste wollte ich mit meinen 3 Arrays austesten.
(Im 1. Post sieht man 3 Arrays, wovon 2 auskommentiert sind..)
Einer davon ist der idealfall, bei dem schon alles sortiert ist. Dann gibts noch den "zufälligen" der relativ durcheinander ist. Und dann gibts noch einen der absteigend sortiert ist. Damit wollte ich testen und Erkenntnisse gewinnen..

 

[1668mib]

Kannst ja mal auch eine "leicht"-sortierte Liste nehmen... alles stimmt bis auf ein Wert (z.B. am Ende)

also
1, 6, 8, 11, 23, 52, 92, 7

das wäre quasi wenn du in eine bestehende Liste nen neuen Eintrag (oder einige neue Einträge) dazu machst...