Navigation-Bar

Seminare

InsertionSort

InsertionSort verfährt nach folgender Methode: 

Nehmen wir an, a[1],...,a[i-1] seien bereits sortiert, d.h. a[1].key £ ... £ a[i-1].key. Dann wird das i-te Element a[i] an der richtigen Stelle in die Folge a[1],...,a[i] eingefügt. Das Einfügen geschieht so, dass man a[i].key der Reihe nach mit a[i-1].key, a[i-2].key,.. vergleicht und dann das Element a[j] dabei jeweils um eine Position nach rechts verschiebt, für j=i-1,i-2,...,wenn a[j].key > a[i],key ist. Sobald a[j].key £ a[i].key, hat man die Stelle gefunden, na der das Element a[i] eingefügt werden kann, nämlich die Position j+1.

Analyse:

• WorstCase : O(n²)

Warum:  Zum Einfügen des i. Elementes werden mindestens 1 und maximal i Vergleiche und  mindestens zwei oder höchstens i+1 Bewegungen von Datensätzen ausgeführt.

--> O(n*n-1)=O(n²)

• AverageCase: O(n²)

• BestCase (vorsortiert): O(n)

FAZIT:

·        InsertionSort profitiert im Gegensatz zu SelectionSort von einer Vorsortierung

·        Iterativer Algorithmus

·        In-Place Algorithmus

·        Vorgehen wie bei Skat Spiel

·        Worstcase O(n²)

·     AverageCase O(n²)

Skripte Top 5

Der Klassiker