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

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

  • Suchfunktion benutzen ;)
    http://frost.feig.at/informati…hread.php?s=&threadid=888


    SelectionSort ist instabil:

  • eben deswegen frage ich, weil ich es bezweifle ... siehe Begründung oben:


    Zitat


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

    Zitat


    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.

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

  • 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???

  • naja, du hast nur eine ungünstige Zahlenfolge als Beispiel gewählt.
    Mein Bsp:

    Code
    1. 3(a),5,3(b),1,2 //1 wird mit 3(a) vertauscht, damit er ganz nach vor kommt.
    2. 1,5,3(b),3(a),2 //2 wird mit 5 vertauscht
    3. 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------ .

  • 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)

  • Zitat

    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.

  • @ 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

  • 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:

    Zitat


    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