Dându-se un șir a[] cu n elemente, să se ordoneze crescător elementele acestuia, folosind un subprogram recursiv.
Exemplu. Pentru a = (1, 10, 9, 8, 2), șirul ordonat este (1, 2, 8, 9, 10).
Metoda 1: Bubble sort (recursiv)
Bubble sort este pesemne cel mai cunoscut algoritm de sortare. Să analizăm cum funcționează.
Explicarea algoritmului
Bubble sort funcționează astfel: se parcurg elementele șirului și dacă se întâlnesc două elemente consecutive într-o ordine greșită (elementul mai mic este după cel mai mare), acestea se interschimbă. Forma algoritmului nerecursiv, învățat în clasa a IX-a, este următoarea:
for(int i = 1; i < n; i++) {
for(int j = i + 1; j <= n; j++) {
if(a[i] > a[j]) { //a[j] e după a[i], dar e mai mic => interschimbare
int aux = a[i];
a[i] = a[j];
a[j] = aux;
}
}
}
Transformarea în formă recursivă constă în schimbarea primei structuri repetitive for într-o funcție recursivă. Astfel, funcția noastră va lua ca parametri:
- Șirul nostru (
a); - Lungimea șirului (
n); - Indicele curent (
i).
Această funcție va conține un for, care este echivalent cu cel de-al doilea for din codul de mai sus.
Funcția va fi de tip void, pentru că nu returnează nimic.
Implementare C++
Iată codul în C++:
#include <iostream>
using namespace std;
void sortare(int a[], int n, int i) {
if(i > n) { //Dacă am ieșit din "for"-ul mare (condiție de oprire)
return; //Ne oprim (ca și break)
}
for(int j = i + 1; j <= n; j++) {
if(a[i] > a[j]) { //a[j] e după a[i], dar e mai mic => interschimbare
int aux = a[i];
a[i] = a[j];
a[j] = aux;
}
}
sortare(a, n, i + 1);
}
int main()
{
//Declarăm și citim șirul nostru
int n, a[101];
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
//Sortarea șirului
sortare(a, n, 1);
//Afișarea șirului după sortare
cout << "Sirul sortat este: ";
for(int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
return 0;
}
Metoda 2: Merge sort (recursiv)
Merge sort este un algoritm de tip Divide et Impera — mai exact, pentru a sorta șirul curent, vom împărți șirul în două jumătăți și le vom sorta, după care le vom interclasa. La rândul lor, jumătățile se vor împărți în alte două jumătăți fiecare pe le vom sorta și le vom interclasa. Iată un exemplu vizual:
Implementare C++
Codul este ușor de parcurs, deoarece urmărește exact metoda sortării menționată mai sus:
#include <iostream>
using namespace std;
void sortare(int a[], int st, int dr) { //st, dr sunt indicii secvenței curente
if(st >= dr) { //Caz particular de oprire
return;
}
//Împărțim șirul în două secvențe: (st, mijloc) și (mijloc + 1, dr)
int mijloc = (st + dr) / 2;
//Sortăm cele două jumătăți
sortare(a, st, mijloc);
sortare(a, mijloc + 1, dr);
//Interclasăm cele două jumătăți sortate
int tmp[101], k = 0; //Vector temporar
int i = st, j = mijloc + 1;
while(i <= mijloc && j <= dr) {
if(a[i] < a[j]) {
tmp[++k] = a[i++];
} else {
tmp[++k] = a[j++];
}
}
while(i <= mijloc) {
tmp[++k] = a[i++];
}
while(j <= dr) {
tmp[++k] = a[j++];
}
//Înlocuim secvența curentă cu vectorul temporar
i = st;
j = 1;
while(i <= dr) {
a[i] = tmp[j];
i++;
j++;
}
}
int main()
{
//Declarăm și citim șirul nostru
int n, a[101];
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
//Sortarea șirului folosind algoritmul recursiv Merge sort
sortare(a, 1, n);
//Afișarea șirului după sortare
cout << "Sirul sortat este: ";
for(int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
return 0;
}