DAA - Insertion Sort

Die Einfügesortierung ist eine sehr einfache Methode, um Zahlen in aufsteigender oder absteigender Reihenfolge zu sortieren. Diese Methode folgt der inkrementellen Methode. Es kann mit der Technik verglichen werden, wie Karten zum Zeitpunkt des Spielens sortiert werden.

Die Nummern, die sortiert werden müssen, sind bekannt als keys. Hier ist der Algorithmus der Einfügesortiermethode.

Algorithm: Insertion-Sort(A) 
for j = 2 to A.length 
   key = A[j] 
   i = j – 1 
   while i > 0 and A[i] > key 
      A[i + 1] = A[i] 
      i = i -1 
   A[i + 1] = key

Analyse

Die Laufzeit dieses Algorithmus hängt stark von der gegebenen Eingabe ab.

Wenn die angegebenen Zahlen sortiert sind, wird dieser Algorithmus ausgeführt O(n)Zeit. Wenn die angegebenen Zahlen in umgekehrter Reihenfolge sind, wird der Algorithmus ausgeführtO(n²) Zeit.

Beispiel

Unsorted list:

2 13 5 18 14

1^st iteration:

Schlüssel = a [2] = 13

a [1] = 2 <13

Tauschen, kein Tauschen

2 13 5 18 14

2^nd iteration:

Schlüssel = a [3] = 5

a [2] = 13> 5

Tauschen Sie 5 und 13

2 5 13 18 14

Als nächstes ist a [1] = 2 <13

Tauschen, kein Tauschen

2 5 13 18 14

3^rd iteration:

Schlüssel = a [4] = 18

a [3] = 13 <18,

a [2] = 5 <18,

a [1] = 2 <18

Tauschen, kein Tauschen

2 5 13 18 14

4^th iteration:

Schlüssel = a [5] = 14

a [4] = 18> 14

Tauschen Sie 18 und 14

2 5 13 14 18

Als nächstes ist a [3] = 13 <14,

a [2] = 5 <14,

a [1] = 2 <14

Also kein Tausch

2 5 13 14 18

Schließlich,

the sorted list is

2 5 13 14 18