Metode de sortare

Metodele de sortare sunt:

1. Sortarea prin comparare
2.Sortarea prin aflarea minimului
3. Sortarea prin numărare
4. Sortarea prin inserție directă
5. Sortarea prin inserție binară

1.Sortarea prin comparare (metoda bulelor)

Se parcurge vectorul atât timp cât mai există o pereche (a[i],a[i+1]) cu a[i] > a[i+1] (adică o pereche de numere astfel încât primul să fie mai mare ca cel de-al doilea). Se observă că după prima parcurgere elementul maximal al şirului, dacă deja nu se află pe ultima poziţie, se va deplasa către aceasta.

Metode de sortare
Exemplu:

Date de intrare: n = 8 8 7 6 5 4 3 2 1
Date de iesire: Tabloul ordonat crescator: 1 2 3 4 5 6 7 8

Metode de sortare

#include

int a[100],n,i;
void bubble_sort(int a[100], int n) // a – tabloul de numere intregi care se va ordona crescator // n – numarul de elemente al tabloului
{
int i,aux,inv; // variabila inv este 0 atunci cand s-a facut o interschimbare
do{
inv=1;
for(i=1; i a[i+1] )
{
aux = a[i];
a[i] = a[i+1];
a[i+1] = aux;
inv = 0; }
}while( !inv );
return;
}

int main(void) {
cout<>n;
cout<<“Dati elementele tablourile \n”;
for(i=1; i<=n; i++) {
cout<<“a[“<<i<>a[i];
}
bubble_sort(a,n);
cout<<“Tabloul ordonat crescator \n”;
for(i=1; i<=n; i++)
cout<<a[i]<<” “;
}

2. Sortarea prin aflarea minimului
La fiecare pas să se determine poziţia i a celui mai mic element al secventei a[i+1], a[i+2], . . . , a[n-1].
Este asemănătoare cu cea anterioară:
• la prima parcurgere valoarea minimală se deplasează către prima poziţie
• la a doua parcurgere următorul element ca valoare va ocupa a doua poziţie, etc.
Exemplu:

Date de intrare: n = 5 1 10 7 -2 3
Date de iesire: Tabloul ordonat crescator: -2 1 3 7 10

Program:

#include int a[100], n, i;

void min_sort(int a[100], int n) // a – tabloul de numere intregi care se va ordona crescator // n -numarul de elemente al tabloului {
int i, aux, j;
for(i=1; i<=n-1; i++)
for(j=i+1; j a[j] )
{
aux = a[i];
a[i] = a[j];
a[j] = aux;
}
return;
}
int main(void) {
cout<>n; cout<<“Dati elementele tablourile \n”;
for(i=1; i<=n; i++) {
cout<<“a[“<<i<>a[i];
} min_sort(a, n);
cout<<“Tabloul ordonat crescator \n”;
for(i=1; i<=n; i++)
cout<<a[i]<<” “;
}

3. Sortarea prin numărare

Se foloseşte un vector auxiliar b unde în b[i] se păstrează numărul de elemente din vectorul a care sunt mai mici ca a[i].
Pentru a nu număra de două ori acelaşi element se folosesc două for-uri cu indicii de la 1 la n-1 respectiv i+1, . . . , n. Apoi fiecărui element a[i] îi va corespunde poziţia b[i] în vectorul c.

Exemplu:

Date de intrare: n = 7 -4 23 1 10 7 -2 3
Date de iesire: Tabloul ordonat crescator: -4 -2 1 3 7 10 23

Vrem să sortăm urmatorul şir: A= (9, -5, 2, 12, 4) Elementele lui A le atribuim lui B: B= (9, -5, 2, 12, 4) Pentru fiecare element A[i] numărăm câte elemente sunt mai mici ca el, aceste numere reţinându-le în vectorul C: C=(3, 0, 1, 4, 2) se reconstituie vectorul A astfel: A[C[1]+1]=B[1]; A[C[2]+1]=B[2]… obţinându-se vectorul A sortat (-5, 2, 4, 9, 12)

#include int a[100], n, i;

void numarare(int a[100], int n) // a – tabloul de numere intregi care se va ordona crescator // n – numarul de elemente al tabloului {
int i, j, b[100], c[100], x;
for(i=1; i<=n; i++) b[i]=0;

for(i=1; i<=n-1; i++)
for(j=i+1; j<=n; j++)
if( a[i] < a[j] ) b[j] = b[j]+1;
else b[i] = b[i]+1; for(i=1; i<=n; i++) {
x=b[i];
c[x]=a[i]; // sau c[b[i]]=a[i];
}
for(i=1; i<=n; i++)
a[i] = c[i];
return;
}

