Pagina informaticii

Teste de informatică pentru liceu, articole C#, C/C++, PHP

Sortarea vectorilor în C++ utilizând STL

Problema ordonării crescătoare sau descrescătoare a unui vector apare frecvent. Pentru a evita definirea unei funcţii pentru ordonare, se poate utiliza cu succes o funcţie din Standard Template Library (STL), anume funcţia sort. Avantajul principal este complexitatea sortării care este O(n log n). Iată un exemplu în care definim un vector de 10 numere întregi (tabloul este indexat de la 0 la 9) şi-l ordonăm crescător:

int a[] = {5, 1, 3, 7, 8, 9, 2, 6, 10, 3} ;
sort(a, a + 10) ;

În continuare ne propunem să generăm un tablou de n numere naturale aleatoare cuprinse între 0 şi 99 şi să-l ordonăm descrescător. Iată programul:

int a[1000], n ;

// se genereaza un vector de numere aleatoare cuprinse intre 0 si 99
void Generare()
{
 int i ;
 srand(time(0)) ;
 for (i = 0 ; i < n ; i++)
    a[i] = rand() % 100;
}

void Afisare()
{
 int i ;
 for (i = 0 ; i < n ; i++)
    cout << a[i] << " " ;
}

int main()
{
 n = 50 ;
 Generare() ;
 sort( a, a + n, greater< int > () ) ;
 Afisare() ;
 return 0 ;
}

Vom considera acum că avem un vector de n puncte în spaţiu, fiecare punct fiind dat prin coordonatele (x, y, z). Dorim realizarea unei ordonări a punctelor în primul rând după x, iar dacă există puncte au coordonata x identică, vom face ordonarea crescătoare după y. Pentru aceasta trebuie definită o funcţie - am numit-o cmp - care compară două elemente de tip punct în spaţiu. Iată programul.

struct punct
{
   int x, y, z;
};

punct a[1000];
int n ;

// sortare crescatoare dupa x; in caz de egalitate,
// se face sortarea crescator dupa y
inline bool cmp (const punct A, const punct B )
{
 if (A.x == B.x)
    return A.y < B.y;
 return A.x < B.x ;
}

void Citire()
{
 int i ;
 ifstream fin("puncte.in");
 fin>>n ;
 for (i = 0 ; i < n ; i++)
    fin >> a[i].x >> a[i].y >> a[i].z ;
 fin.close() ;
}

void Afisare()
{
 int i ;
 for (i = 0 ; i < n ; i++)
    cout << a[i].x << " " << a[i].y << " " << a[i].z << "\n" ;
}

int main()
{
 Citire() ;
 sort (a, a + n, cmp);
 Afisare() ;
 return 0 ;
}

În cazul în care se doreşte sortarea punctelor după alte criterii, de exemplu descrescător, pur şi simplu se poate modifica funcţia cmp.

Despre autor
Author

Dan Pracsiu deţinător www.dponline.ro
Profesor, Liceul Teoretic "Emil Racoviță" Vaslui
Membru în Comisia Naţională a Olimpiadelor de Informatică
Pasiuni: istoria, călătoriile, fotografia, muzica clasică

Scrie un comentariu
Nume:

Comentariu:

15 + 10 =