stabil - instabil

[phlow]

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

[nexxyz]

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.

[phlow]

ich nehm mal an du hast dich vertippt und meinst eh selection sort

[qmp]

Suchfunktion benutzen ;)
http://frost.feig.at/informatik-forum/showthread.php?s=&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

[phlow]

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.

[nexxyz]

äääh...nein...hab mich verlesen und bei insertion-sort nachgeschaut...

[qmp]

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

[phlow]

jap, hast recht! danke dir!

[Iris]

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

[steve]

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

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

[Zentor]

Bis auf Insertionsort und Bubblesort sind doch alle anderen Sortierverfahren instabil oder? Wie sieht das sonst bei Merge und Heapsort aus?

[phlow]

Heap: instabil
Merge: stabil ... instabil ist der optimierte code auf seite 35

[Iris]

okej .. gewonnen :-))
Stimmt ..

[Zentor]

Also sollte man bei stabil/instabil bei Merge Sort stabil wählen...

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

[moose]

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.

[FaKe]

@ 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

[SinusDiabolicus]

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