Sortarea prin inserție

Sortarea prin inserție (Insertion Sort) este un algoritm de sortare care construiește o secvență sortată de elemente una câte una. Aici este o implementare în C++ a algoritmului de sortare prin inserție pentru un tablou de întregi:

#include <iostream>

void sortarePrinInserție(int lista[], int lungime) {
    for (int i = 1; i < lungime; i++) {
        int elementCurent = lista[i];
        int j = i - 1;

        while (j >= 0 && lista[j] > elementCurent) {
            lista[j + 1] = lista[j];
            j--;
        }

        lista[j + 1] = elementCurent;
    }
}

void afișareLista(int lista[], int lungime) {
    for (int i = 0; i < lungime; i++) {
        std::cout << lista[i] << " ";
    }
    std::cout << std::endl;
}

int main() {
    int lista[] = {5, 1, 9, 3, 7};
    int lungime = sizeof(lista) / sizeof(lista[0]);

    std::cout << "Lista initiala: ";
    afișareLista(lista, lungime);

    sortarePrinInserție(lista, lungime);

    std::cout << "Lista sortata: ";
    afișareLista(lista, lungime);

    return 0;
}

Această implementare a sortării prin inserție sortează un tablou de întregi în ordine crescătoare. Funcția sortarePrinInserție parcurge elementele tabloului și le inserează în locul corect în secvența sortată. Funcția afișareLista este folosită pentru a afișa conținutul tabloului.