ShellSort

Der ShellSort ist im Prinzip nur eine verbesserte Variante des InsertionSorts. Durch Tauschen von Elementen bringt der InsertionSort diese an ihre endgültige Position in der zu sortierenden Menge. Ist ein Elemente weit von seiner endgültigen Position entfernt, sind sehr viele Tauschoperationen notwendig, bis das Element einsortiert wird, und dadurch werden schlechte Laufzeiten erzielt. Genau hier setzt die Idee des ShellSorts ein, um das ``Verschieben'' von Elementen über große Distanzen hinweg effizienter zu gestallten.

Im allgemeinen erzielt der ShellSort bessere Laufzeiten und ist somit dem InsertionSort vorzuziehen. Durch eine entsprechende, scheinbare Teilung der zu sortierenden Datenmenge, läßt der ShellSort den InsertionSort auf diesen Mengen arbeiten. Der Clue hierbei ist, daß die entstehenden Mengen nicht zusammenhängend sind und die Sortierung ``in-place'' geschieht.

Zu bemerken sei, daß durch die Art des ShellSorts sich für ihn eigentlich nur Mengen, die durch zusammenhänden Speicher representiert sind, eignen, da der Algorithmus über eine Addresse direkt auf ein Element zugreifen muss. Bei verketten Listen wäre eine Iteration notwendig um dieses ausfindig machen, was zu sehr schlechtem Laufzeitverhalten des Algorithmus führen würde.


Unterabschnitte
Nächste Seite  Aufwärts  Vorherige Seite  Inhalt 


Nächste Seite: Arbeitsweise Aufwärts: Sortieren Vorherige Seite: Laufzeitkomplexität   Inhalt

2002-05-09