Sortarea prin metoda inserției

Descrierea metodei în limbaj natural

Metoda inserției construiește ordonarea puțin câte puțin, păstrând în permanență o parte a vectorului deja ordonată. La început, această parte este formată din primul element singur, care este ordonat în mod banal.

La fiecare etapă se ia primul element din partea neordonată și se așază la locul lui în partea ordonată. Locul se găsește parcurgând partea ordonată 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, făcând loc. Parcurgerea se oprește la primul element mai mic sau egal cu valoarea de inserat, iar valoarea se așază imediat după el.

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. Se observă că valoarea 9, inserată la a doua etapă fără nicio deplasare, ajunge să fie deplasată la fiecare dintre etapele următoare: fiind cel mai mare element, el este împins de fiecare dată spre dreapta.

Aprecierea complexității

În cazul cel mai nefavorabil, când vectorul este ordonat exact invers decât se cere, fiecare valoare nouă trebuie dusă 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²). Aceeași este și complexitatea în cazul mediu, când în medie se parcurge jumătate din partea ordonată.

În cazul cel mai favorabil, când vectorul este deja ordonat, fiecare valoare rămâne pe loc 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: se pornește de la al doilea element și, pentru fiecare, se caută locul potrivit printre elementele dinaintea lui, deplasându-le spre dreapta pe cele mai mari, până când se ajunge la poziția în care valoarea poate fi așezată.

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, indicii începând 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, ca media a două valori de paritate diferită 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 strecoara printre ele, la locul potrivit. */
    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 fiind impar, 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.