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

  • Social distancing? Try a better way to work remotely on your online files. Dokkio, a new product from PBworks, can help your team find, organize, and collaborate on your Drive, Gmail, Dropbox, Box, and Slack files. Sign up for free.

View
 

Insertionsort

Page history last edited by wikiuser0007 1 year 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 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 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;

}

 

 

Comments (0)

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