Bubblesort mit Funktion (C++)
-
@Swordfish Warum?
Aus meiner Sicht ein sehr gutes Lehrbeispiel. Also für Komplexität (theoretische Informatik) nicht zum C++ lernen jetzt
-
@Leon0402 Bubble sort misconceptions aka why bubblesort shouldn't be taught
-
@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.
