Bei Insertionsort handelt es sich um ein sehr einfaches und verständliches Sortierverfahren. Die Elemente, die sortiert werden sollen, werden direkt ausgewählt und dann an die richtige Stelle getauscht.

Ablauf:

Ausgehend von einem Teilfeld , welches bereits sortiert ist (zu Beginn enthält das Teilfeld nur das Startelement), und kleiner ist als das Gesamtfeld, wird ein weiteres Element aus dem Gesamtfeld einsortiert, indem es mit den ersten Elementen des Teilfeldes verglichen wird und dann an der entsprechenden Stelle eingefügt wird. Hierzu müssen alle folgenden Elemente vorher um einen Platz nach hinten verschoben werden. Dabei wächst das Teilfeld jeweils um ein Element. Dies geschieht solange, bis das Teilfeld der größe des Gesamtfeldes entspricht. Am Anfang ist das Teilfeld nur ein Element gross und beinhaltet nur das erste Element.

• Erstellen Sie ausgehend von den Beschreibungen das Nassi-Shneiderman-Diagramm für Ihren Algorithmus.
• Lassen Sie sich das erstellte Diagramm von Ihrem Tutor bestätigen.
• Implementieren Sie nun den Algorithmus in einer Funktion in Matlab.

 

Lösung:

Insertionsort

function Y=insertionSort(X)
n=length(X);

for ii = 1:n
zw = X(ii);
jj = 1;

while X(jj) < X(ii)
jj = jj+1;
end

for kk = ii:-1:jj+1
X(kk) = X(kk-1);
end

X(jj) = zw;
end
Y=X;