Η μέθοδος αυτή εισάγει ένα-ένα τα στοιχεία του συνόλου που εξετάζεται στη σωστή τους θέση. Στη φάση i:
- υποθέτουμε ότι ο πίνακας
Α[1..(i-1)]είναι ταξινομημένος, - εισάγουμε το στοιχείο
A[i]στην ακολουθίαΑ[1..(i-1)]στη σωστή θέση. Αυτό επιτυγχάνεται μετακινώντας όλα τα στοιχεία που είναι μεγαλύτερα τουA[i]μία θέση δεξιά.
Κώδικας
Ο κώδικας που υλοποιεί τον αλγόριθμο δίνεται με μορφή διαδικασίας για τη ΓΛΩΣΣΑ και την C. Παράμετρος είναι ο πίνακας που θα ταξινομηθεί και το πλήθος των στοιχείων του.
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: Α[n], Ι, J. KEY
ΑΡΧΗ
ΓΙΑ Ι ΑΠΟ 2 ΜΕΧΡΙ n
KEY=A[I] ! στοιχείο εισαγωγής
J = I-1 ! δεξί άκρο ταξινομημένης ακολουθίας
ΟΣΟ J>0 ΚΑΙ KEY<A[J] ΕΠΑΝΑΛΑΒΕ
Α[J+1] = A[J] ! μετακίνηση στοιχείου δεξιά
J <- J-1 ! μετακίνηση στο αμέσως αριστερά στοιχείο
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Α[J+1] = KEY;
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
Οι πίνακες στην C ξεκινούν από το στοιχεί 0 και φτάνουν στο n-1. Αυτό επιβάλει μερικές μικρές αλλαγές στον αλγόριθμο τόσο στο for όσο και στο while.
for (i=1; i<n; i++) {
key = A[i]; /* στοιχείο εισαγωγής */
j = i-1; /* δεξί άκρο ταξινομημένης ακολουθίας */
while (j >= 0) and (key < A[j]) {
A[j+1] = A[j]; /* μετακίνηση στοιχείου δεξιά */
j--; /* μετακίνηση στο αμέσως αριστερά στοιχείο */
}
A[j+1] = key;
}
return;
}
Ορθότητα
Τα στοιχεία του πίνακα Α[1..(i-1)] είναι ταξινομημένα. Το πρώτο στοιχείο της μη ταξινομημένης ακολουθίας Α[i..n], δηλαδή το Α[i] ελέγχεται με όλα τα στοιχεία του πίνακα Α[1..(i-1)] ξεκινώντας από το i-1 μέχρι να βρεθεί κάποιο μικρότερό του. Κάθε φορά που βρίσκεται ένα στοιχείο μεγαλύτερο του A[i] αυτό μετακινείται στην αμέσως μεγαλύτερη θέση.
Έστω ότι το A[k] (1<k<i-1) είναι μικρότερο του A[i]. Όταν βρεθεί ήδη όλα τα στοιχεία A[k+1..i-1] έχουν μετακινηθεί στην αμέσως μεγαλύτερη θέση τους, και το Α[i] τοποθετείται στη θέση A[k+1], οπότε τα στοιχεία Α[1..i] του πίνακα είναι ταξινομημένα.
Στην περίπτωση που δε βρεθεί στοιχείο μικρότερο του Α[i] τότε έχουμε φτάσει στην αρχή του πίνακα και το Α[i] τοποθετείται στη θέση A[1], ήδη όμως όλα τα στοιχεία Α[2..(i-1)] έχουν μετακινηθεί στην αμέσως μεγαλύτερη θέση τους, οπότε τα στοιχεία Α[1..i] του πίνακα είναι ταξινομημένα.
Μέσω του βρόχου while γίνεται η σύγκριση του Α[i] με τα στοιχεία Α[1..(i-1)]. Ο βρόχος τερματίζει πάντα όπως περιγράφηκε παραπάνω.
Ο βρόχος for εξασφαλίζει ότι ελέγχονται όλα τα στοιχεία του πίνακα και τερματίζει όταν το i=n, οπότε όλα τα στοιχεία του πίνακα Α[1..n] είναι ταξινομημένα.
Χρονική Πολυπλοκότητα
Ο αλγόριθμος έχει δύο βρόχους εμφολιασμένους. Ο εσωτερικός βρόχος while, θεωρούμε ότι εκτελείται για κάθε i, άρα εκτελείται για i=2 μία φορά, για i=3 δύο φορές και για i=n, n-1 φορές, συνολικά n(n-1)/2 φορές.
Ο βρόχος for εκτελείται n φορές.
Ο συνολικός χρόνος για τον αλγόριθμο είναι:
Ο μεγαλύτερος όρος είναι ο n2, άρα ο αλγόριθμος είναι τετραγωνικής πολυπλοκότητας Ο(n2).
Περίπτωση αρχικού ταξινομημένου πίνακα
Σε περίπτωση που ο πίνακας Α είναι ήδη ταξινομημένος η εντολή while δεν εκτελείται ποτέ γιατί πάντα key > A[j] (ή αλλιώς Α[i] > A[i-1] αφού key=A[i] και j=i-1) και η συνθήκη στο while είναι πάντα ψευδής. Σ' αυτή την περίπτωση η συνεισφορά της while είναι σταθερής πολυπλοκότητας. Τελικά έχουμε έναν εξωτερικό βρόχο ο οποίος εκτελείται n φορές και ο συνολικός χρόνος είναι T(n)=n. Οπότε, σ' αυτή την περίπτωση ο αλγόριθμος είναι γραμμικής πολυπλοκότητας O(n).
Χωρική Πολυπλοκότητα
Ο αλγόριθμος χρησιμοποιεί έναν πίνακα με n στοιχεία και τρεις μεταβλητές, την i, την j και την key. Αυτές οι μεταβλητές καταλαμβάνουν από μία θέση μνήμης η κάθε μία. Οπότε, συνολικά η θέσεις μνήμης που χρησιμοποιεί ο αλγόριθμος είναι:
S(n)=n+3
Η χωρική πολυπλοκότητα καθορίζεται από τον μεγαλύτερο όρο της εξίσωσης ο οποίος είναι ο n, δηλαδή, ο αλγόριθμος έχει γραμμική χωρική πολυπλοκότητα O(n).