Insertionsort


Insertionsort (Sortieren durch Einfügen):

 

Beim Insertionsort wird die erste Zahl im Zahlenfeld als sortiert angenommen.

Der Algorithmus betrachtet jeweils die folgende Zahl und falls diese größer ist, wird die Zahl direkt in den sortierten Bereich am Ende eingefügt. Ansonsten wird die Zahl an der richtigen Position in dem sortierten Feld eingefügt.

Der Algorithmus endet, nachdem die letzte Zahl in das sortierte Feld eingefügt wurde.

 

Bei einem bereits (aufsteigend) sortiertem Zahlenfeld ist die Laufzeit von Insertionsort linear (O(n)), da die Zahlen nur jeweils an das Ende des sortierten Feldes angehängt werden.

Bei einem noch nicht sortierten Zahlenfeld entspricht die Laufzeit der Summe aller aufgerundeten Logarithmen zur Basis 2 von n+1 für n ∈ Natürliche Zahlen und n < Anzahl der zu sortierenden Elemente (O(n²)).

 

Quelltext

Ein nicht optimierter Insertionsort ist im folgenden Quelltext dargestellt:

for(int i = 1; i < zahlenfeld.length;i++){

     int temp = zahlenfeld[i];

     int j = i;

     while(j > 0 && zahlenfeld[j-1] > temp){

          zahlenfeld[j] = zahlefeld[j-1];

          j--;

     }

     zahlenfeld[j] = temp;

}

 

Ein optimierter Insertionsort ist im folgenden Quelltext dargestellt:

int i, j, speicher;

        i = 1;

        while(i< zahlenfeld.length )

        {

            if(zahlenfeld[i]>zahlenfeld[i-1]){i++;}

            else{speicher = zahlenfeld[i];

                j = i;

                while(j >= 1 && zahlenfeld[j-1] > speicher)

                { zahlenfeld[j] = zahlenfeld[j-1];

                    j--;

                }

                zahlenfeld[j] = speicher;

                i++;

            }

        }