Start

Sortieralgorithmen  

Suchalgorithmen  

Datenstrukturen  

Verschiedenes  

Quellen  

Bubblesort

Insertionsort

Selectionsort

Quicksort

Shellsort

Mergesort

Countingsort

Optimierung

Ausgehen von der Annahme, die Datenmenge sei ein kontiunierlich zusammenhängender Speicherbereich, ist das ständige Vorschieben des Markenelements bis zu seiner richtigen Position, eine effiziente Methode. Würde man zuerst die richtige Postion ausfindig machen und erst danach das Element an dieser einfügen, so müsste man das aufwendige Einfügen des Elements in die Datenmenge in Kauf nehmen. Aufwendig vor dem Hintergrund, da es notwendig ist, alle Elemente nach der Einfügeposition um eine Stelle zu verschieben, was eine Iteration über diese bedeutet und somit Rechenzeit kostet. Von daher ist das Vorschieben des Markenelements in einem kontinuierlichem Speicherbereich (Array) geradezu schon optimiert.

Genau umgekehrt jedoch sieht die Situation aus, wenn man von einer Datenmenge ausgeht, die als verkette Liste implementiert ist. Würde man das Markenelement wie in obiger Situation ständig vorschieben, würde dies eine ständige Neuverlinkung der Datenelemente bedeuten (siehe verkettete Listen). Da aber auf verketteten Listen die Einfügeoperation sehr effizient ist, liegt der Ansatz, zuerst die richtige Position ausfindig zu machen und das Markenelement erst dann dort einzufügen, viel näher und trägt zur Optimierung der Implementierung bei, da das ständige Verlinken vermieden wird. Um das Mass der Optimierung zu erfahren, werde man sich dessen bewusst, dass das Vorschieben des Markenelements im nichtoptimierten Fall grob geschätzt mal und im optimierten Fall nur noch mal ausgeführt wird. Dies heisst allerdings nicht, dass die Laufzeitkomplexität des Algorithmus verbessert wird. Dies ist nur eine Implementierungsoptimierung, die sich aber in der messbaren Ausführungszeit auf grossen Mengen durchaus bemerkbar machen kann.

Ein anderes Verfahren, dass zur Sortierung benutzt wird und auf dem InsertionSort aufbaut, heisst ShellSort und kann gegebenenfalls als eine Optimierte Variante des InsertionSorts aufgefasst werden. Der ShellSort wird separat behandelt und vorgestellt.

Nächste Seite: SelectionSort Aufwärts: InsertionSort Vorherige Seite: Implementierung   Inhalt