Algoritmi de sortare

A sorta un tablou înseamnă a rearanja elementele tabloului astfel încât între acestea să existe o relaţie de ordine (crescătoare sau descrescătoare). Un algoritm de sortare este o metodă prin care se aranjează elementele unui tablou într-o ordine precisă.

Bubble sort sau Sortare prin metoda bulelor

Exemplu: Să sortăm crescător vectorul: {5, 1, 12, 8, 16}

int main()

{

int n,i,ok;

int v[50],aux;

cout<<"n= ";

cin>>n;

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

{

cout<<"v["<<i<<"]= ";

cin>>v[i];

}

do //Se parcurge şirul de la stânga la dreapta în mod repetat,

{ //La fiecare parcurgere se verifică succesiv dacă orice două elemente vecine sunt ordonate;

ok=0;

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

if(v[i]>v[i+1]) // Dacă nu sunt ordonate ele sunt interschimbate;

{

aux=v[i];

v[i]=v[i+1];

v[i+1]=aux;

ok=1;//marcăm că s-a executat o interschimbare

}

}while(ok); // Procedeul se repetă până când se efectuează o parcurgere în care nu se execută interschimbări

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

cout<<v[i]<<" ";

return 0;

}

Sortare prin selectia minimului

int main()

{

int v[50],n,i,min,k,j,aux;

cout<<"n= ";cin>>n;

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

{cout<<"v["<<i<<"]= ";

cin>>v[i]; }

/*Vectorul este împărţit în două părţi imaginare - o parte sortată şi o parte nesortată.

La început, partea sortată este goală, iar partea nesortată conţine întreg tabloul. */

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

{min=v[i];

k=i;

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

if(v[j]<min) /*Se execută căutări repetate a elementului minim în partea nesortată.*/

{

min=v[j];

k=j;

}/*La fiecare pas, algoritmul găseşte elementul minim din partea nesortată şi îl adaugă la finalul părţii sortate.*/

aux=v[k];

v[k]=v[i];

v[i]=aux;

}

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

cout<<v[i]<<" ";

return 0;

}

Sortare prin inserţie

Vectorul este împărţit imaginar în două părţi - o parte sortată şi o parte nesortată. La început, partea sortată conţine primul element al tabloului şi partea nesortată conţine restul tabloului.

int main(){

int v[50], n,i,j,aux;

cout<<"Numarul de elemente din vector=";

cin>>n;

cout<<"Vectorul este:";

for(int k=0;k<=n-1;k++)

cin>>v[k];

for(i=1;i<n;i++)/* La fiecare pas, algoritmul ia primul element din partea nesortată şi îl inserează în locul potrivit al părţii sortate.*/

// Începem sa inseram de la al doilea element al vectorului

{/* Când partea nesortată nu mai are nici un element, algoritmul se opreşte.*/

j=i;

while(j>0&&v[j-1]>v[j])

{

aux=v[j];

v[j]=v[j-1];

v[j-1]=aux;

j--;

}

}

cout<<"Vectorul sortat este:";

for(k=0;k<=n-1;k++)

cout<<v[k]<<" ";

}