Zusammenfassung Sortierverfahren

  • Da noch keiner hier irgendwas gepostet hat, werde ich mal meine € 0.02 besteuern. Keine Garantie darauf, dass auch nur irgendwas davon stimmt!


    4. Hier den (Straight) Insertion Sort. Bei dem werden nur die Elemente herumverschoben, die noch nicht sortiert sind. (also fast keine)


    5. Hier den Selection Sort. Minimale Datenbewegungen. (<= n)


    6.
    (Straight) Insertion Sort: n
    Selection Sort: n²
    Merge Sort: n log n
    Partiton Exchange (aka Quicksort): n²
    Heapsort: n log n


    7. Da versteh ich die Frage nicht. Bitte um Erklärung.

    I'm a pessimist because of intelligence, but an optimist because of will. -- Antonio Gramsci

  • 5: laut Skriptum auf Seite 38 auch Mergesort:

    Zitat

    Als alternative Datenstruktur eignen sich verkettete Listen, da alle Teilfolgen nur sequenziell abgearbeitet werden. Dann werden keine Daten bewegt, nur Zeiger verändert => Merge Sort ist deshalb auch gut als externes Suchverfahren geeignet


    9: Divide and Conquer: Merge- und Heapsort


  • 6.
    heap sort: Obwohl Best Case n log n ist, tritt bei gleichen Daten imho eine Laufzeit von n auf.
    Warum ?
    Beim Aufbau werden n/2 Element versickert, das Versickern ist IMMER konstant (drei Vergleiche, dann Abbruch).
    Beim Sortieren gibt es n Aufrufe von Versickere, wieder brechen sie nach jeweils 3 Vergleichen ab.


    9. Mergesort und Quicksort. Diese beiden Verfahren haben jeweils eine führen jeweils rekursive Aufrufe der linken und rechten Hälfte aus, wobei die Teilung einmal in der Mitte floor(n/2) bei Merge und einmal durch Partitioniere mit Hilfe des Pivotelements durchgeführt wird. Heap-Sort ist imho keine Teile und Herrsche Prozedur (denn die Menge wird nicht geteilt und getrennt bearbeitet)

  • @ shabby
    6. Stimmt schon das mit dem Merge Sort. Der scheint wirklich nur in n zu liegen. Beweisen kann ich das auch nicht, aber es ist recht anschaulich, wenn man es selbst zb. hier ausprobiert.


    7. Hat da irgendwer eine Ahnung, was sie damit meinen? Suchverfahren, die bei mehrmaligem Auftreten von Schlüsseln inkorrekt sortieren kennen wir ja nicht. (Siehe auch 6.) Oder meinen sie, ob/wie man die einzelnen Algorithmen stabil machen kann (Was ja eigentlich Frage 8 ist)?

    I'm a pessimist because of intelligence, but an optimist because of will. -- Antonio Gramsci

  • 6. Also dass da noch keiner draufgekommen ist!


    shabby und ich reden natürlich vom Heapsort !!!! (Siehe auch meinen Link) Der Mergesort liegt schon in n log n.
    Nur beim Heapsort sollte sich die Funktion Versickere bei gleichen Werten eben auf 3 Vergleiche beschränken (Zeile 2, 5, 11).
    Der Aufbau des ersten Heaps dauert (auch laut Skriptum) O(n).
    Die Funktion Versickere wird dann noch n-1 mal aufgerufen.
    Zusammengefasst (Alg 8):
    c1 + c2 + (n-1) * (c3 + c4) = n/2 * c4 + c2 + (n-1) * (c3 + c4)
    Wobei eben c4 nur 3 Vergleiche sind.
    Schlüsselvergleiche: 3 * (3n/2 + 1)
    Vertauschungen: n-1


    Könnte das stimmen???


    skytale : Ich glaub' irgendwie doch nicht, dass 7 nur eine Scherzfrage ist. wahrscheinlich ist sie nur schlecht formuliert.

    I'm a pessimist because of intelligence, but an optimist because of will. -- Antonio Gramsci

  • zu frage 2: man kann die liste doch nicht mit quicksort sortieren weil das erste element nicht das kleinste ist... was soll man euerer meinung denn dann machen? "falsch" sortieren?

  • Zitat

    Original geschrieben von PliniusSecundus
    SelectonS, InsertionS und BubbleS müssten die einzigen Alg sein, die im BestCase keine Moves produzieren?
    Ist das nun Mmin=theta(0) oder theta(1)?


    insertion sort tauscht doch auch elemente mit sich selbst, müsste bei vorsortierter folge doch zu konstantem aufwand führen, oder?
    (bei selection sort glaub ich auch, bin mir im moment nur nicht sicher...)


    demnach wäre der einzige alg. der wirklich keine moves erzeugt bubble sort, der nämlich wirklich nur elemente tauscht die unterschiedlich sind...


    /edit:
    hmm, selectionsort tauscht elemente auch nicht mit sich selbst, also dürfte der im best case auch keine moves durchführen

  • edit:
    ah verdammt, er hat die abstände nicht richtig übernommen, vielleciht sieht mans ja trotzdem raus, wenn nicht, einfach überlesen ...
    /edit



    ich denk ich habs doch hingekriegt:


    1 2 3 4 5 6 7
    7 1012 13 128 5 4711 34



    Baum: 7
    1012 13
    128 5 4711 34


    Verschiebung 4711
    1012 7
    128 5 13 34


    Neue Zeile
    1012 7 128 5 13 34 4711


    Baum 1012
    7 128
    5 13 34


    Verschiebung erspar ich mir mal
    NZ
    34 7 128 5 13 1012



    B 34
    7 128
    5 13


    NZ
    13 7 34 5 128


    B 13
    7 34
    5


    NZ
    5 7 13 34


    B 5
    7 13

    NZ
    5 7 13


    B 5
    7
    NZ
    5 7


    B 5 :cool:



    stimmt das sO? (ich hoff das sieht man übersichtlich genug)

  • Zitat

    Original geschrieben von FaKe
    zu 2. da krieg ich den heapsort nicht hin, hat den schon jemand und kanns mir hier rein stellen?


    1. erstelle heap:
    7,1012,13,128,5,4711,34
    7,1012,4711,128,5,13,34
    4711,1012,7,128,5,13,34
    4711,1012,34,128,5,13,7


    2. immer oberstes element mit letztem vertauschen und versickern:
    7,1012,34,128,5,13|4711
    1012,7,34,128,5,13
    1012,128,34,7,5,13


    13,128,34,7,5|1012
    128,13,34,7,5


    5,13,34,7|128
    34,13,5,7


    7,13,5|34
    13,7,5


    5,7|13
    7,5


    5|7


    => 5,7,13,34,128,1012,4711