Informatiile acestui spatiu sunt gratuite. Observatii si sugestii pot fi trimise pe adresa de contact sau pe forum.

     Sortari C++

Sortarea sau ordonarea unui sir/tablou/liste/etc. este o necesitate intalnita in multe cazuri atunci cand realizamm un algoritm pentru rezolvarea unei anumite probleme. Prin sortare se intelege realizarea unui algoritm prin intermediul caruia putem rearanja in ordine crescatoare sau descrescatoare un anumt numar de elemente.

Exista mai multi algoritmi de sortare, printre care putem enumera:

     Sortarea prin metoda bulelor / Bubble sort

Este una dintre cele mai simple metode de sortare, eficientã pentru un numãr mic de elemente, nefiind mare consumatoare de memorie. Metoda consta in parcurgerea unui vector de mai multe ori, pana cand acesta devine un vector ordonat. La fiecare pas se compara 2 elemente consecutive: v[i] si v[i+1], iar atunci cand v[i]>v[i+1] se interschimba cele 2 elemente (in cazul ordonarii crescatoare).

Pentru repetarea parcurgerii vectorului se foloseste o variabila booleana care la fiecare reluare a algoritmului primeste o valoare initiala, urmand ca aceasta sa se schimbe in cazul in care se efectueaza o interschimbare a valorilor celor 2 elemente consecutive. Cand tabloul va fi parcurs fara a se mai efectua nici o interschimbare, inseamna ca aceste este deja sortat - in consecinta algoritmul se va incheia.

Metoda este mai lentã decât metoda prin insertie, timpul de executie depinzand de datele de intrare, adicã de ordinea initialã al elementelor. Dacã tabela este deja sortatã e nevoie de un singur pas, adicã N-1 comparãri. În cazul cel mai nefavorabil sunt necesare N×(N-1)/2 comparãri si N×(N-1)/2 interschimbãri.

Pasii care trebuiesc urmati in cazul sortarii prin metoda bulelor:

  • Se citesc elementele vectorului (nesortat)
  • Se creaza bucla repetitiva de parcurgere a vectorului (do...while)
    • se initialiseaza variabila booleana utilizata pentru controlul parcurgerii vectorului
    • se creaza bucla repetitiva (for) pentru a realiza compararea elementelor succesive ale vectorului
      • se compara elementele succesive (v[i] si v[i+1]) - daca v[i]>v[i+1] atunci:
        • se interschimba valorile v[i] si v[i+1]
        • se modifica valoarea variabilei booleene
  • Se afiseaza elementele vectorului (sortat).

Exemplu: Sa se ordoneze crescator un vector de n elemente folosind metoda bulelor.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
using namespace std;
int main()
{
   int v[20],n,i,gasit,temp;
   cout<<"Introduceti dimensiunea vectorului: n=";cin>>n;
   cout<<"Introduceti elementele vectorului:"<<endl;
   for(i=1;i<=n;i++)
   {
      cout<<"v["<<i<<"]=";
      cin>>v[i];
   }
   do
      {
         gasit=0;
         for(i=1;i<n;i++)
         if(v[i]>v[i+1])
            {
            temp=v[i];
            v[i]=v[i+1];
            v[i+1]=temp;
            gasit=1;
            }
      }
   while(gasit==1);
   cout<<"Dupa sortarea bubble sort, vectorul este: ";
   for(i=1;i<=n;i++)
      cout<<v[i]<<" ";
}
Introduceti dimensiunea vectorului: n=4
Introduceti elementele vectorului:
v[1]=3
v[2]=2
v[3]=5
v[4]=1
Dupa sortarea bubble sort, vectorul este: 1 2 3 5
























top

     Sortarea prin selectie directa / Selection sort

Prin aceasta metoda se cauta elementul minim din fiecare subsir obtinut din sirul initial cu exceptia primului element a sirului/subsirului initial. Astfel, daca avem un vector V cu n elemente:
- primul subsir este: v[2], v[3], ... , v[n] - se cauta minimul din acest subsir si acesta se interschimba cu v[1]
- al doilea subsir este: v[3], v[4],...,v[n] - se cauta minimul din acest subsir si acesta se interschimba cu v[2]
- al treilea subsir este: v[4], v[5],...,v[n] - se cauta minimul din acest subsir si acesta se interschimba cu v[3]
- s.a.m.d.

Pentru repetarea cautarii minimului in subvectorii consecutivi se folosesc 2 structuri repetitive cu numar finit de pasi (for).

Pasii care trebuiesc urmati in cazul sortarii prin metoda selectiei directe:

  • Se citesc elementele vectorului (nesortat)
  • Se creaza bucla repetitiva de parcurgere a vectorului (de la primul pana la penultimul element: for i=1;i<n;i++)
    • se retine intr-o variabila (min) valoarea aflata in vector pe pozitia i
    • se retine pozitia i intr-o alta variabila (k) in vederea interschimbarii valorii vectorului de pe aceasta pozitie cu o eventuala valoare mai mica gasita pe alta pozitie
    • se realizeaza o a doua parcurgere a vectorului incepand cu pozitia i+1 pana la ultima pozitie: (for j=i+1;j<n;j++)
      • se compara valoarea stocata in variabila min cu elementele v[j] - daca se gaseste o valoare mai mica atunci:
        • variabila min va primi valoarea gasita in v[j]
        • se retine pozitia valorii mai mici gaisite (j) in variabila k
    • se interschimba valorile v[i] si v[k]
  • Se afiseaza elementele vectorului (sortat).

Exemplu: Sa se ordoneze crescator un vector de n elemente folosind metoda selectiei directe.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
using namespace std;
int main()
{
   int v[20],n,i,j,k,min,temp;
   cout<<"Introduceti dimensiunea vectorului: n=";cin>>n;
   cout<<"Introduceti elementele vectorului:"<<endl;
   for(i=1;i<=n;i++)
   {
      cout<<"v["<<i<<"]=";
      cin>>v[i];
   }
   for(i=1;i<n;i++)
      {
         min=v[i];
         k=i;
         for(j=i+1;j<=n;j++)
            if(v[j]<min)
               {
               min=v[j];
               k=j;
               }
         temp=v[i];
         v[i]=v[k];
         v[k]=temp;
      }
   cout<<"Dupa sortarea prin selectie directa, vectorul este: ";
   for(i=1;i<=n;i++)
      cout<<v[i]<<" ";
}
Introduceti dimensiunea vectorului: n=4
Introduceti elementele vectorului:
v[1]=3
v[2]=2
v[3]=5
v[4]=1
Dupa sortarea prin selectie directa, vectorul este: 1 2 3 5

























top