Bubblesort geht nicht

Kellerautomat

Buuuuh! Bubblesort ist Mist.

volkard

Kellerautomat schrieb:

Buuuuh! Bubblesort ist Mist.

Nicht immer.
https://www.youtube.com/watch?v=-1R40EVoyWo

juhu123

Vielen herzlichen Dank.
Man bin ich blöd.
Es läuft.

juhu123 schrieb:

Was mach ich verkert??????
beim sortiren

verkert => verkehrt
sortiren => sortieren

juhu123 schrieb:

Nur die Lotto zahlen er geben keinen Sinn.

Lotto zahlen => Lottozahlen

Weitere Fehler finde ich jetzt so spontan nicht. Aber ich hoffe, damit ist Dir schon mal geholfen .

Marthog

Kellerautomat schrieb:

Buuuuh! Bubblesort ist Mist.

Aber einfach zu lernen und deswegen fuer Lehrzwecke ganz sinnvoll.

Kellerautomat

Marthog schrieb:

Kellerautomat schrieb:

Buuuuh! Bubblesort ist Mist.

Aber einfach zu lernen und deswegen fuer Lehrzwecke ganz sinnvoll.

Und dann verwendet er noch womoeglich Bubblesort in production code. Ne danke.

volkard

Kellerautomat schrieb:

Und dann verwendet er noch womoeglich Bubblesort in production code. Ne danke.

Hab ich schon gemacht.
Außerdem hat mir Bubblesort auch beim Lernen sehr geholfen.

Marthog

Kellerautomat schrieb:

Und dann verwendet er noch womoeglich Bubblesort in production code. Ne danke.

Und?
Ausserdem hat Bubblesort viele nuetzliche Eigenschaften. Es ist der einfachste Algorithmus, der stabil ist, fuer verkettete Listen geeignet ist und aus dem man ein Sortiernetz bauen kann.

volkard

Marthog schrieb:

Kellerautomat schrieb:

Und dann verwendet er noch womoeglich Bubblesort in production code. Ne danke.

Und?
Ausserdem hat Bubblesort viele nuetzliche Eigenschaften. Es ist der einfachste Algorithmus,

Kann man abstreiten und behaupten, insetion sort sei einfacher. Oder natürlich bogosort, der ist echt einfacher.

Marthog schrieb:

der stabil ist,

Sind wohl die meisten in der Laufzeitnähe von bubblesort.

Marthog schrieb:

fuer verkettete Listen geeignet

Gerade quicksort und mergesort eignen sich hervorragend für verkettete Listen. Quicksort gestaltet sich einfach zu
-Erstes Element ausketten und zum Pivot machen.
-Zwei leere Listen anlegen.
-Alle Elemente anschauen und in die linke oder rechte Liste umketten.
-Die beiden rekursiven Aufrufe.
-LinkeListe-Pivot-RechteListe zusammenketten, fertig.
Mergesort ähnlich schlicht und Mergesort geht endlich zwanglos in-place.

Marthog schrieb:

ist und aus dem man ein Sortiernetz bauen kann.

Ähm, dafür würde ich ihn jetzt nicht gleich nehmen.

Ich nahm ihn, weil die Liste beim Laden schon sortiert war und bis zum Speichern meistens keine und selten mal bis zu vielleicht 10 Datensätze verändert wurden.

Jockelx

Ich mag Bubblesort!
Wenn man Kenntnise über die zu sortierenden Daten hat, ist der (ausm Bauch heraus) auch glaube ich nicht schlecht.
Z.B. viele vorsortierte Daten in den ersten 99% und das letzte 1% mit neuen, unsortierten Daten oder sowas.
Oder generell vorsortiert und dann von beiden Seiten bubbeln und so.
Habs aber noch nie gebraucht.

SeppJ

