Sortarea prin metoda inserției

Descrierea metodei în limbaj natural

Vectorul este împărțit în două secvențe: la început o secvență ordonată, iar după ea o secvență neordonată. Inițial, secvența ordonată conține numai primul element, deoarece o secvență formată dintr-un singur element este ordonată.

La fiecare etapă, primul element din secvența neordonată se inserează în secvența ordonată, pe poziția care păstrează ordonarea. Poziția se determină prin parcurgerea secvenței ordonate de la dreapta spre stânga. Cât timp elementul întâlnit este mai mare decât valoarea de inserat, el se deplasează cu o poziție spre dreapta. Parcurgerea se oprește la primul element mai mic sau egal cu valoarea de inserat, iar valoarea se memorează pe poziția imediat următoare acestuia.

După fiecare etapă, partea ordonată crește cu un element, iar cea neordonată scade cu unul. Pentru un vector cu n elemente sunt necesare n−1 etape, fiindcă prima parte ordonată conține deja un element.

Exemplificarea etapelor pentru 7 numere

Se ordonează crescător numerele 5, 2, 9, 1, 7, 3, 8. Bara verticală desparte partea ordonată, la stânga, de cea neordonată, la dreapta.

După cele șase etape vectorul este ordonat crescător. Valoarea 9, inserată la a doua etapă fără nicio deplasare, este deplasată spre dreapta la fiecare dintre etapele următoare, deoarece este cel mai mare element.

Aprecierea complexității

În cazul cel mai nefavorabil, când vectorul este ordonat descrescător, fiecare valoare nouă trebuie deplasată până la începutul părții ordonate, deci la etapa i se fac i deplasări. Numărul total al operațiilor este de ordinul lui n², așa că complexitatea este O(n²). Complexitatea rămâne O(n²) și în cazul mediu, în care se parcurge, în medie, jumătate din partea ordonată.

În cazul cel mai favorabil, când vectorul este deja ordonat, fiecare valoare rămâne pe poziția ei după o singură comparație, iar complexitatea devine O(n).

Din punctul de vedere al duratei de executare, metoda inserției este potrivită pentru vectori de dimensiuni mici și pentru cei aproape ordonați, la care numărul deplasărilor este mic. Pentru volume mari de date se folosesc algoritmii cu complexitatea O(n·log n).

Problema propusă

Enunț. Se citesc de la tastatură un număr natural n (1 ≤ n ≤ 100) și n numere întregi, reprezentând temperaturile înregistrate la aceeași oră în n zile consecutive. Se cere să se afișeze temperaturile în ordine crescătoare și să se determine mediana lor, adică valoarea din mijlocul șirului ordonat, dacă n este impar, sau media aritmetică a celor două valori din mijloc, dacă n este par.

Exemplu: pentru n = 7 și temperaturile 5, 2, 9, 1, 7, 3, 8 se afișează 1 2 3 5 7 8 9, iar mediana este 5.

Descrierea soluției în limbaj natural. Se citesc numărul de zile și temperaturile, care se rețin într-un vector. Vectorul se ordonează crescător prin metoda inserției: fiecare element, începând cu al doilea, se inserează în secvența ordonată formată de elementele dinaintea lui. Elementele mai mari decât el se deplasează cu o poziție spre dreapta, iar valoarea se memorează pe poziția rămasă liberă.

Mediana nu poate fi determinată decât după ordonare, fiindcă ea este definită pe șirul ordonat, nu pe cel citit. După ordonare, poziția din mijloc se calculează direct din n: pentru n impar, mediana este elementul de pe poziția n/2 (pozițiile se numerotează de la 0); pentru n par, mediana este media aritmetică a elementelor de pe pozițiile n/2−1 și n/2. Împărțirea se face în format real, pentru ca media a două valori de parități diferite să nu fie trunchiată.

Se afișează întâi vectorul ordonat, apoi mediana.

Implementarea soluției.

#include <iostream>
using namespace std;

int main() {
    int t[100], n;

    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> t[i];

    /* Sortare prin insertie. Primele i elemente sunt deja ordonate;
       valoarea t[i] se insereaza pe pozitia care pastreaza ordonarea. */
    for (int i = 1; i < n; i++) {
        int x = t[i];
        int j = i - 1;
        while (j >= 0 && t[j] > x) {
            t[j + 1] = t[j];
            j--;
        }
        t[j + 1] = x;
    }

    for (int i = 0; i < n; i++)
        cout << t[i] << " ";
    cout << endl;

    cout << "Mediana: ";
    if (n % 2 == 1)
        cout << t[n / 2];
    else
        cout << (t[n / 2 - 1] + t[n / 2]) / 2.0;

    return 0;
}

Verificarea pe exemplul din enunț. Pentru cele șapte temperaturi date, vectorul ordonat este 1 2 3 5 7 8 9. Numărul de valori este impar, deci mediana este elementul de pe poziția 7/2 = 3, adică valoarea 5, a patra din șir, cu trei valori mai mici și trei mai mari.