int main(void) {
cout<>n; cout<<“Dati elementele tablourile \n”;
for(i=1; i<=n; i++) {
cout<<“a[“<<i<>a[i];
}
numarare(a, n);
cout<<“Tabloul ordonat crescator \n”;
for(i=1; i<=n; i++)
cout<<a[i]<<” “;
}

 

4. Sortarea prin inserţie directă
Sortarea prin inserţie directă se bazează pe următoarea metodă:
Fie un vector a de n numere.

• Elementul aflat pe poziţia a[2] se compară cu a[1]
şi încercăm să găsim poziţia în care ar trebui să se
introducă.

• Dacă a[2]<a[1] atunci a[2] trebuie să fie înainte,
deci îl mutăm pe a[1] pe poziţia următoare.

• La un pas j avem vectorul sortat a[1],…,a[j-1] şi încercăm să-l inserăm pe a[j] astfel încât să păstrăm vectorul ordonat între 1 şi j-1.

• Pentru aceasta, se compară succesiv a[j] cu elementele a[j-1], a[j-2], …, a[1] (în această ordine), mutând elementul de la poziţia curentă cu o poziţie la dreapta atunci când a[i]>a[j].

• Când a[i]<=a[j] procesul de inserţie se opreşte, poziţia la care se realizează inserarea fiind i+1.

Rezumatul metodei de sortare prin insertie directa:

• Se compară primul element cu toate elementele care urmează după el.

• Dacă găsim un element mai mic decât primul atunci le interschimbăm pe cele două.

• Apoi continuăm cu al doilea element al şirului, pe care, de asemenea îl comparăm cu toate elementele care urmează după el şi în caz de inversiune interschimbăm cele două elemente.

• Apoi procedăm la fel cu al treilea element al şirului, iar procesul continuă astfel până la penultimul element al şirului care va fi comparat cu ultimul element din şir.

Exemplu:

Date de intrare: n = 10 10 9 8 7 6 5 4 3 2 1

Date de iesire:

Tabloul ordonat crescator: 1 2 3 4 5 6 7 8 9 10

Program:

#include int a[100], n, i;

void inserare(int a[100], int n) // a – tabloul de numere intregi care se va ordona crescator // n – numarul de elemente al tabloului {

int i, j, x;

for(i=2; i<=n; i++) {

x = a[i]; j = i-1;

while( j >= 1 && a[j] > x ) {

a[j+1] = a[j];

j–;

}

a[j+1] = x;

}

return;

}

int main(void) {

cout<<“Dati dimensiunea tabloului n = “;

cin>>n;

cout<<“Dati elementele tablourile \n”;

for(i=1; i<=n; i++) {

cout<<“a[“<<i<<“] ==”” “;=”” cin=””>>a[i];

}

inserare(a, n);

cout<<“Tabloul ordonat crescator \n”;

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

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

}

5. Sortarea prin inserţie binară

Metoda de sortare prin inserţie binară se deosebeşte de cea prin inserţie directă prin modul de căutare al poziţiei de inserare:

• în metoda de inserţie directă poziţia se caută utilizând algoritmul de căutare liniară,

• aici ea se determină folosind metoda de căutare binară, mult mai eficientă. Aceasta constă în înjumătăţirea repetată a intervalului vizat până la găsirea locului căutat.

Exemplu:

Date de intrare: n = 6 1 10 7 -2 3 -23

Date de iesire:

Tabloul ordonat crescator: -23 -2 1 3 7 10

Program:

#include void insertie_binara(int a[], int n) {

int i, j, stanga, dreapta, m, aux; for(i=1;i<=n;i++) {

aux=a[i];

stanga=1;

dreapta=n;

while(stanga<=dreapta) {

m = (stanga+dreapta) / 2;

if(a[stanga]>aux) dreapta=m-1;

else

stanga=m+1;

}

for(j=i-1; j>=stanga; j–)

a[j+1]=a[j];

a[stanga]=aux;

}

}

int main () {

int i,n,a[50];

cout<<“Introduceti dimensiunea sirului: “;

cin>>n;

cout<<“Dati elementele sirului:\n”;

for(i=1;i<=n;i++) {

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

cin=””>>a[i];

}

insertie_binara(a,n);

cout <<“Sirul ordonat este: “;

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

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

}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s