SortSortăriări

LectLect. Univ. Dr. Nisioiu Codrin. Univ. Dr. Nisioiu Codrin--FlorentinFlorentin

Sortarea prin interschimbareSortarea prin interschimbare

Se compară 2 câte 2 elemente Se compară 2 câte 2 elemente consecutive ale vectorului, consecutive ale vectorului, interschimbându-le în cazul interschimbându-le în cazul neîndeplinirii criteriului de ordonareneîndeplinirii criteriului de ordonare

S1S1::

DO-FOR i=0,n-1,1DO-FOR i=0,n-1,1

IF (IF (xx[i]>x[i+1]) THEN {aux<-x[i];x[i]<-[i]>x[i+1]) THEN {aux<-x[i];x[i]<-x[i+1];x[i+1]<-aux;}x[i+1];x[i+1]<-aux;}

ENDIFENDIF

ENDDOENDDO

Sortarea prin interschimbareSortarea prin interschimbare

ddupupă o parcurgere integrală a vectorului ă o parcurgere integrală a vectorului procesul se reiaprocesul se reia începând cu primul element începând cu primul element S2:S2:p<-1p<-1WHILE(p) DO{p<-0;S1’}WHILE(p) DO{p<-0;S1’}ENDWHILEENDWHILES1’ – S1 la care se adaugS1’ – S1 la care se adaugă după ă după inteinterrschimbare pschimbare p=1=1

Elementele cu valoare mică sunt Elementele cu valoare mică sunt ““împinseîmpinse”” către începutul vectoruluicătre începutul vectorului

Procesul se opreşte când la o parcurgere a Procesul se opreşte când la o parcurgere a vectorului nu s-a produs nici o vectorului nu s-a produs nici o interschimbare, situaţie ce va fi indicată de o interschimbare, situaţie ce va fi indicată de o variabilă pvariabilă p->->p=0p=0

PseudocodPseudocod

ÎNTREG ÎNTREG i, i, nn, p;REAL x[50],aux;, p;REAL x[50],aux;SCRIE(“IntroduceSCRIE(“Introduceţi dimensiunea ţi dimensiunea

vectorului, nvectorului, n=”);=”);CITECITEŞTEŞTE(n);(n);DO-FOR i=0,n,1DO-FOR i=0,n,1

SCRIE(“x[i]=”,i);CITESCRIE(“x[i]=”,i);CITEŞTEŞTE(x[i]);(x[i]);ENDDOENDDOS2S2DO-FOR i=0,n,1 SCRIE(x[i]);DO-FOR i=0,n,1 SCRIE(x[i]);ENDDOENDDO

Sortarea prin selecSortarea prin selecţieţie

Metoda presupune determinarea Metoda presupune determinarea elementului minim din vector şi elementului minim din vector şi aducerea lui pe prima poziţie, aducerea lui pe prima poziţie, după care se determină minimul după care se determină minimul din vectorul rămas şi aducerea lui din vectorul rămas şi aducerea lui pe a doua poziţie, etc.pe a doua poziţie, etc.

Sortarea prin selecSortarea prin selecţieţie

Minimul se poate determina comparând un Minimul se poate determina comparând un element al vectorului element al vectorului cu toate care îl cu toate care îl succed, interschimbându-le în cazul succed, interschimbându-le în cazul neîndeplinirii criteriului de ordonareneîndeplinirii criteriului de ordonareS1S1::

DO-FOR i=0,n-1,1DO-FOR i=0,n-1,1DO-FOR DO-FOR j=i+1,j=i+1,n,1n,1

IF (x[i]>x[j]) THEN {aux<-x[i];x[i]<- IF (x[i]>x[j]) THEN {aux<-x[i];x[i]<- x[j];x[j]<-aux;}x[j];x[j]<-aux;}

ENDIFENDIF ENDDOENDDOENDDOENDDO

PseudocodPseudocod

ÎNTREG ÎNTREG i, i, nn;REAL x[50],aux;;REAL x[50],aux;

SCRIE(“IntroduceSCRIE(“Introduceţi dimensiunea ţi dimensiunea vectorului, nvectorului, n=”);CITE=”);CITEŞTEŞTE(n);(n);

DO-FOR i=0,n,1DO-FOR i=0,n,1

SCRIE(“x[i]=”,i);CITESCRIE(“x[i]=”,i);CITEŞTEŞTE(x[i]);(x[i]);

ENDDOENDDO

S1S1

DO-FOR i=0,n,1 SCRIE(x[i]);DO-FOR i=0,n,1 SCRIE(x[i]);

ENDDOENDDO

Sortarea prin inserSortarea prin inserţieţie

IpotezăIpoteză: la pasul i elementele : la pasul i elementele predecesoare lui x[i] sunt predecesoare lui x[i] sunt ordonateordonate, , se determinse determină poziţia ă poziţia poz în care valoarea lui xpoz în care valoarea lui x[i] se [i] se încadrează conform criteriului de încadrează conform criteriului de ordonareordonareS1:S1:

IF (x[i]<x[j]) THEN poz <- j;IF (x[i]<x[j]) THEN poz <- j; ELSE j=j+1;ELSE j=j+1;

ENDIFENDIF

Sortarea prin inserSortarea prin inserţieţie

SS2: 2:

poz <- -1;j<-0;poz <- -1;j<-0;

DO DO

S1S1

UNTIL (j>i) UNTIL (j>i) ŞŞII (poz diferit de -1)(poz diferit de -1)