Warum wird hier auf einmal ernsthaft Bubblesort schön geredet? Als bei mir in der Schule in Informatik Sortieralgorithmen dran kamen, hat der Lehrer uns erst einmal Vorschläge machen lassen. Von den Leuten, die nicht wussten, worauf er hinaus wollte, kamen Vorschläge, die im Prinzip auf Sachen wie Insertion Sort und ähnliches hinaus liefen. Das war dem Lehrer aber verwunderlicherweise zu gut. Nur derjenige mit den Informatikvorkenntnissen wusste, dass er Bubblesort hören wollte, weil da die Laufzeit besonders leicht zu berechnen war. Bubblesort ist also so schlecht, dass ein normaler Mensch nicht einmal auf die Idee käme, sofern man nicht mit Absicht ein abschreckendes Beispiel konstruieren möchte.

Jockelx schrieb:

Z.B. viele vorsortierte Daten in den ersten 99% und das letzte 1% mit neuen, unsortierten Daten oder sowas.

So etwas wie 2 3 4 5 6 ... 97 98 99 1?

volkard

SeppJ schrieb:

Warum wird hier auf einmal ernsthaft Bubblesort schön geredet? Als bei mir in der Schule in Informatik Sortieralgorithmen dran kamen, hat der Lehrer uns erst einmal Vorschläge machen lassen. Von den Leuten, die nicht wussten, worauf er hinaus wollte, kamen Vorschläge, die im Prinzip auf Sachen wie Insertion Sort und ähnliches hinaus liefen. Das war dem Lehrer aber verwunderlicherweise zu gut.

Ja, verwunderlich. Er hätte beim ersten Verfahren bleiben können und sollen. Ob Insertionsort, Selectionsort, Bubblesort ist ja egal. Denke nicht, daß Laien auf Anhieb unter O(n^2) kommen. Egal welches Verfahren die Schüler finden, darauf kann er aufbauen, wenn er überhaupt weiß, was er tut, und nicht nur aus einem Buch abliest.

SeppJ schrieb:

Nur derjenige mit den Informatikvorkenntnissen wusste, dass er Bubblesort hören wollte,

Ja, er dachte schon mit Arrays und Schleifen und so ein wenig.

SeppJ schrieb:

weil da die Laufzeit besonders leicht zu berechnen war.

Tut mir leid, das vermute ich nicht als ersten Grund, daß der verbelastete Schüler auf Bubblesort kam. Mein erstes Sortierverfahren, was ich "erfunden" hatte, was mit mehr als 3 Variablen geht, war Bubblesort und kein anderes. Ich fühlte mich mit Schleifen und Arrays aber schon recht heimisch.

SeppJ schrieb:

Bubblesort ist also so schlecht, dass ein normaler Mensch nicht einmal auf die Idee käme, sofern man nicht mit Absicht ein abschreckendes Beispiel konstruieren möchte.

Auch hier widerspreche ich, denn ich kam auf Bubblesort und damals war ich noch normal. Meine Mutter hat mich testen lassen.

SeppJ

Der "vorbelastete" Schüler wusste aber sogar, dass das Bubblesort heißt. Es ging auch insgesamt mehr um die Einführung von Laufzeitanalyse und Laufzeitklassen. Der Lehrer hat dann auch jeden das Verfahren implementieren lassen, das derjenige erfunden hat (oder was ihm am besten gefiel) und gegeneinander antreten lassen für verschiedene Eingabegrößen. Und letztlich auch gegen ein Quicksort, welches der Lehrer aber selber vorstellen musste, weil man darauf nicht alleine im Rahmen von ein paar Unterrichtsstunden kommt (der vorbelastete Schüler kannte aber immerhin schon den Namen^*). Und dann jeweils theoretische Aufarbeitung der Komplexitätsklassen, auch für die selbsterfundenen Verfahren, mitsamt Erklärung, warum die zwar in der gleichen Klasse sind wie Bubblesort, aber trotzdem so viel schneller. Beim Bubblesort war es bloß am offensichtlichsten, dass es O(N²) ist, da wirklich im Vorhinein die Anzahl der Schritte feststeht (außer mit Vertauschungszähler), was bei Insertionsort wesentlich komplizierter ist, da man Erwartungswerte betrachten muss (Das war Oberstufe, da ist so etwas noch Neuland!).

