Insertionsort

Der Insertionsort arbeitet sozusagen mit 2 Listen. in Liste eins stehen die ungeordnenten Werte, während Liste 2 am Anfang leer ist.

1. Im ersten Arbeitsschritt wird dabei der erste Wert von links aufgedeckt, an die erste Stelle gestellt, als erster Teil des Arrays gespeichert und aus Liste eins gelöscht.
   
   
2. Im Arbeitsschritt zwei wird zuerst die Position des zweiten Wertes bestimmt. Ist dieser kleiner als der erste Wert, wird der 2. Wert zum ersten Teil des Arrays und der erste Wert zum zweiten Teil, ist er größer, wird der zweite Wert hinter dem ersten eingefügt. Danach wird eben jener neue Wert aus Liste eins gelöscht.
   
   
3. Der Algorithmus fährt dann mit den restlichen Werten ähnlich fort.
   

• Ist der Wert kleiner als der zu überprüfende Wert, wird er davor eingefügt und die nachfolgenden Werte werden um eine Position nach hinten verschoben(ergebnis[i]=ergebnis[i+1]).
  
• Ist der Wert größer als der zu überprüfende Wert, springt der Algorithmus eine Stelle weiter und beginnt wieder bei Punkt drei.

for (int i=1; i < vector.length; i++)
{
int temp = vector[i];
int j = i - 1;

while (j >= 0 && vector[j] > temp){
vector[j + 1] = vector[j];
j–;
}
vector[j+1] = temp; }

http://de.wikipedia.org/wiki/Insertionsort