Sortieralgorithmus

[Delphi-Laie]

Zitat von snears:

Ich habe eine Frage und zwar würde ich gerne wissen was passiert wenn ein ein sortieralgorithmus auf ein bereits sortiertes Feld angewandt wird?

Diese Eigenschaft, auf (Vor-)Sortierungen gegenüber völlig unsortierten/-geordneten Mengen mit einer merklichen Laufzeitverkürzung zu reagieren, nennt sich Adaptivität.

Schneller werden alle Sortieralgorithmen, die auf Vergleichen und vor allem (weil in diesem Kontext wichtig) Vertauschungen basieren, schon deshalb geringfügig, weil die Vertauschungen weniger werden oder gar entfallen. Andere Sortieralgorithmen, die nicht auf Vergleichen beruhen, haben m.E. überhaupt nichts von einer (Vor-)Sortierung, die sind immer gleich schnell. Doch die fehlenden Vertauschungen allein reizen das Beschleunigungspotential nicht immer aus, d.h., Adaptivität ist mehr.

Daß Bubblesort per se adaptiv ist, ist allerdings falsch. Vielmehr muß ein etwas höherer Entwicklungs- und Programmieraufwand betrieben werden, um ihn für (vor-)sortierte Mengen merklich zu beschleunigen. In meinem "Sortierkino" (auch hier im Forum zu finden) machte ich Bubblesort adaptiv, ließ aber den originalen - und bezüglich der Adaptivität eben völlig "unintelligenten" - Quellcode auskommentiert dort stehen. Einfach mal beides ausprobieren.