Sortarea prin insertie

Sortarea prin insertie

Aceasta metoda este larg utilizata de jucatorii de carti.

Elementele (cartile) sunt in mod conceptual divizate intr-o secventa destinatie a₁a_i-1 si intr-o secventa sursa a_i.a_n.

In fiecare pas incepand cu i = 2 , elementul i al tabloului (care este de fapt primul element al secventei sursa), este luat si transferat in secventa destinatie prin inserarea sa la locul potrivit.

Se incrementeaza i si se reia ciclul.

Astfel la inceput se sorteaza primele doua elemente, apoi primele trei elemente si asa mai departe.

Se face precizarea ca in pasul i, primele i-l elemente sunt deja sortate, astfel incat sortarea consta numai in a insera elementul a[i] la locul potrivit intr-o secventa deja sortata.

Analiza sortarii prin insertie

In cadrul celui de-al i-lea ciclu FOR, numarul C_i al comparatiilor de chei executate in bucla WHILE, depinde de ordinea initiala a cheilor, fiind:

Cel putin ^{1 (secventa ordonata)},

Cel mult ^{i-l (secventa ordonata invers)}

In medie ^i/2, presupunand ca toate permutarile celor n chei sunt egal posibile

Intrucat avem ^n-1 reluari ale lui FOR pentru ^{i:= 2..n} , parametrul C are valorile precizate in [3.2.1.c].

[3.2.1.c]

Numarul maxim de atribuiri de elemente in cadrul unui ciclu FOR este C _i + 3 si corespunde numarului maxim de comparatii

Chiar pentru numarul minim de comparatii de chei (C _i egal cu 1) cele trei atribuiri raman valabile.

In consecinta, parametrul M ia urmatoarele valori [3.2.1.d].

[3.2.1.d]

// Sortarea prin insertie - varianta C

insertie(int a[],int n)

a[j-1]=a[n];

}

// sortarea prin insertie in situ

Insert_sort1(char *s, int n)

S[j+1]=t;