Sinn von Bubble Sort?`
-
Wozu gibts überhaupt Bubble Sort? Quasi jeder andere Algo ist schneller.
-
guuuuuuuu schrieb:
Wozu gibts überhaupt Bubble Sort? Quasi jeder andere Algo ist schneller.
Ist zum Üben ganz gut erstmal. Einfacher Algo. Auch zum Üben, um mit Arrays bzw Iteratoren umzugehen. Also mir hat das beim Einstieg voll geholfen.
In der Praxis kann er sogar auch was taugen, wenn ganz viele quasi persistente Daten bei Programmstart geladen werden und bei Ende gespeichert und bei Programmlauf nur ganz wenige Datensätze ihren Schlüssel ändern oder auch einige ihren nur ganz wenig ändern. Die werden dann vom bubblesort eben auch in ganz wenigen Durchläufen richtig positioniert. Quicksort rechnet sich daran einen Wolf im Vergleich dazu. Naja, trotzdem ist dann insertionsort meist (evtl immer?) ein klitzewenig schneller.
Deswegen übrigens darf kein C++-Compiler ein handgeschriebenes Bubblesort als "Ach, der sortiert hier" erkennen und durch einen Aufruf von std::sort ersetzen. Es könnte sein, daß der Programmierer mit purer Absicht den "langsamen" Algo gewählt hat, weil er in seiner Datenlage eben doch schneller ist als jeder Standard-Algo. Nicht supi anfängerfreundlich, aber wenn man nicht mehr so der Anfänger ist genau klasse.
-
volkard schrieb:
Deswegen übrigens darf kein C++-Compiler ein handgeschriebenes Bubblesort als "Ach, der sortiert hier" erkennen und durch einen Aufruf von std::sort ersetzen.
Wie kommst du denn darauf? Mal abgesehen davon, dass die Prämisse ziemlich schwachsinnig ist, dürfte er das ggf. selbstverständlich.
-
Bashar schrieb:
dürfte er das ggf. selbstverständlich.
Jep, er könnte auch gleich Bogosort nehmen, alles standardkonform.
-
Bashar schrieb:
volkard schrieb:
Deswegen übrigens darf kein C++-Compiler ein handgeschriebenes Bubblesort als "Ach, der sortiert hier" erkennen und durch einen Aufruf von std::sort ersetzen.
Wie kommst du denn darauf? Mal abgesehen davon, dass die Prämisse ziemlich schwachsinnig ist, dürfte er das ggf. selbstverständlich.
Richtig, er *darf*. Neben dem reinen Standard gabs's dann Verabredungen, die vor 20 Jahren noch deutlich ausgesprochen wurden, ich erinnere mich. Damals war alles besser.
-
Bashar schrieb:
volkard schrieb:
Deswegen übrigens darf kein C++-Compiler ein handgeschriebenes Bubblesort als "Ach, der sortiert hier" erkennen und durch einen Aufruf von std::sort ersetzen.
Wie kommst du denn darauf? Mal abgesehen davon, dass die Prämisse ziemlich schwachsinnig ist, dürfte er das ggf. selbstverständlich.
Ernsthaft? Ich meine, ich sehe volkards Argument, dass der selbst implementierte Sortieralgorithmus bestimmte Eigenschaften haben könnte, die wichtig sind und die std::sort nicht bietet. std::sort gewährleistet ja nichtmal, dass ein stabile Sortierverfahren genutzt wird.
-
volkard schrieb:
Neben dem reinen Standard gabs's dann Verabredungen, die vor 20 Jahren noch deutlich ausgesprochen wurden, ich erinnere mich. Damals war alles besser.
Glaub ich nicht. Das Leben ist zu kurz für solche Verabredungen.
gregor schrieb:
Ernsthaft? Ich meine, ich sehe volkards Argument, dass der selbst implementierte Sortieralgorithmus bestimmte Eigenschaften haben könnte, die wichtig sind und die std::sort nicht bietet. std::sort gewährleistet ja nichtmal, dass ein stabile Sortierverfahren genutzt wird.
OK, die Stabilität ist ein Problem, aber Volkard ging es nur um die Performance. Ersetzte sort meinetwegen durch stable_sort.
-
guuuuuuuu schrieb:
Wozu gibts überhaupt Bubble Sort? Quasi jeder andere Algo ist schneller.
kann man so nicht sagen - Bogosort ist noch einen Tuck langsamer.
-
Wozu gibts überhaupt Bubble Sort? Quasi jeder andere Algo ist schneller.
Wozu gibt es die Zahl 0? Quasi jede natuerliche Zahl ist groesser.
-
Bashar schrieb:
volkard schrieb:
Deswegen übrigens darf kein C++-Compiler ein handgeschriebenes Bubblesort als "Ach, der sortiert hier" erkennen und durch einen Aufruf von std::sort ersetzen.
Wie kommst du denn darauf? Mal abgesehen davon, dass die Prämisse ziemlich schwachsinnig ist, dürfte er das ggf. selbstverständlich.
Sobald irgendwelche auf T aufgeführten Operationen des handgeschriebenen Bubblesort irgendwelche beobachtbaren Effekte haben darf er das garantiert nicht mehr.
-
Bashar schrieb:
OK, die Stabilität ist ein Problem
Nein, ist sie nicht. Jedenfalls nicht zwangsläufig, aber in dem Fall ist wieder mehr interessant als nur die Stabilität. (z.B. wenn Kopierkonstruktoren volatile Zugriffe machen.)
-
cooky451 schrieb:
Bashar schrieb:
OK, die Stabilität ist ein Problem
Nein, ist sie nicht.
Wieso nicht?
Jedenfalls nicht zwangsläufig, aber in dem Fall ist wieder mehr interessant als nur die Stabilität. (z.B. wenn Kopierkonstruktoren volatile Zugriffe machen.)
Jaja, schon klar.
hustbaer schrieb:
Sobald irgendwelche auf T aufgeführten Operationen des handgeschriebenen Bubblesort irgendwelche beobachtbaren Effekte haben darf er das garantiert nicht mehr.
Jaja, schon klar.
Nochmal zusammengefasst: Volkard hat aus meiner Sicht behauptet, der Compiler dürfe einen Algorithmus nicht durch eine semantisch äquivalente Bibliotheksfunktion ersetzen, wenn sich dadurch die vom Programmierer indentierte, möglicherweise für einen Spezialfall vorgesehene, Laufzeitkomplexität verschlechtert. Mein Argument: Darf er, Laufzeit gehört nicht zur Semantik.
Lediglich das Beispiel mit std::sort ist schlecht, weil es hier nicht sematisch äquivalent ist und daher die Ersetzung aus trivialen Gründen nicht erlaubt ist.
-
Vermutlich hast du Recht.
Wobei das dann ein Oversight im Standard ist.
Denn es führt alle Komplexitätsangaben im Standard ad absurdum.
Man könnte die dann gleich alle rauslöschen oder mit O(so lang wie es halt dauert) ersetzen
-
Die Komplexitätsangaben bei Containern sind auf die Operationen auf den enthaltenen Objekten bezogen, nicht auf die Zeit. (Wobei ich nicht weiß, ob das nicht ein Lippenbekenntnis ist.)
-
Ah, OK.
Sobald die Operationen auf T aber nicht beobachtbar sind, hat man ja wieder das gleiche Problem.
-
Bei Template-Sachen kann man eben nur die Komplexität bezüglich der Operatoren ausdrücken, weil die Operatoren vom User kommen und nicht bekannt sind.
Hab mal ein wenig in den Draft geschaut
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3337.pdf18.9.2.4:
Complexity: constant time.23.3.4.6.25:
Complexity: linar time.23.3.5.5.6:
Complexity: Constant time.24.2.1.8:
All the categories of iterators require only those functions that are realizable for a given category in constant time (amortized).Also darf der Compiler wohl die paar std::sachen, die eine Zeitkomplexität garantieren, nicht deoptimieren, das andere (insbesondere allen Usercode) aber doch. Wie gemein.
