stabil - instabil
Results 1 to 18 of 18

Thread: stabil - instabil

  1. #1

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

    stabil - instabil

    Ist "Selection Sort", wenn man die Zeile 9 miteinbezieht (was im Skript ja nicht gemacht wird) stabil ??? Weil da wird ja dann keine Datenbewegung durchgeführt wenn zb 2 gleiche Zahlen da sind => sie sind in der Ausgabefolge genauso angeordnet wie in der Eingabefolge.

    Oder Irre ich mich da, wenn ja, bitte kurze erklärung wo mein Denkfehler liegt.

    thx

  2. #2
    nexxyz's Avatar
    Title
    Elite
    Join Date
    Apr 2002
    Location
    Wien
    Posts
    404
    Thanks
    0
    Thanked 0 Times in 0 Posts
    hmmm....da insertion-sort von links nach rechts arbeitet und immer das kleinste element mit dem 'aktuellen' vertauscht...und nie auf sich selbst...sollte der algorithmus stabil sein.

    ja.

    glaub ich.
    “It is a fool's prerogative to utter truths that no one else will speak.”
    (\)exxyz-Music-Home

  3. #3

    Title
    Mag.rer.soc.oec
    Join Date
    Nov 2001
    Location
    dzt. München
    Posts
    1,270
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ich nehm mal an du hast dich vertippt und meinst eh selection sort

  4. #4

    Title
    Principal
    Join Date
    Dec 2001
    Posts
    88
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Suchfunktion benutzen
    http://frost.feig.at/informatik-foru...=&threadid=888

    SelectionSort ist instabil:
    Original geschrieben von Jimmy
    Selection Sort - da gabs im alten Skriptum angeblich 2 Versionen vom Algorithmus... die version die <b>wir</b> im NEUEN haben ist instabil..
    weil ja zum Bsp.
    2(a),2(b),1 sortiert wird in 1,2(b),2(a) -> er vertauscht ja das erste Element mit dem letzten A[minpos] ---> instabil !
    im alten Skriptum gabs ne <k>optimierte</k> Version vom Selection Sort die stabil war - laut Tutorium zumindest.
    also wenn gefragt ist , ob Sel.S stabil oder instabil ist, einfach angeben ,dass dies vom Sortieralgorithmus abhängt,da es beides seien kann..

    gute n8, jim

  5. #5

    Title
    Mag.rer.soc.oec
    Join Date
    Nov 2001
    Location
    dzt. München
    Posts
    1,270
    Thanks
    0
    Thanked 0 Times in 0 Posts
    eben deswegen frage ich, weil ich es bezweifle ... siehe Begründung oben:

    .. wenn man die Zeile 9 miteinbezieht (was im Skript ja nicht gemacht wird) stabil ??? Weil da wird ja dann keine Datenbewegung durchgeführt wenn zb 2 gleiche Zahlen da sind => sie sind in der Ausgabefolge genauso angeordnet wie in der Eingabefolge.
    ich würde eben gerne wissen was ihr von der Argumentation haltet, dass vorher schon geposted wurde das es instabil ist weis ich, ....

    Bitte um Kommentare zu meinen Zweifeln (Beweis / Gegenbeweis )

    Edit:

    in deinem Quote steht übrigens nicht explizit drin das es instabil ist, wie du behauptest:
    also wenn gefragt ist , ob Sel.S stabil oder instabil ist, einfach angeben ,dass dies vom Sortieralgorithmus abhängt,da es beides seien kann..
    .... das problem ist, wir sollen "stabil" oder "instabil" ankreuzen (siehe frühere Prüfungen) und da tut man sich dann mit solchen Argumentationen (die sicher korrekt sind) imho schwer.
    Last edited by phlow; 15-04-2002 at 18:47.

  6. #6
    nexxyz's Avatar
    Title
    Elite
    Join Date
    Apr 2002
    Location
    Wien
    Posts
    404
    Thanks
    0
    Thanked 0 Times in 0 Posts
    äääh...nein...hab mich verlesen und bei insertion-sort nachgeschaut...
    “It is a fool's prerogative to utter truths that no one else will speak.”
    (\)exxyz-Music-Home

  7. #7

    Title
    Principal
    Join Date
    Dec 2001
    Posts
    88
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Selection Sort ist so wie wir es kennen Algo 2 im Skriptum instabil, egal ob mit oder ohne Zeile 9

    Zeile 9 vermeidet ja nur das unnötige Vertauschen, es hindert aber nicht dass gleich große Schlüssel aneinander vorbeibewegt werden

    siehe Bsp: 2(a),2(b),1 wird zu 1,2(b),2(a) egal ob mit oder ohne Zeile 9

    um SelectionSort stabil zu machen müsste man schon erheblich mehr Aufwand betreiben, oder hat jemand eine Idee?

    Bei einer Kreuzerlfrage würde ich instabil ankreuzen ...
    Last edited by qmp; 15-04-2002 at 19:15.

  8. #8

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

  9. #9

    Title
    Veteran
    Join Date
    Apr 2002
    Posts
    24
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Hmm .. ich sehe eigentlich nicht, wo gleich große Schlüssel bei selection sort aneinander vorbei sortiert werden, denn wenn man das Beispiel mit 5,2,2,1 dann bewegen sich die zwei zweier nicht, sonder nur der einser mit dem 5er
    Habe ich da einen Denkfehler???

  10. #10
    steve's Avatar
    Title
    Super Moderator
    Join Date
    Jan 2002
    Location
    planet earth
    Posts
    539
    Thanks
    14
    Thanked 2 Times in 2 Posts
    naja, du hast nur eine ungünstige Zahlenfolge als Beispiel gewählt.
    Mein Bsp:
    Code:
    3(a),5,3(b),1,2   //1 wird mit 3(a) vertauscht, damit er ganz nach vor kommt.
    1,5,3(b),3(a),2   //2 wird mit 5 vertauscht
    1,2,3(b),3(a),5   //fertig sortiert.
    du merkst, 3(a) hat den anderen dreier beim Vertauschen "überholt"...
    -----BEGIN GEEK CODE BLOCK-----
    Version: 3.12
    GAT d-(+) s++: a- C++$>+$ U++>+++ P++>+++ L+++ !E W++>$ !N K? w(--)@ !O !M V? PS+ PE++(-)> Y+ PGP(+) t---(-) !5 X R- tv-(--) b++>$ DI+ D+(++) G(+) e>++++* h-- r++ y++
    ------END GEEK CODE BLOCK------ .

  11. #11
    Zentor's Avatar
    Title
    CO-Administrator
    Join Date
    Dec 2001
    Location
    Wien???
    Posts
    1,156
    Thanks
    2
    Thanked 9 Times in 6 Posts
    Bis auf Insertionsort und Bubblesort sind doch alle anderen Sortierverfahren instabil oder? Wie sieht das sonst bei Merge und Heapsort aus?

  12. #12

    Title
    Mag.rer.soc.oec
    Join Date
    Nov 2001
    Location
    dzt. München
    Posts
    1,270
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Heap: instabil
    Merge: stabil ... instabil ist der optimierte code auf seite 35

  13. #13

    Title
    Veteran
    Join Date
    Apr 2002
    Posts
    24
    Thanks
    0
    Thanked 0 Times in 0 Posts
    okej .. gewonnen :-))
    Stimmt ..

  14. #14
    Zentor's Avatar
    Title
    CO-Administrator
    Join Date
    Dec 2001
    Location
    Wien???
    Posts
    1,156
    Thanks
    2
    Thanked 9 Times in 6 Posts
    Also sollte man bei stabil/instabil bei Merge Sort stabil wählen...

  15. #15
    SinusDiabolicus's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Location
    Wien
    Posts
    383
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ja!
    wie schon in einem anderen thread erwähnt, ist ein alg. laut skriptum stabil, wenn man ihn so implementieren kann, das er sich eben stabil verhält, soll heissen, wenn auch nur eine einzige möglichkeit besteht den alg. stabil zu implementieren, ist er auch stabil
    (das bezieht sich halt auf die idee die hiner dem alg steht und nicht auf eine bestimmte umsetzung)

  16. #16

    Title
    Principal
    Join Date
    Feb 2002
    Location
    wien
    Posts
    59
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Original geschrieben von SinusDiabolicus
    ja!
    wie schon in einem anderen thread erwähnt, ist ein alg. laut skriptum stabil, wenn man ihn so implementieren kann, das er sich eben stabil verhält, soll heissen, wenn auch nur eine einzige möglichkeit besteht den alg. stabil zu implementieren, ist er auch stabil
    (das bezieht sich halt auf die idee die hiner dem alg steht und nicht auf eine bestimmte umsetzung)
    dann ist aber jeder algo stabil, denn es gibt sicher zu jeder idee vom sortieren einen algo, der die stabilitätsbedingung erfüllt.... ich muss ja nur bei 3a,5,3b,1 (selection sort) nicht den einser mit 3a vertauschen, sondern alles nach hinten schieben (1,3a,5,3b)... braucht erheblich mehr zeit, aber in der umsetzung isser sicher stabil.

  17. #17

    Title
    Principal
    Join Date
    Apr 2002
    Posts
    41
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @ moose: Korrigiert mich, wenn ich mich irre, aber wenn du 1 einfach nur nach hinten schiebst ist das nicht mehr selection sort (von der grundidee) sondern insertion sort

  18. #18
    SinusDiabolicus's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Location
    Wien
    Posts
    383
    Thanks
    0
    Thanked 0 Times in 0 Posts
    edit:
    mein nein... is an moose gerichtet nicht an fake, ich sollte schneller posten *gg*
    /edit

    nein, weil die grundidee gleich bleibt, und man nicht durch irgendwelche "unnötigen" aktionen erzwingen darf den alg stabil zu halten, sonst könnt ich ja einfach zuerst mal die ganze folge durchgehen ob gleiche elemente enthalten sind, und die dann zusammenfassen, also alles darf man nicht *gg*

    ausserdem steht im skriptum eben wie gesagt:
    Ein Sortierverfahren heißt stabil, wenn es so implementiert werden kann, dass die Reihenfolge....
    und es steht auch drin das es bei merge sort von der implementierung abhängt ob er stabil ist

    aus diesen zwei aussagen folgt: merge sort ist stabil
    Last edited by SinusDiabolicus; 16-04-2002 at 23:52.

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
  •