Stabile Sortierverfahren

  • hi leute,


    frage: welche der sortieralgos (insert, select, merge,quick,heap) KANN man stabil implementieren? das is eine prüfungsfrage und ich würd sagen man KÖNNTE alle stabil implementieren, wenn man a bissl gschickt ist. ich mein, ich könnts nicht , aber das is a andere geschichte :coolsmile
    also wenn mir von euch was dazu sagen könnt, ich bin für alle meinungen offen, solange sie überzeugend sind.


    thx schon mal,
    Cracker

  • stabil sind nur der Insertion-Sort und die 2. Implementierungsversion des Merge-Sorts (=die kürzere)


    das mit dem "geschickt sein" würd ich so nicht sagen, wenn du die anderen Algorithmen stabil implementieren willst musst du warscheinlich neuartige Verfahren entwickeln. ;)


    z.B.: die Idee von Selection-Sort ist, das jeweils kleinste Element auszuwählen und an die richtige Stelle zu schreiben und dabei wird mehrmals "über den Kopf anderer Elemente" getauscht, d.h. egal wie du es implementierst, wenn du dieses Verfahren zur Sortierung anwenden willst, wird dein Alg bei korrekter Verfahrensumsetzung instabil bleiben ....

  • Zitat

    Original geschrieben von Länz
    stabil sind nur der Insertion-Sort und die 2. Implementierungsversion des Merge-Sorts (=die kürzere)


    BubbleSort ist auch stabil: es werden immer nur Nachbarn vertauscht, jedoch nicht wenn sie gleich groß sind, so kann kein Element an einem gleichgroßen anderen Element vorbeibewegt werden.