Contact și feedback

Nu obții 100 de puncte sau ai nelămuriri în privința problemelor? Scrie-mi pe Instagram.


Ai găsit o greșeală, vrei să raportezi un utilizator sau vrei să comunici altceva? Folosește formularul de contact.


Vrei să ne transmiți o părere despre platformă? Folosește formularul de feedback.

Shortcuturi

Folosește următoarele shortcuturi pentru a naviga mai ușor pe platformă.

Generale

Meniu shortcuturi?
Căutare probleme sau utilizatori/
Navigare printre rezultatele căutării↑, ↓
Meniu de contact și feedbackCTRL + Shift + F
Ieșire din meniuriEsc

Editor probleme

Setări editorCTRL + Shift + S
Schimbare stil editorCTRL + Shift + E
Șabloane de codCTRL + Shift + 1/2/3
Golire editorCTRL + Shift + 4

Sortare crescătoare recursivă în C++ - Merge sort și Bubble sort

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:

https://i.ibb.co/1d5cg2y/image.png

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

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Cuprinsul lecției

Se încarcă…

Citește și

Suma 1 + 2 + 3 + ... + N în C++Al N-lea termen Fibonacci în C++Mediana unui șir de valori în C++Cel mai frecvent element dintr-un șir în C++Cea mai lungă secvență de elemente crescătoare în C++Cum să calculezi instant 2 la puterea N în C++Verificare număr prim în C++ (Clasa a IX-a)Verificare dacă un număr este palindrom în C++Numărul de divizori primi ai unui număr în C++Aplicații cu ciurul lui Eratostene în C++: suma divizorilor, numărul divizorilorȘiruri de caractere în C++. Tot ce trebuie să știiDe ce cer unele probleme răspunsul modulo 666013 sau modulo 1.000.000.007?Comentarii în C++Numărul aranjamentelor în C++ (formula aranjamentelor)Afișarea divizorilor primi ai unui număr în C++Verificare dacă șir de caractere este palindrom în C++Vectori de frecvență (de apariții) în C++Cum să afișezi partea întreagă a unui număr real în C++Maximul și minimul a n valori în C++Vectorii în C++: declarare și parcurgereInstrucțiunea continue (structuri repetitive)Cifra maximă a unui număr recursiv în C++Indicatorul lui Euler al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Sortare crescătoare recursivă în C++ - Merge sort și Bubble sortValoarea absolută (modulul) unui număr în C++Numărul permutărilor în C++ (formula permutărilor)Maximul și minimul unui vector în C++Funcții în C++. Ce sunt subprogrameleRidicarea la putere în timp logaritmic în C++. Exponențiere rapidăAria unui triunghi folosind coordonatele acestora în C++Do while vs while în C++ - Care e diferența?Suma numerelor naturale dintr-un interval dat în C++Materia pentru olimpiada de informatică - tot ce trebuie să știiRadicalul unui număr în C++ (rădăcina pătrată)Instrucțiunea break (structuri repetitive)Numărul de divizori al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Numere triunghiulare. Verificarea unui număr triunghiularCombinatorică în C++: permutări, aranjamente, combinări și alteleInstrucțiunea de decizie în C++: if, else, switch, caseVerifică dacă o literă este vocală în C++Ciurul lui Eratostene în C++Oglinditul recursiv al unui număr în C++Codul ASCII (tabel complet)Verifică dacă un bit de pe o anumită poziție este 1 sau 0 în C++Prima cifră a unui număr în C++Tutorial instalare CodeBlocks (ușor) - Introducere în informatică C++Matrice pătratice în C++. Diagonala principală și secundarăMatrice Fibonacci - al n-lea termen Fibonacci în timp logaritmicInterschimbarea a două variabile în C++ (3 metode)Numărul minim de peroane pentru o gară în C++Interclasarea a doi vectori în C++Află secolul unui an citit de la tastatură în C++Algoritm recursiv pentru căutare binară (clasa a X-a)Rădăcina cubică a unui număr în C++ (cube root)Cifra maximă și minimă a unui număr în C++Verifică dacă un caracter este literă în C++Maximul și minimul a trei valori în C++Indicatorul lui Euler în C++Cifrele unui număr. Prelucrarea cifrelor unui număr în C++Transformarea unui număr din baza 2 în baza 10 în C++Divide et Impera (metodă de programare C++)Șirul lui Fibonacci în C++Instrucțiunea do while (structuri repetitive)Verifică dacă un număr dat este o putere de 2 în C++Cel mai mic/mare divizor prim al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Aria și circumferința unui cerc în C++Tipul struct în C++. Ce sunt structurile de date neomogeneVerifică dacă un număr este par sau impar fără modulo în C++Numărul de cifre ale factorialului unui numărFuncții predefinite în C++ (matematice, șiruri de caractere)Cel mai mare divizor comun (CMMDC) a două numere în C++Vectorii în C++: citire și afișareCalculul combinărilor de n luate câte k (nCk) în C++Bordarea unei matrice în C++Ce este o funcție void în C++?Suma divizorilor numerelor de la 1 la N (Folosind ciurul lui Eratostene)Al N-lea termen dintr-o progresie geometricăInversarea unui vector în C++Distanța dintre două puncte în C++Structuri repetitive (while, do while, for, etc)Căutare binară în C++Generarea șirului Fibonacci generalizat în C++Complexitatea unui algoritm (timp și spațiu) în C++Verifică dacă trei puncte sunt coliniare C++Aflarea sumei primelor N sume GaussTransformarea unei litere mici în literă mare în C++Verifică dacă un caracter este cifră în C++Suma elementelor unui vector recursiv în C++Transformarea unei litere mari în literă mică în C++Transformarea unui număr din baza 10 în baza 2 în C++Copiuțe: Cifrele unui numărAl N-lea termen dintr-o progresie aritmeticăCe înseamnă variabilă globală și locală în C++?Tipuri de date în C++: numere întregi, reale, caractere și alteleInstrucțiunea for (structuri repetitive)Citirea și afișarea matricelor în C++Cel mai semnificativ bit în C++Operații cu numere mari în C++ - Toate funcțiile explicateCâte numere naturale sunt într-un interval dat? (C++)Ce înseamnă endl în C++?Citește un șir de caractere cu spații în C++Verificarea unui an bisect în C++CMMDC recursiv a două numere naturale în C++Numărul de divizori al unui număr în C++Recursivitate în C++Cum să citești și să afișezi în fișiere în C++Matrice în C++. Declararea și parcurgerea tablourilor bidimensionaleOglinditul unui număr în C++Instrucțiunea while (structuri repetitive)Numărul combinărilor în C++ (formula combinărilor)Suma divizorilor unui număr în C++Inversarea unui șir de caractere în C++Afișarea elementelor unui vector recursiv în C++CMMMC a două numere în C++ (cel mai mic multiplu comun)Factorialul unui număr în C++Cifra de control a unui numărPointer în C++. Variabile de tipul char * (char steluță)Verifică dacă un număr aparține șirului Fibonacci în C++Verifică dacă o literă este mică sau mare în C++Maximul și minimul a două valori în C++Numărul de apariții al unui număr într-un vector în C++Cel mai puțin semnificativ bit în C++Cel mai mic număr cu suma cifrelor N în C++Ce este o variabilă unsigned în C++?

© Drepturi de autor

Echipa InfoAs își rezervă drepturile de autor pentru conținutul acestei pagini. Copierea conținutului fără acordul scris expres al InfoAs reprezintă o încălcare a Legii 8/1996 și va fi tratată ca atare.

Trimite lecția

Toată lecția

Doar videoclipul pe YouTube

Informatica devine ușoară cu InfoAs

Intră în cont