3. Bubblesort geht nicht

Bubblesort geht nicht

  • I

    hardware schrieb:

    heapsort

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

    0
  • Mod

    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.

    0
  • J

    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.

    0
  • Mod

    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?

    0
  • J

    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?

    0
  • J

    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?

    0
  • ?

    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.

    0
  • J

    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
    0
  • V

    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.

    0
  • ?

    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?

    0
  • ?

    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 😞 .

    0
  • Mod

    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.

    0
Anmelden zum Antworten