VECTORIMetode de

sortare

Proiect realizat de Vicentiu Mihaela Raluca

Clasa a X-a BColegiul National “Mihai Eminescu”

Metoda Bulelor (bubblesort)

Descriere :• Parcurge vectorul de mai

multe ori pana cand il sorteaza.

• Compara fiecare element cu succesorul sau si se interchimba intre ele daca nu sunt in ordine.

• Vectorul este sortat cand la o parcurgere completa nu se efectueaza nicio interchimbare .

Program C++ :• #include <iostream.h> using namespace std; int main() { int v[100], i, n, ok,aux; cout<<"n= ";cin>>n; for(i=1;i<=n;i++) { cout<<"v["<<i<<"]=“; cin>>v[i]; } do { ok=1; for(i=1;i<=n;i++) if(v[i]>v[i+1]) { aux=v[i]; v[i]=v[i+1]; v[i+1]=aux; } } while(ok==0); cout<<"Vectorul sortat este: "; for(i=1;i<=n;i++) cout<<v[i]<<" "; return 0; }

Metoda prin insertie

DESCRIERE :

PROGRAM C++ :

Aceasta metoda aseaza elementul citit pe pozitia lui finala in vector, comparandu-l cu valorile introduse deja si interschimbandul pana ajunge in pozitia corecta.

#include <iostream.h> using namespace std; int main() { int v[100],n,i,j,aux; cout<<"n= ";cin>>n; cout<<"v[1]= ";cin>>v[1]; for(i=2;i<=n;i++) { cout<<"v["<<i<<"]= "; cin>>v[i];

j=i; while(v[j]<v[j-1] && j>1) { aux=v[j]; v[j]=v[j-1]; v[j-1]=aux; j--; } } cout<<"Vectorul sortat este: "; for(i=1;i<=n;i++) cout<<v[i]<<" "; return 0; }

Metoda directaDescriere : Program C++ :

Parcurge vectorul o singura data.

Se verifica comparand elementul de pe pozitia curenta cu toate elementele de dupa aceasta pozitie.

Unde elementele nu sunt in ordine se interchimba.

#include <iostream> using namespace std;

int main () { int v[50],n,i,j,aux; cin>>n; for(i=0;i<=n;i++) for(j=i+1;j<=n;j++) if(v[i]>v[j] && i%2==0 && j%2==0) { aux=v[i]; v[i]=v[j]; v[j]=aux; } cout<< “\n vectorul sortat:”; for(i=0;i<=n;i++) cout<<v[i]<<“ “; return 0; }

METODA DE SORTARE PRIN MINIM

DESCRIERE : PROGRAM C++ :

Aflam minimul si il ducem pe ultima pozitie a vectorului prin comparare si interchimbare in caz de dezordine.

Procedeul se repeta pentru fiecare element .

#include <iostream.h> using namespace std; int main() { int v[100],i,n,min,k,aux,j; cout<<"n= ";cin>>n; for(i=1;i<=n;i++) { cout<<"v["<<i<<"]= “; cin>>v[i[; } for(i=1;i<=n-1;i++) { min=v[i]; k=i; for(j=i+1;j<=n;j++) if(v[j]<min) { min=v[j]; k=j; } aux=v[i]; v[i]=v[k]; v[k]=aux; } cout<<"Vectorul sortat este: "; for(i=1;i<=n;i++) cout<<v[i]<<" "; return 0; }

Metoda inserarii

Descriere :

Programul C++ :

Se folosesc 2 vectori: vectorul sursa: a (nesortat) si vectorul destinatie : b (sortat).

Elementele vectorului sursa se copiaza in vectorul destinatie prin inserare in pozitia corespunzatoare ,astfel incat in vectorul destinatie sa fie respectara relatia de ordine.

#include <iostream> using namespace std; int main () {int I,j,n,k,a[50],b[50]; cout<<“n=“; cin>>n; for(i=0;i<=n;i++) {cout<<“a[“<<i<<“]= “; cin>>a[i];} b[0]=a[0]; for(i=1;i<n;i++) {j=0; while (j<=i-1&& a[i]>b[j]) j++; for( k=I;k>j+1;k--) b[k]=b[k-1]; b[j]=a[i]; } for(i=0;i<=n;i++) cout<<b[i]<<“ “; return 0; }

Descriere :

*Vectorul se imparte in 2 subvectori : subvectorul sursa: a[i] si subvectorul destinatie: a[0].

*Elementul a[i] sin subvectorul sursa este inserat in subvectorul destinatie conform relatiei de ordine , astfel vectorul destinatie va fi mereu un vector ordonat .

Program C++ :

* #include <iostream>

using namespace std;

int main ()

{int i,j,n,aux,a[50];

cout<<“n=“; cin>>n;

for(i=0;i<n;i++)

{ cout<<“a[“<<i+1<<“]= “;

cin>>a[i];}

for(i=0;i<n;i++)

{aux=a[i];

j=i-1;

while (j>0 && aux<a[j])

{a[j+1]=a[j]; j--;}

if(aux>a[j]) a[j+1]=aux;

else {a[1]=a[0]; a[0]=aux;}

}

for(i=0;i<=n;i++)

cout<<a[i]<< “ “ ;

return 0; }

*Metoda inserarii directe

Metoda inserarii rapide Descriere :

• Vectorul se imparte in doi subvectori : subvectorul sursa si subvectorul destinatie (ordonat).

• Pozitia elementului a[i] va fi gasita cu prin algoritmul de cautare binara.

• Subvectorul destinatie este impartit in doi subvectori se examineaza relatie de ordine dintre mijloc si vectorul a[i] si se stabileste daca vectorul se insereaza in prima sau a doua jumatate . Operatia de divizare a subvectorului continua pana se gaseste pozitia in care urmeaza sa fie inseray a[i].

Program C++ :• #include <iostream>

using namespace std;

int main ()

{int i,j,n,aux,st,dr,mijl,a[50];

cout<<“n=“; cin>>n;

for(i=0;i<n;i++)

{ cout<<“a[“<<i+1<<“]= “;cin>>a[i];}

for(i=0;i<n;i++)

{aux=a[i]; st=0; dr=i-1;

while (st<=dr)

{mijl=(st+dr)/2;

if (aux<a[mijl]) dr=mijl-1;

else st=mijl+1;}

j=i-1;

while (j>=st) {a[j+1]=a[j]; j=j-1;}

a[st]=aux;

}

for(i=0;i<‘;i++) cout<<a[i]<< “ “ ;

return 0; }

Thanks for watching !!!