Welchen Algorithmus verwende ich, um 50 Zahlen mit möglichst wenig Vergleichen und Vertauschungen zu sortieren?
Die Aufgabe ist, einen beliebigen Sortieralgorithmus aus berliebiger Quelle in Java zu implementieren, um bis zu 50 Zahlen zu vergleichen. Gewertet wird nur die möglichst geringe Anzahl an Vergleichen und Vertauschungen. Der Rest ist egal. Keine Zahl kommt Zweimal vor. Welcher Algorithmus eignet sich da am besten?
4 Antworten
Die anderen Antworten sind offensichtlich von Laien verfasst, und ich - als richtiger Profi - habe dir hier mal zwei sehr effiziente Sortieralgorithmen in Java implementiert:
http://pastebin.com/PCZ5R3BqrandSort() würfelt die Elemente eines Arrays so lange durcheinander, bis sie sich zufällig in einer sortierten Reihenfolge befinden. Wenn man ganz ganz viel Glück hat, wird nur eine Iteration benötigt, und der Algorithmus ist demnach als "effizient" zu bezeichnen.
assumeSort() ist sogar noch schneller, da einfach angenommen wird, dass das Array von vornherein schon sortiert vorliegt, und andernfalls einfach eine Ausnahme geworfen wird. Dieser Algorithmus ist sehr sehr schnell, hat aber auch eine sehr hohe Fehleranfälligkeit.
Habe den obigen Code zwar nur mit 10 Arrayelementen getestet, aber er sollte natürlich auch mit deinen geforderten 50 Elementen funktionieren ... vorausgesetzt, du achtest nicht so genau auf die Rechenzeit. :)
Einfach den Code in "Main.java" speichern, und mit:
javac Main.java
... kompilieren, und danach testweise mit:
java Main one two three four five six seven eight nine ten
... ausführen!
Tja, dagegen kommen Bubblesort & Co nicht an.
Viel Spaß noch mit Java! :)
PS: Ich sehe gerade, dass es dir wohl nur um Zahlen und nicht um Strings geht ... aber das Prinzip ist ja im Grunde genommen das Gleiche. :)
Na doch, es wurde nicht nach einer effizienten Laufzeit, sondern nach effizienz bezüglich der Vergleiche gefragt. Eine obere Schranke für den Worst Case gibt es halt nicht, theoretisch könnte der bis in alle Ewigkeit zufällig das Array "sortieren"
Und ich hielt mich immer für den einzigen, der auf die Idee mit dem zufälligen sortieren kam ^^.
Du weist aber schon, dass man da best und worst Case unterscheiden muss ? Im best Case hat man keine Vertauschung , aber einen Aufruf von .isSorted(). Das die Antwort jetzt nivht all zu ernst zu nehmen ist, ist klar; an sich hat er aber fachlich recht
Ja. Im best-case hat man keine Vertauschung. Aber im average-case und worst-case ist die Laufzeit bzw. Anzahl der Vertauschungen schrecklich :) Bei anderen Algorithmen hat man im best-case die gleiche Laufzeit bzw. Anzahl von Vertauschungen (0) (wenn man vorher auch so eine "isSorted"-Methode aufruft). Aber im average- und worst-case hat man dann eine deutlich bessere Laufzeit bzw. weniger Vertauschungen. Das einzige was an diesem Algorithmus gut ist, ist das man das Verfahren gut nachvollziehen kann. Gruß :)
Wie gesagt, die Antwort trollt auf recht subtile weise .... Aber das hat man als Fragen Steller davon, wenn man ungenau formuliert
Es gibt keinen Algorithmus, der für alle Fälle optimal ist. Ich habe z.B. eine Tabelle, die ich sortiert benötige. Die Daten bekomme ich bereits sortiert aus der Datenbank. Nur: Die Datenbank sortiert die Umlaute anders, so wie der Anwender es normalerweise braucht, meine Tabelle muss aber binär korrekt sortiert sein. Die Wahrscheinlichkeit, dass es überhaupt Differenzen gibt, ist eher gering.
Nun kann ich einen Super-Sort in mein Programm einbinden, der völlig unterfordert ist, aber diesen Fall kann der viel geschmähte Bubble-Sort mit viel weniger Aufwand genauso gut erledigen. Insofern ist der Gedanke von TeeTier gar nicht so abwegig (ist halt ein Profi), dass die zu sortierende Tabelle schon sortiert sein kann und ganz einfache Algorithmen voll ausreichend sind.
Auch das dynamische Einfügen in eine bereits sortierte Tabelle (kommt häufig vor) ist so ein Fall. Man hängt das neue Element hinten dran und lässt z.B. einen Sort drüber laufen. Dazu braucht man auch keinen Super-Sort, es sei denn, diesen habe ich aus anderen Gründen schon im Programm.
Man muss auch berücksichtigen, dass manche sonst gut bewertete Sort-Algorithmen eine Art von Analyse durchführen, bevor sie mit dem eigentlichen Sortieren beginnen. Diese Rüstzeit ist bei kleinen Datenmengen nicht gerade von Vorteil.
Auf jeden Kochtopf passt ein Deckel, aber es gibt keinen Deckel, der auf jeden Kochtopf passt.
Google mal nach "bubblesort" dabei handelt es sich um einen Sortieralgorithmus der die Werte anhand ihrer Größe tauscht.
Bubblesort gehört zu den schlechteste Sortieralgorithmen überhaupt :D
Ist aber recht simpel zu verstehen.
Außerdem maximal eine Laufzeit von O n^2. Ist also garnicht so langsam.
Sag mal, du hast dich nicht all zu sehr damit befasst, oder ? Bubblesort ist grauenhaft. Schau dir mal die Laufzeit von Quicksort oder Mergesort an : Im best Case n*log n ... Wer mit simpler Mathematik vertraut ist, sollte den Unterschied bemerken.
Trotzdem ist Bubblesort nicht langsam. Viele Algorithmen haben dieselbe Laufzeit.
O(n^2) ist grausam. Bubblesort wird häufig nicht mal als Sortieralgorithmus genannt.
Ist der Zahlenbereich offen?
Keine Hobbys? Dieses getrolle ist weder lustig, noch hilft es einem weiter. Effizient ist es jedenfalls nicht.