ENDDOENDDO

Sortarea prin inserSortarea prin inserţieţie

Elementul x[i] va fi inserat Elementul x[i] va fi inserat în în aceea poziţie, după ce toate aceea poziţie, după ce toate elementele vectorului, începând elementele vectorului, începând cu poz şi până la sfârşit, glisează cu poz şi până la sfârşit, glisează cu o poziţie la dreaptacu o poziţie la dreaptaS3:S3:

DO-FOR kDO-FOR k=i,poz,-1=i,poz,-1 x[k]<-x[k-1];x[k]<-x[k-1]; ENDDOENDDO X[poz]<- aux;X[poz]<- aux;

PseudocodPseudocod

ÎNTREG ÎNTREG i, i, n, poz, j, kn, poz, j, k;;REAL x[50],aux;REAL x[50],aux;SCRIE(“IntroduceSCRIE(“Introduceţi dimensiunea vectorului, ţi dimensiunea vectorului,

nn=”);CITE=”);CITEŞTEŞTE(n);(n);DO-FOR i=0,n,1DO-FOR i=0,n,1

SCRIE(“x[i]=”,i);CITESCRIE(“x[i]=”,i);CITEŞTEŞTE(x[i]);(x[i]);ENDDOENDDODO-FOR i=DO-FOR i=11,n,1,n,1 IF (x[i]<x[IF (x[i]<x[i-1i-1]) THEN]) THEN SS22 aux < - x[i];aux < - x[i]; S3S3 ENDIFENDIFENDDOENDDODO-FOR i=0,n,1 SCRIE(x[i]);DO-FOR i=0,n,1 SCRIE(x[i]);ENDDOENDDO

Interclasarea a 2 vectori de Interclasarea a 2 vectori de dimensiuni diferitedimensiuni diferite

Interclasare = procesul de Interclasare = procesul de obobţinere ţinere din 2 sau mai multe din 2 sau mai multe mulţimi ordonatemulţimi ordonate, a unei , a unei mulţimi ordonate după acelaşi mulţimi ordonate după acelaşi criteriu.criteriu.

Interclasarea a 2 vectori de Interclasarea a 2 vectori de dimensiuni diferite(m,n)dimensiuni diferite(m,n)

Metoda presupune compararea a 2 Metoda presupune compararea a 2 elemente, câte unul din fiecare vector iniţial elemente, câte unul din fiecare vector iniţial cu scrierea celui mai mic dintre ele în vectorul cu scrierea celui mai mic dintre ele în vectorul rezultat şi trecerea la următorul element al rezultat şi trecerea la următorul element al vectorului iniţial din care s-a preluat.vectorului iniţial din care s-a preluat.Procesul Procesul de comparare se de comparare se încheie când s-a epuizat încheie când s-a epuizat unul din vectorii iniţiali.unul din vectorii iniţiali.

S1S1::i<-0;j<-0;p<-0;i<-0;j<-0;p<-0;WHILE (WHILE ((i<m) (i<m) ŞI ŞI (j<n)(j<n)) DO) DOIF (x[i]<y[j]) THEN {z[p]<-x[i];p<-p+1;i<-i+1;}IF (x[i]<y[j]) THEN {z[p]<-x[i];p<-p+1;i<-i+1;} ELSE {z[p]<-y[j];p<-p+1;j<-j+1;}ELSE {z[p]<-y[j];p<-p+1;j<-j+1;}ENDIFENDIFENDWHILEENDWHILE

Interclasarea a 2 vectori de Interclasarea a 2 vectori de dimensiuni diferite(m,n)dimensiuni diferite(m,n)

Elementele netransferate aleElementele netransferate ale celuilaceluilallt t vector iniţial se copiază în vectorul vector iniţial se copiază în vectorul rezultat.rezultat.

S2S2::

IF (i este m) THEN IF (i este m) THEN

DO-FOR i=j,n,1 z[p]<-y[i];p<- p+1;DO-FOR i=j,n,1 z[p]<-y[i];p<- p+1;

ENDDOENDDO

ELSE ELSE

DO-FOR j=i,m,1 z[p]<-x[j];p<- p+1;DO-FOR j=i,m,1 z[p]<-x[j];p<- p+1;

ENDDO ENDIFENDDO ENDIF

PseudocodPseudocod

ÎNTREG ÎNTREG i, i, n,n, j,j,m, p;m, p;REAL x[50], y[100], z[150];REAL x[50], y[100], z[150];SCRIE(“IntroduceSCRIE(“Introduceţi dimensiunea ţi dimensiunea primului primului vectorului, vectorului,

m=”);CITEm=”);CITEŞTEŞTE(m);(m);DO-FOR i=0,m,1DO-FOR i=0,m,1

SCRIE(“x[i]=”,i);CITESCRIE(“x[i]=”,i);CITEŞTEŞTE(x[i]);(x[i]);ENDDOENDDOSCRIE(“IntroduceSCRIE(“Introduceţi dimensiuneaţi dimensiunea vectoruluivectorului 2 2, ,

n=”);CITEn=”);CITEŞTEŞTE(n);(n);DO-FOR j=0,n,1DO-FOR j=0,n,1

SCRIE(“y[j]=”,j);CITESCRIE(“y[j]=”,j);CITEŞTEŞTE(y[j]);(y[j]);ENDDOENDDOS1S1S2S2DO-FOR i=0,p,1 SCRIE(z[i]);DO-FOR i=0,p,1 SCRIE(z[i]);ENDDOENDDO