Warum ist der Quick Sort instabil?
ich habe morgen einen Vortrag über quick sort und stoße immer wieder darauf, dass es ein instabiler sortieralgorithmus ist. Kann mir das jemand erklären, was damit gemeint ist? Am besten auf Schüler Niveau :)
2 Antworten
Angenommen du hast von einem Wettbewerb eine Liste die zwei Informationen enthält: die Neuen der Teilnehmer und die Punktzahlen. Die Liste ist dabei nach der Alphabetischen Reihenfolge der Namen sortiert.
Angenommen du willst nun die Liste nach den Punktzahlen sortieren. Damit die Liste jedoch "neutral" bleibt, sollen aber die Leute, die die selbe Punktzahl haben, immer noch alphabetisch geordnet bleiben.
Ein Stabiles Sortierverfahren erfüllt diese Eigenschaft, ein instabiles Sortierverfahren hingegen nicht.
Anders ausgedrückt:
Wenn du eine Liste hast, die zwei identische Werte haben, dann sorgt ein stabiles Sortierverfahren dafür, dass der erste wert nach dem Sortieren immer noch links vom zweiten wert bleibt.
Wenn das Verfahren hingegen nicht stabil ist, kann die Reihenfolge vertauscht werden.
Bei Quicksort kann sowas zum Beispiel passieren.
Der QuickSort-Algorithmus ist ein instabiler Sortieralgorithmus, weil er die relative Reihenfolge der Elemente mit gleichem Wert bei der Sortierung ändern kann.
Ein instabiler Algorithmus ist einer, der die Reihenfolge von Elementen mit gleichem Wert nicht beibehält. Ein stabiler Algorithmus hingegen bewahrt die Reihenfolge von Elementen mit gleichem Wert bei.
Um es einfacher zu verstehen, stell dir vor du hast eine Liste mit Namen und Alter von Personen. Wenn du die Liste nach Alter sortieren möchtest, dann werden die Namen nach Alter sortiert, aber es kann passieren, dass Personen mit gleichem Alter nicht mehr in der gleichen Reihenfolge sind wie vorher. Wenn die Personen mit gleichem Alter z.B. den gleichen Namen haben, dann kann es sein, dass sie nicht mehr nebeneinander stehen.
Ein Beispiel für einen stabilen Sortieralgorithmus ist der Insertion Sort oder der Merge Sort.