Bubblesort geht nicht

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?

Jockelx

Also, ich hab ja schon geschrieben, dass ich das nie selber gebraucht habe und ich bewege mich auf dünnem Eis.
Kann also gut sein, das ich Unsinn erzähle.
Aber Bubblesort ist halt so extrem einfach, dass man ihn extrem gut modifizieren kann.
Also zumindest schonmal:
- swap-Test
- Bubble-Reihenfolge (zur Not alternierend)
- letzte swap-Position

Die 'strenge Anforderung' war nicht, dass 99% volständig sortiert sind, sondern nur vorsortiert.
D.h. ein paar falsche Daten können da drin sein.
Welche Methode schlägst du denn vor?

Jockelx

Ok, mit den 99%-1% ist wohl schlecht.
Da bietet sich wohl an, die 99% erst zu sortiern und die letzten mit binärer Suche einzufügen.
Aber wie würdest du die vorsortierte Daten sortieren?

Jockelx schrieb:

Aber wie würdest du die vorsortierte Daten sortieren?

Halt einen guten adaptiven Sortieralgorithmus raussuchen. Smoothsort wäre das akademische Beispiel. Wächst nicht von O(n) im Idealfall zu O(n^2) im schlimmsten Fall sondern nur bis O(n log n) und ist auch O(n) in mehr vorsortieren Fällen. In der Praxis dann Timsort.

Jockelx

Na gut, will ich das mal glauben.
Macht auch keinen Sinn mit mir zu diskutieren, weil ich Smothsort und Timsort nichtmal gekannt habe.
Meine Sortiererei sieht eh so aus:

container.sort();  // Wirst schon wissen, was du da machst

volkard

needle in bubblestack schrieb:

In der Praxis dann Timsort.

Bin da nicht sicher, daß man das in C++ nehmen möchte, wo swap oder move auch mal was mehr kosten könnte als zwei Zeiger auf GC-Typen zu tauschen oder einen zu kopieren.

Wahrscheinlich eine doofe Frage aber kann mir wer erklären wofür dieser Codeabschnitt gut sein soll?

for ( j=0; j<i; j++)
            {
                if( lotto [j] == lotto [i])
                {
                    neueZahl = false;
                }
            }

Zuerst wird den Elementen des Array ja zufallszahlen zugeordent aber was soll dieser Abschitt bewirken?

Ist das nur dafür da um zu prüfen ob eine Zahl Mehrfach vorkommt und dann falls ja eine neue zu erzeugen?
Ich bin leider sehr schlecht darin fremden Code zu verstehen .

SeppJ

Ja. Der aktuelle Wert ( lotto[i] ) wird dafür mit allen anderen Werten verglichen. Ist ein Wert gleich, so wird ein entsprechendes Flag ( neueZahl ) gesetzt, dass dann im Rest des Codes (Zeilen 17-27) dafür sorgt, dass lotto[i] neu gezogen wird.

Der vom Threadersteller gezeigte Code ist sicherlich kein all zu tolles Vorbild, weder von der Idee, und ganz bestimmt nicht von der Umsetzung her.