Menu
Probleme Rezolvate
Manual clasa a X a |
Tehnici de implementarea algoritmilor |
Recursivitate |
Metoda bulelor este o metodă de sortare a unui vector care constă în repetarea mai multor treceri peste vector, în fiecare trecere comparându-se fiecare element cu elementul următor și schimbându-le poziția dacă nu sunt în ordine.
Implementarea recursivă a acestei metode se poate face astfel:
# include < iostream >
using namespace std ;
// Subprogram recursiv pentru sortarea crescatoare a unui vector folosind metoda bulelor
void bubbleSort ( int v[], int n) {
// Cazul de bază: vectorul de un singur element este deja sortat
if (n == 1 ) {
return ;
}
// Parcurgem vectorul si interschimbam elementele vecine daca sunt in ordine inversa
for ( int i = 0 ; i < n - 1 ; i++) {
if (v[i] > v[i+ 1 ]) {
int temp = v[i];
v[i] = v[i+ 1 ];
v[i+ 1 ] = temp ;
}
}
// Apelam recursiv functia bubbleSort pentru vectorul ramas
bubbleSort (v, n -1 );
}
// Exemplu de utilizare a subprogramului de sortare
int main () {
int v[] = { 5 , 2 , 4 , 6 , 1 , 3 };
int n = 6 ;
cout << "Vectorul initial : " ;
for ( int i = 0 ; i < n; i++) {
cout << v[i] << " " ;
}
cout << endl ;
bubbleSort (v, n);
cout << "Vectorul sortat: " ;
for ( int i = 0 ; i < n; i++) {
cout << v[i] << " " ;
}
cout << endl ;
return 0 ;
}
using namespace std ;
// Subprogram recursiv pentru sortarea crescatoare a unui vector folosind metoda bulelor
void bubbleSort ( int v[], int n) {
// Cazul de bază: vectorul de un singur element este deja sortat
if (n == 1 ) {
return ;
}
// Parcurgem vectorul si interschimbam elementele vecine daca sunt in ordine inversa
for ( int i = 0 ; i < n - 1 ; i++) {
if (v[i] > v[i+ 1 ]) {
int temp = v[i];
v[i] = v[i+ 1 ];
v[i+ 1 ] = temp ;
}
}
// Apelam recursiv functia bubbleSort pentru vectorul ramas
bubbleSort (v, n -1 );
}
// Exemplu de utilizare a subprogramului de sortare
int main () {
int v[] = { 5 , 2 , 4 , 6 , 1 , 3 };
int n = 6 ;
cout << "Vectorul initial : " ;
for ( int i = 0 ; i < n; i++) {
cout << v[i] << " " ;
}
cout << endl ;
bubbleSort (v, n);
cout << "Vectorul sortat: " ;
for ( int i = 0 ; i < n; i++) {
cout << v[i] << " " ;
}
cout << endl ;
return 0 ;
}
Subprogramul bubbleSort () primește ca parametri un vector v și lungimea sa n . În fiecare apel al funcției, se compară fiecare element cu elementul următor și se interschimbă poziția lor dacă nu sunt în ordine. Apoi se apelează recursiv funcția bubbleSort () pentru vectorul ramas , adică pentru vectorul fără ultimul element (deoarece acesta este deja plasat pe poziția sa finală). Cazul de bază al funcției este când vectorul are un singur element, în acest caz nu mai este necesară nicio trecere peste vector, deci funcția se termină recursivitatea.