Seite 1 von 1

FOO::InsertionSort

Verfasst: 20. Sep 2015 18:22
von sch3rvv1n
Hallo allerseits,

Ich bin der Meinung dass der in FOO implementierte InsertionSort anders funktioniert als er wirklich funktionieren soll. Normalerweise soll das i. Element bei jeder Iteration gewählt werden und falls dieses Element größer als das nächstes Element ist, muss dieses mit dem Nächsten getauscht werde. Also das i. Element wird gegebenenfalls um eine Position nach rechts und das i+1. Element um 1 nach links verschoben. Danach wird das nach links verschobene Element mit vorherigen Elementen(Also Die Elemente die kleiner als i. Position stehen) verglichen und gegebenenfalls miteinander vertauscht.
Z.B. :
4 5 2 5 7 3 2
Nach der 2. Iteration:
2 4 5 5 7 3 2

Aber der im Foo implementierte Algorithmus sucht zunächst das größte Element bei jeder Iteration und schiebt er dann ans Ende der List und die Elemente die danach stehen werden um eine Position nach Links verschoben. (Ich hoffe, ich habe es nicht falsch verstanden).
Z.B. :
4 5 2 5 7 3 2
nach der 2. Iteration:
4 2 5 3 2 5 7

Ich glaube dass der Algorithmus so aussehen soll:

void insertionSort(int E[]) {
int i,j;
for (i = 1; i < E.length; i++) {
int temp = E;
for (j = i; j > 0 && E[j-1] > temp; j--) {
E[j] = E[j-1];
}
E[j] = temp;
}
}