Bubblesort mit Funktion (C++)
-
@Swordfish: Der Autor scheint aber nicht die verbesserte Variante (mit der Abfrage, ob das Array sortiert wurde) zu kennen, wenn man den Absatz "Bubble sort works well with data which is already almost sorted" so liest...
-
@Swordfish Wenn ich drüber nachdenke, ist da vermutlich was dran. Ja, man kann auch mit insertion sort anfangen und tatsächlich haben wir das auch so gemacht
Zum zitieren grade bei der Dikussion, was aus "Lehrsicht" Sinn macht, finde ich übrigens http://warp.povusers.org/grrr/bubblesort_eng.html besser
-
@Swordfish
Was ist so schlimm an Bubblesort?Denn nicht alles was man gelehrt bekommt, hat auch später einen praktischen Nutzen. Ein Beispiel ist mir da noch lebhaft in Erinnerung: Implementierung einer Gleitkommadivision in Assembler ohne Nutzung von FPU Befehlen. Das war absolut fobar.
So manches erscheint mir nur Standardlehre oder Lückenfüller. Ohne nähergehenden Sinn.
-
@Swordfish
Wir durften unter anderem den Quicksort in Assembler, auf einer speziellen zweibändigen Turingmaschine oder unter eine obskuren Programmiersprache programmieren, welche nur die nötigsten Befehle kannte.
-
Bubblesort findet man sogar z.T. in realen Anwendungen, wo es auch Sinn macht.
Eben in diesen Nischen wo man passend vorsortierte Daten hat.Gibt auch eine interessante Abwandlung davon (Cocktail Shaker Sort), wo man nicht immer in der selben Richtung durchgeht sondern so Knight-Rider-mässig immer die Richtung vor und zurück wechselt.
IMO ist das ein gutes Übungsbeispiel zum Einstieg. Man muss (und sollte) damit natürlich nicht Schluss machen. Quicksort und Mergesort sollte jeger mal gehört und verstanden haben wenn es um das Thema Sortieralgorithmen geht.
-
@hustbaer sagte in Bubblesort mit Funktion (C++):
Quicksort und Mergesort
kenne ich nicht
@hustbaer sagte in Bubblesort mit Funktion (C++):
Eben in diesen Nischen wo man passend vorsortierte Daten hat.
Ja, schön. Auch bei bestimmter Hardware kann es eine gute Lösung sein (Tape Drives). Aber das setzt voraus daß der betreffende welche genau weiß was er/sie/es tut. Als Lehrbeispiel bleibt es trotzdem mindestens grenzwertig. Zeig' mir mal einen der ein Kartenspiel intuitiv mit Bubblesort sortiert. Viel Glück.
-
@Swordfish Naja, gute Algorithmen sind ja nicht deswegen "gut", weil sie möglichst genau der menschlichen Intuition folgen... eher im Gegenteil sind diese dann schlechter.
-
@EinNutzer0 sagte in Bubblesort mit Funktion (C++):
gute Algorithmen
da sprach ich von Neulingen, da ist Nachvollziehbar und intuitiv > Effizienz.
-
@hustbaer sagte in Bubblesort mit Funktion (C++):
Bubblesort findet man sogar z.T. in realen Anwendungen, wo es auch Sinn macht.
Eben in diesen Nischen wo man passend vorsortierte Daten hat.Hmm aber auch bei Vorsortierung ist insertionSort eigentlich schneller (oder zumindest gleich schnell), oder nicht?
-
@Swordfish sagte in Bubblesort mit Funktion (C++):
@hustbaer sagte in Bubblesort mit Funktion (C++):
Quicksort und Mergesort
kenne ich nicht
Was dich irgendwie schon für weitere Diskussion disqualifiziert.
@hustbaer sagte in Bubblesort mit Funktion (C++):
Eben in diesen Nischen wo man passend vorsortierte Daten hat.
Ja, schön. Auch bei bestimmter Hardware kann es eine gute Lösung sein (Tape Drives). Aber das setzt voraus daß der betreffende welche genau weiß was er/sie/es tut.
Korrekt. Das ist bei den meisten Sachen so.
Als Lehrbeispiel bleibt es trotzdem mindestens grenzwertig.
Weil?
Zeig' mir mal einen der ein Kartenspiel intuitiv mit Bubblesort sortiert. Viel Glück.
Und?
-
@hustbaer Können wir uns darauf einigen daß wir uns nicht einigen können?
-
Los, holt die Knüppel raus und haut euch auf die Rübe... Nur weil eine Anfängerfrage gestellt wurde
-
@Swordfish Für mich heisst das übersetzt meistens so viel wie "ich hab keine Argumente mehr, aber will einfach trotzdem meine Meinung beibehalten".
Ist jetzt aber auch nicht so dass das Thema besonders wichtig wäre. Also... ja, sicher.
-
Bloß weil Swordfish nicht gut argumentieren kann, liegt er ja nicht falsch. Die BubbleSorter sind ja in der Bringeschuld, zu erklären, wieso das ein guter Einstieg ist. Wieso denn nun BubbleSort?
Aber da ich so lieb bin, mache ich es andersherum und biete aktive Argumente für die Alternativen.
- Mein Favorit: "Versucht mal ohne Anleitung etwas zu erfinden, das sortiert!" Das würde einerseits wesentliche Skills für's Programmieren lehren (Vorgänge verstehen, Planen, Umsetzen) und hätte danach noch einen Aha-Effekt, wenn man bessere Algorithmen lehrt und erklärt. Wenn man bei BS erklärt, dass das schlecht ist, erntet das nur ein No shit, Sherlock, warum hast du uns den Mist überhaupt gezeigt? Ich garantiere auch, dass nicht eine einzige Person bei der selbsterfundenen Lösung auf BS kommen wird, außer denen, die das schon aus anderen Büchern haben. Nachteil dieser Variante ist, dass sie interaktiv ist, und daher einen Lehrkörper braucht, der auch die Zeit und Können hat, sich mit den selbstgefunden Varianten auseinanderzusetzen (wobei 95% gewiss in Richtung Insertion oder Selection Sort gehen werden).
- Insertion oder Selection Sort: Alles ist wie bei Bubblesort, aber wenigstens entspricht es Vorgehensweisen, wie ein normaler Mensch sortiert. Da hat man wenigstens Intuition beim Umsetzen und Verstehen. Der Code ist einfacher als ein gleich stark auf Einfachheit getrimmtes Bubblesort.
- Mergesort: Gut genug, um echte Praxisrelevanz zu haben (und nicht nur an den Haaren herbei gezogene Argumente bezüglich des vorsortierten Falls), aber noch verständlich genug, dass man es intuitiv nachvollziehen kann und sogar im echten Leben anwenden kann. Ich habe im echten Leben schon Klausuren der Größenordnung 100 damit effizient sortiert.
Aktive Argumente gegen Bubblesort:
- Es gibt am Ende immer wieder Leute, die versuchen, das in der Praxis benutzen, weil sie die zweite Lektion verpasst haben. Oder nach "Sortieren für Anfänger" gegoogelt haben.
- Es ist wie Sportunterricht, wo der Lehrer erst einmal alle auffordert, rückwärts zu laufen, und hinterher erklärt, warum Vorwärtslaufen schneller ist. Sag bloß!
-
@SeppJ sagte in Bubblesort mit Funktion (C++):
Ich garantiere auch, dass nicht eine einzige Person bei der selbsterfundenen Lösung auf BS kommen wird
Das stimmt schonmal nicht. Meine erster Sortierung war so was wie Bubblesort und das war definitiv selbst ausgedacht (mangels Büchern oder sowas wie Internet).
Und Jahre später im Studium habe ich Bubblesort auch als den mit Abstand besten (im Sinne von verstehen und daran rumexperimtieren) empfunden.@SeppJ sagte in Bubblesort mit Funktion (C++):
Da hat man wenigstens Intuition beim Umsetzen und Verstehen.
Schön, dass du für die Menschheit sprichst; das scheint mir aber doch sehr subjektiv (umgekehrt pro bubblesort natürlich auch).
-
Wollen wir 100 Leute auf der Straße befragen? Oder wenn wir Statistiken sammeln wollen: Mein erster Programmierkurs, mit Variante 1: 100% der Leute (inklusive mir) ohne Vorwissen haben Selection/Insertionsort erfunden, die Bubblesorter waren 100% Leute, die das aus anderen Kursen hatten. Was dann auch gewissermaßen die These bestätigt, dass es die Leute verdirbt: Denn die Aufgabe war, so effizient wie möglich zu sortieren. Sie haben trotzdem Bubblesort genommen. Und das Wettrennen am Ende verloren. Und die Insertion/Selectionsorter waren schneller mit der Programmierung fertig, da einfacher.
-
@SeppJ sagte in Bubblesort mit Funktion (C++):
Wollen wir 100 Leute auf der Straße befragen?
Wozu? Hast du doch schon längst gemacht! Oder wo auch immer du die Daten her hast, das "man" von selber nie auf Bubblesort kommt und das "man" das sowieso nicht intuitiv finden kann.
Leider war ich bei deiner Repräsentativen Umfrage nicht dabei. Hätte sonst das Ergebnis verfälscht
-
Können wir uns vielleicht darauf einigen: Er ist langsam, aber er ist für die Übung, den Einstieg und für theoretische Überlegungen gut?
Wenn ich ein Auto bauen möchte, beginne ich doch auch erstmal mitm BobbyCar, und nicht gleich mitm Porsche.
-
@EinNutzer0
Ich verstehe auch so langsam die Diskussion nicht mehr.Warum macht man wegen dem Bubblesort so ein Fass auf? Was ist denn so schlimm an Bubblesort als das man deren Lehre verbietet? Warum muss denn ein Algorithmus praxisrelevanz haben?
Ich könnte genauso argumentieren dass man die Lehre von verketteten Listen verbietet.
Vor allen Dingen. Es handelt sich doch um Hintergrundwissen. In 99,9% aller Fälle wird man doch std::sort nutzen.
PS: Selbst Algorithmen wie Stoogesort haben eine Existenzberechtigung. Und sei es nur als Übung in der Komplexitätstheorie.
-
@SeppJ
Bubblesort ist einfach, weil es ausser Schleifen, Verlgeichen und Vertauschen nichts weiter benötigt. Das stimmt grundsätzlich auch für Insertionsort und Selectionsort. Nur Insertionsort bzw. Selectionsort "zu Fuss" zu implementieren, also ohne dass man fertige Funktionen für "in der Mitte einfügen" bzw. "in der Mitte entfernen" hat, ist mehr bzw. bestenfalls gleich viel Aufwand wie Bubblesort zu implementieren. Zumindest wenn man mit Arrays arbeitet. Und wenn man den Ball flach halten möchte, dann sollte man besser mit Arrays arbeiten.Daher halt ich Bubblesort immer noch für einen guten Einstieg. Gut im Sinn von: is OK/nicht schlecht/nicht grundsätzlich abzulehnen/kann man ruhig so machen. Ich habe nie behauptet dass es ideal wäre.
Die BubbleSorter sind ja in der Bringeschuld, zu erklären, wieso das ein guter Einstieg ist.
Siehe oben.
Davon abgesehen sind beide gleichermassen in der Bringeschuld, der der behauptet dass es gut ist und der der behauptet dass es schlecht ist.Was dann auch gewissermaßen die These bestätigt, dass es die Leute verdirbt: Denn die Aufgabe war, so effizient wie möglich zu sortieren. Sie haben trotzdem Bubblesort genommen. Und das Wettrennen am Ende verloren. Und die Insertion/Selectionsorter waren schneller mit der Programmierung fertig, da einfacher.
Wenn Bubblesort die Leute verdirbt, dann muss das selbe auch für Selection- und Insertionsort gelten. Denn wer das als "effizienten" Sortieralgorithmus wählt, der wird damit wohl kaum mehr Glück haben als jemand der Bubblesort wählt. Denn effizient sind im allgemeinen Fall alle drei nicht.
