Was passiert wenn ein Sortieralgorithmus versagt?
-
Ich beschäftige mich aktuell mit verschiedenen Sortieralgorithmen um Werte in Arrays zu sortieren.
Leider sind die schnellsten Filter die, die nicht stabil sind.Leider sagen mir Wicki und Google nur dass die diversen Sortieralgorithmen versagen können.
Aber ich kann aber keine Informationen darüber finden wann Shell Sort, Quick Sort und dergleichen versagen und wie sich dieses Versagen äußert.
Wird da im Fall des Versagens nur länger gebraucht bis fertig sortiert wurde oder wird ein falsches Sortierergebnis geliefert?Kann mir bitte jemand Informationen darüber geben?
-
Wenn du nicht gerade mitten im Sortiervorgang den Stecker ziehst, dürfte da nix versagen.
Nicht verzagen, versag0r fragen
-
"Versagen" tun die nicht. Ein stabiler Sortieralgorithmus hat die Eigenschaft, dass er die Reihenfolge von als "gleich" eingestuften Elementen nicht ändert (so dass man beispielsweise eine Dateiliste erst nach Namen und dann nach Erweiterung sortieren kann), ein instabiler hat das nicht. Welchen man nimmt, hängt davon ab, ob man auf diese Eigenschaft angewiesen ist oder nicht.
-
Die normalen Sortierverfahren versagen nie. Stabilitaet hat damit aber nichts zu tun. Aber es gibt Sortierverfahren wie Bogosort (kein normales Verfahren), das eine sehr schlechte worst case Komplezitaet hat. http://en.wikipedia.org/wiki/Sorting_algorithm
-
Danke für eure Hinweise.
@knivil
Danke für den Link
Ich habe zwar einiges im Wicky gelesen aber diese Seite habe ich übersehen.