Mein Informatiklehrer war schon ziemlich gut.

^*: Ich bin nicht mehr 100% sicher, ob es wirklich Quicksort war. Vielleicht hat nur der vorbelastete Schüler es "Quicksort" genannt. Denn Quicksort ist von den flotten Verfahren auch eines der komplizierteren. Ich glaube, es könnte eher Tree-Sort gewesen sein, da wir Bäume auch schon behandelt hatten und das Verfahren deshalb nahe lag. Oder vielleicht wurden auch Bäume anhand des Sortierverfahrens eingeführt. Das wäre natürlich auch clever gewesen. Ist leider zu lange her, ich erinnere mich nur noch an den Stoff und an einige besonders herausragende Unterrichtsstunden (wie zum Beispiel den Wettbewerb der Sortierimplementierungen), nicht mehr an die konkrete Abfolge.

volkard

SeppJ schrieb:

Es ging auch insgesamt mehr um … Mein Informatiklehrer war schon ziemlich gut.

Chapeau!
In der Lehre besser als einige meiner Informatik-Profs, will ich meinen.

So und jetzt quick oder heapsort

Kellerautomat

Ich hab schon Radixsort verwendet um Akten zu sortieren, bzw eine Kombination aus Radixsort und Mergesort wenn es zu viele wurden. Finde ich voll praktisch.
Die ganzen Laien sollten mal Sortieralgorithmen lernen, kann man im Buero gebrauchen.

icarus2

hardware schrieb:

heapsort

Heapsort ist leider (auch wenn die Laufzeitkomplexität optimal ist) in der Praxis ziemlich langsam wegen fehlender Lokalität.

SeppJ

Kellerautomat schrieb:

Ich hab schon Radixsort verwendet um Akten zu sortieren, bzw eine Kombination aus Radixsort und Mergesort wenn es zu viele wurden. Finde ich voll praktisch.
Die ganzen Laien sollten mal Sortieralgorithmen lernen, kann man im Buero gebrauchen.

Hah! So (Mergesort mit Cutoff bei ungefähr 4-5) habe ich auch mal Klausurabgaben nach Namen sortiert. Wobei ich aber den Eindruck hatte, dass meine Kollegen mit Insertionsort nicht langsamer waren. Ein großer Nachteil von Insertionsort, das teure Verrücken der Elemente, ist im echten Leben schließlich fast kostenlos. N war so ungefähr 25-50.

Jockelx

SeppJ schrieb:

Jockelx schrieb:

Z.B. viele vorsortierte Daten in den ersten 99% und das letzte 1% mit neuen, unsortierten Daten oder sowas.

So etwas wie 2 3 4 5 6 ... 97 98 99 1?

Ja, genau sowas.
Und wegen der groben Kenntnis der Daten geht das super schnell, da du natürlich anderes rum 'bubbelst' und die 1 in einem Lauf nach oben klettert.

SeppJ

Jockelx schrieb:

SeppJ schrieb:

Jockelx schrieb:

Z.B. viele vorsortierte Daten in den ersten 99% und das letzte 1% mit neuen, unsortierten Daten oder sowas.

So etwas wie 2 3 4 5 6 ... 97 98 99 1?

Ja, genau sowas.
Und wegen der groben Kenntnis der Daten geht das super schnell, da du natürlich anderes rum 'bubbelst' und die 1 in einem Lauf nach oben klettert.

Wenn du solch strenge Anforderungen an die Ausgangsdaten stellst ist ein Bubblesort die beste Methode, die dir einfällt, um das in Ordnung zu bringen?