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]<<" ";

}