Sortari interne - caracteristici generale - algoritmii

Sortari interne - caracteristici generale - algoritmii

in aceleasi locatii (nr. minim de locatii suplimentare)

operatia de baza - compararea cheilor

Sortari interne - algoritmii

S. prin insertie directa

S. prin selectie directa (a min. sau max.)

S. prin interschimbare directa (BubbleSort)

Sortari interne - algoritmii

S. prin insertie directa

sortarea prin insertie cu micsorarea incrementului (ShellSort)

S. prin selectie directa (a min. sau max.)

sortarea prin selectie folosind structuri arborescente (ansamble=heap)(HeapSort)

S. prin interschimbare directa (BubbleSort)

sortarea prin interschimbare folosind partitii (QuickSort)

Sortarea prin insertie directa

pas iterativ (1): se ia componenta A[2] si se insereaza la locul ei in vectorul sortat de lungime 1, A[1], producand un vector sortat de lungime 2.

pas iterativ (i): (pasa) vectorul este impartit in doua parti: A[1], …, A[i] este sortata crescator si se numeste destinatie, iar A[i+1], …, A[n] este inca nesortata si se va numi sursa. Se ia prima componenta din sursa, A[i+1], si se cauta sa se insereze la locul ei in destinatie. Cautarea locului lui A[i+1] in destinatie se face linear, parcurgand destinatia de la dreapta la stanga si mutand pe rand cate o pozitie la dreapta componentele care sunt mai mari decat valoarea de inserat, pana cand gasim locul valorii x = A[i+1] si o inseram.

Sortarea prin insertie directa

procedure InsDir (A)

for i:= 2 to n do

x:= A[i];

j:= i- 1;

while (j > 0) and (x < A[j]) do

A[j+1]:= A[j]

j:= j- 1

endwhile

A[j+1]:= x

endfor

endproc

Sortarea prin insertie directa (cont.)

procedure InsDir1(A)  

for i:= 2 to n do

A[0]:= A[i];

j:= i-1;

while (A[0] < A[j]) do

A[j+1]:= A[j]

j:= j-1

endwhile

A[j+1]:= A[0]

endfor

endproc.

Sortarea prin insertie directa - complexitate

La fiecare pas iterativ i (cu i=1,…,n-1)  al algoritmului, cand se insereaza componenta A[i+1] la locul ei in destinatie

- notam  cu Ci numarul de comparatii efectuat (presupunem ca lucram pe variante cu componenta marcaj, deci avem cate o singura comparatie ce controleaza ciclul while care cauta locul inserarii efectuand si mutari). Ci poate atinge o valoare maxima, i+1, daca valoarea de inserat este cea mai mica si va veni pe prima componenta a sursei; poate atinge o valoare minima, si anume 1, daca valoarea de inserat este cea mai mare si pozitia ei va fi ultima din noua sursa, iar valoarea medie a lui Ci va fi i/2.

Document online: Accizele armonizate Document online: Elementele dobanzii simple si Plati esalonate anticipate - formule contabile

- notam cu Mi numarul de mutari efectuat de algoritm la pasul iterativ i, avem relatia Mi=Ci+1 intre mutari si comparatii

Sortarea prin insertie directa - complexitate

Cmin= 1 +   1 + … + 1 = n-1

pas 1 pas 2 pas n-1

Mmin= 2 +   2 + … + 2 = 2(n-1)

pas 1 pas 2 pas n-1

Sortarea prin selectie directa a minimului

pas iterativ (i): (pasa) vectorul este impartit in doua parti:

destinatia A[1..i-1] ce contine minime puse la locul lor de pasii anteriori, si

sursa A[i..n], pe care se efectueaza o pasa, adica se cauta secvential minimul din subvectorul sursa si apoi se interschimba cu componenta A[i].

dimensiunea destinatiei creste cu 1, iar a sursei scade corespunzator. Dupa n-1 pasi iterativi vectorul A va fi sortat crescator.

Sortarea prin selectie directa a minimului

procedure SelDir(A)

for i:= 1 to n-1 do

k:= i; min:= A[i]; 

for j:= i+1 to n do

if A[j] <min then

k:= j; min:= A[j]

endif

endfor

A[k]:= A[i]

A[i]:= min

endfor

endproc

Sortarea prin selectie directa - complexitate

numarul de comparatii este independent de ordinea initiala a componentelor

Sortarea prin interschimbare directa

(pasa) parcurgem vectorul de la dreapta la stanga comparand doua elemente succesive A[i-1] si A[i]; daca A[i-1] A[i] le lasam pe loc, daca A[i-1] > A[i] le interschimbam.

pas iterativ (i): vectorul este impartit in doua parti:

destinatia A[1..i-1] cela mai mici i-1 valori puse la locul lor de pasii anteriori

sursa A[i..n], pe care se efectueaza o pasa, de la dreapta spre stanga, rezultat impingerea minimului din sursa pe A[i].

dimensiunea destinatiei creste cu 1, iar a sursei scade corespunzator. Dupa n-1 pasi iterativi vectorul A va fi sortat crescator.

Sortarea prin interschimbare directa

procedure InterschDir(A)

for j:=2 to n do

for i:=n downto j do

if A[i-1] > A[i] then

interschimba (A[i-1], A[i])     

endif

endfor

endfor

endproc.

Sortarea prin interschimbare directa-modificari

- posibilitatea reducerii numarului de pasi iterativi

daca la o pasa nu se face nici o interschimbare, atunci sursa este sortata si, cum si destinatia este, inseamna ca intregul vector A este sortat si este inutil sa mai reluam pasele

- scurtarea lungimii paselor

sa tinem minte, nu numai faptul ca s-au facut efectiv interschimbari, dar si locul unde  s-a efectuat ultima interschimbare. Din acest loc, pana la destinatie, avem de-a face cu o bucata sortata, deci e suficient sa reluam pasa urmatoare de la n si pana aici. Daca ultima interschimbare s-a facut intre A[k-1] si A[k], atunci sursa pentru pasul urmator va fi A[k+1..n]. Se schimba deci si lungimea surselor

Sortarea prin interschimbare directa-complexitate

numarul de comparatii pe care-l face algoritmul la fiecare pas iterativ i este determinat de lungimea subvectorului sursa  A[i..n] pe care se face o pasa si este independent de ordinea cheilor. La pasul i algoritmul face Ci = n-1 comparatii