Zusammenfassung Sortierverfahren
Results 1 to 16 of 16

Thread: Zusammenfassung Sortierverfahren

  1. #1

    Title
    Principal
    Join Date
    Feb 2002
    Posts
    57
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Zusammenfassung Sortierverfahren

    Hat schon jemand Lösungen für die Fragen unter 2.8 auf Seite 53? Insbesondere für 4. bis 7.
    Ich mach jedenfalls einmal ein Thema zur Diskussion auf...

  2. #2

    Title
    Veteran
    Join Date
    Feb 2002
    Posts
    22
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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&#178;
    Merge Sort: n log n
    Partiton Exchange (aka Quicksort): n&#178;
    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

  3. #3

    Title
    Master
    Join Date
    Feb 2002
    Posts
    141
    Thanks
    0
    Thanked 0 Times in 0 Posts

    ...

    5: laut Skriptum auf Seite 38 auch Mergesort:
    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

  4. #4

    Title
    Mag.rer.soc.oec
    Join Date
    Nov 2001
    Location
    dzt. München
    Posts
    1,270
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: ...

    Original geschrieben von MrBurnst


    9: Divide and Conquer: Merge- und Heapsort
    Also Heapsort ... ich weis net, bist sicher!?
    Warum nicht auch Quicksort? Das teilt ja auch alles in 2 Teile (mit Hilfe des Pivot Elementes)

  5. #5
    shabby's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Location
    Schrödinger, 1040 Wien
    Posts
    267
    Thanks
    2
    Thanked 9 Times in 8 Posts
    Original geschrieben von ded
    6.
    (Straight) Insertion Sort: n
    Selection Sort: n&#178;
    Merge Sort: n log n
    Partiton Exchange (aka Quicksort): n&#178;
    Heapsort: n log n
    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)
    Last edited by shabby; 15-04-2002 at 22:39.

  6. #6

    Title
    Veteran
    Join Date
    Feb 2002
    Posts
    22
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @ 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)?
    Last edited by ded; 15-04-2002 at 20:42.
    I'm a pessimist because of intelligence, but an optimist because of will. -- Antonio Gramsci

  7. #7

    Title
    Master
    Join Date
    Mar 2002
    Posts
    158
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Ich denk mir Frage 7 ist einfach ein fake. Du musst die Algorithmen gar nicht verändern.

    6) Wenn Merge-Sort wirklich in n liegt, wär ja das ein (weiterer) Fehler im Skriptum.

  8. #8

    Title
    Veteran
    Join Date
    Feb 2002
    Posts
    22
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.
    Last edited by ded; 16-04-2002 at 00:43.
    I'm a pessimist because of intelligence, but an optimist because of will. -- Antonio Gramsci

  9. #9

    Title
    Master
    Join Date
    Feb 2002
    Posts
    141
    Thanks
    0
    Thanked 0 Times in 0 Posts

    wowowow!!!

    da hab ich wohl für etwas verwirrung gesorgt... ich glaub auch nicht dass heapsort nach dem prinzip funkt... hab auch quicksort gemeint...

  10. #10

    Title
    Principal
    Join Date
    Feb 2002
    Posts
    57
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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)?

  11. #11

    Title
    Master
    Join Date
    Feb 2002
    Posts
    141
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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?

  12. #12
    Zentor's Avatar
    Title
    CO-Administrator
    Join Date
    Dec 2001
    Location
    Wien???
    Posts
    1,156
    Thanks
    2
    Thanked 9 Times in 6 Posts
    Wird durch das Stoppelement immer möglich, schau im Skriptum nach, man stellt an den anfang der Folge immer einen gesonderten Wert der kleiner als jeweils die restlichen ist = Stoppelement

  13. #13
    SinusDiabolicus's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Location
    Wien
    Posts
    383
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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

  14. #14

    Title
    Principal
    Join Date
    Apr 2002
    Posts
    41
    Thanks
    0
    Thanked 0 Times in 0 Posts
    zu 2. da krieg ich den heapsort nicht hin, hat den schon jemand und kanns mir hier rein stellen?

  15. #15

    Title
    Principal
    Join Date
    Apr 2002
    Posts
    41
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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


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

  16. #16

    Title
    Principal
    Join Date
    Feb 2002
    Location
    wien
    Posts
    59
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •