Bubblesort geht nicht

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.