| 
  • If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

View
 

Insertionsort

Page history last edited by wikiuser0009 2 years ago

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++;

            }

        } 

 

 

 

Comments (0)

You don't have permission to comment on this page.