Algoritmul de sortare prin inserție

Analiza:

Sortarea - prin sortarea elementelor unei multimi a[1], a[2]... a[n-1] vom intelege rearanjarea elementelor intr-o ordine specificata de utilizator cu scopul de a facilita cautarea unui element dat.

Sortarea este o etapa fundamentala, cu caracter universal. Intr-o carte de telefoane, intr-un dictionar, in orice activitate in care se impune un anumit obiect, sortarea este prezenta. In cele ce urmeaza vom presupune ca elementele de sortat au structura:

struct element

{

int cheie;

[alte campuri;]

}

Campul cheie este cel mai important intrucat vom defini sortarea ca o permutare a elementelor a[k0], a[k1]... a[k(n-1)] astfel incat secventa cheilor elementelor din aceasta permutare sa fie monoton crescatoare (descrescatoare). Acest camp cheie din structura elementului e o valoare care il identifica in mod unic in cadrul structurii. Campul cheie l-am ales intreg pentru usurinta exprimarii, dar el poate fi orice data scalara.

Metodele de sortare pot fi impartite in doua mari categorii: interna (elementele sunt memorate in memoria interna) si externa (elementele sunt memorate in memoria externa). In primul caz presupunem ca elementele colectiei de date sunt memorate intr-un tablou (sort. tablourilor), iar in al doilea caz, intr-un fisier secvential (sort. fisierelor).

Sortarea tablourilor:

a[0] a[1] a[2] a[3] ...................... a[n-1]

A

Eficienta: memorie minima si timp de executie minim.

Intrucat elementele sunt memorate in memoria centrala, trebuie sa avem cel putin atatea locatii de memorie...

Deci ne vor interesa doar acei algoritmi de sortare care realizeaza sortarea elementelor ...

Rezulta ca vom clasifica algoritmii de sortare dupa tipul necesar.

Aprecierea cantitativa a unui algoritm de sortare se realizeaza cu ajutorul a doi parametrii specifici. Vom contoriza cmed (nr. de comparari) si mmed (nr. de mutari).

Tema1: Sortarea tablourilor. Algoritmul de sortare prin insertie.

Fie A=(35, 64, 12, 22, 83, 4, 67). Sa se ordoneze crescator elementele tabloului.

pas 1: i=1

35<64 => A=(35, 64, 12, 22, 83, 4, 67)

pas 2: i=2

a[1]>a[2] trec la elementul urmator

a[0]>a[2] trec la elementul urmator

k=j=-1 => k+1 loc de inserat

aux=a[2]

A=(35, 35, 64, 22, 83, 4, 67)

A=(12, 35, 64, 22, 83, 4, 67)

pas 3: - plasez elementul a[i] la locul sau in secventa destinatie

caut locul de inserat pentru a[i]

- k=j, k+1 este locul de inserat

- aux=a[i]

- mut a[k+1]...a[i-1] spre dreapta cu o pozitie

A=(12, 35, 35, 64, 83, 4, 67)

A=(12, 22, 35, 64, 83, 4, 67)

....

Elementele tabloului se considera a fi divizate in a[0] ... a[i-1] (destinatia) si a[i]...a[n-1] (sursa).

Algoritmul de sortare prin insertie presupune la fiecare pas al algoritmului, incepand cu i=1 cu pasul 1, plasarea elementului a[i] de la locul sursa in locul sau la destinatie.