Insertion Sort

Η λογική του αλγορίθμου είναι η ακόλουθη:

θεωρούμε ότι στα j πρώτα περάσματα του αλγορίθμου (j>=2) έχουμε ήδη ταξινομήσει το

τμήμα S[0..j] του πίνακα. Στην συνέχεια διαβάζουμε το στοιχείο

S[j+1] και σαρώνουμε το ταξινομημένο τμήμα S[1..j] μέχρι να

βρούμε την κατάλληλη θέση στην οποία πρέπει να τοποθετηθεί το S[j+1],

έστω S[k]. Όταν γίνει αυτό πρέπει να μετακινήσουμε όλα

τα στοιχεία S[k],..,S[k+1] μια θέση δεξιά, για να κάνουμε χώρο για το S[j+1].

Τώρα έχει ταξινομηθεί το τμήμα S[1..(j+1)].

Επαναλαμβάνουμε την ίδια διαδικασία μλεχρι να ταξινομηθεί πλήρως ο πίνακας.


for(j=2;j<"n;j++){

var key = S[j];

var i = j-1;

while(i>0 && key <"S[i] ){

S[i+1] = S[i];

i=i-1;

}

S[i+1] = key;

}