Sortarea prin inserție

Sortarea prin inserție (Insertion Sort) se bazează pe următoarea idee:

• fie un vector X[] cu n elemente;
• dacă secvența cu indici 0, 1, …, i-1 este ordonată, atunci putem insera elementul X[i] în această secvență astfel încât să fie ordonată secvența cu indici 0, 1, …, i-1, i.
• luăm pe rând fiecare element X[i] și îl inserăm în secvența din stânga sa
• la final întreg vectorul va fi ordonat

Algoritm

O reprezentare a algoritmului este:

• parcurgem vectorul cu indicele i
  • inserăm pe X[i] în secvența din stânga sa; pentru inserare se mută unele elemente din secvență spre dreapta

Exemplu

Să ordonăm următorul vector, în care n=5:

sortarea prin inserție presupune următoarele transformări ale vectorului:

Secvență C++

În secvențele următoare considerăm că tabloul are elementele indexate de la 0 la n-1:

int n, X[100];
//citire X[] cu n elemente
for(int i = 1 ; i < n ; i ++)
{
    int aux = X[i];
    int p = i - 1;
    while(p >= 0 && X[p] > x)
        X[p + 1] = X[p], p --;
    X[p + 1] = aux;
}

sau:

for(int i = 1 ; i < n ; i ++)
{
    int p = i;
    while(p > 0 && X[p] < X[p-1])
    {
        int aux = X[p];
        X[p] = X[p-1];
        X[p-1] = aux;
        p --;
    }
}

Resurse online

Insertion Sort pe Wikipedia

Animație pas cu pas

Animație, valori configurabile

Animație, mai multe metode de sortare

Animație

Un filmuleț care ilustrează Sortarea prin inserție, creat la Târgu Mureș: