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;
}

Bibliografie sau alte resurse

• PbInfo.ro
• SparkNotes
• Tutoriale-Pe.NET