Algoritmi de sortare

Programa prevede următoarele metode:

• metoda bulelor;
• sortarea prin inserție;
• sortarea prin selecție;
• sortarea prin numărare.

Primele trei ordonează elementele comparându-le între ele. A patra nu efectuează comparații între elemente și se poate aplica numai valorilor întregi dintr-un interval cunoscut și mic.

Toate exemplele de mai jos ordonează crescător.

Metoda bulelor

Cum funcționează algoritmul

• Tabloul se parcurge de la primul element spre ultimul.
• Se compară fiecare element cu vecinul lui din dreapta.
• Perechile care nu se află în ordinea cerută se interschimbă.
• La sfârșitul unei parcurgeri, cel mai mare element din partea neordonată ajunge pe ultima ei poziție.
• Parcurgerile se reiau cât timp în cea dinainte s-a făcut cel puțin o interschimbare.

Numele metodei vine de la felul în care elementele cu valori mari înaintează spre sfârșitul tabloului la fiecare parcurgere, asemenea bulelor de aer care se ridică la suprafața apei.

Pașii algoritmului

bule(v, n):
    pana ← n - 1
    repetă
        schimbat ← fals
        pentru i ← 1, pana execută
            dacă v[i] > v[i+1] atunci
                interschimbă v[i] cu v[i+1]
                schimbat ← adevărat
            sfdacă
        sfpentru
        pana ← pana - 1
    până când schimbat = fals

void bule(int v[], int n) {
    bool schimbat;
    int pana = n - 1;

    do {
        schimbat = false;

        for (int i = 0; i < pana; i++)
            if (v[i] > v[i + 1]) {
                swap(v[i], v[i + 1]);
                schimbat = true;
            }

        pana--;
    } while (schimbat);
}

def bule(v):
    pana = len(v) - 1
    schimbat = True

    while schimbat:
        schimbat = False

        for i in range(pana):
            if v[i] > v[i + 1]:
                v[i], v[i + 1] = v[i + 1], v[i]
                schimbat = True

        pana -= 1

Variabila pana scade cu o unitate după fiecare parcurgere: ultimele elemente se află deja pe pozițiile lor definitive, iar compararea lor din nou nu ar schimba nimic.

În Python, interschimbarea se scrie într-o singură atribuire, v[i], v[i+1] = v[i+1], v[i], fără variabilă ajutătoare. În C++, aceeași operație cere funcția swap sau o a treia variabilă.

Exemplu. Tabloul 5, 1, 4, 2.

Observație. Variabila schimbat face metoda eficientă pe date aproape ordonate. Pe un tablou deja sortat, algoritmul efectuează o singură parcurgere și se oprește. Fără această variabilă, numărul de parcurgeri ar fi întotdeauna același, oricât de ordonate ar fi datele.

Sortarea prin inserție

Cum funcționează algoritmul

• Tabloul se împarte în două părți: una ordonată, la început, și una neordonată.
• La început, partea ordonată cuprinde numai primul element.
• Se ia primul element din partea neordonată și se păstrează într-o variabilă.
• Elementele din partea ordonată mai mari decât el se deplasează cu o poziție spre dreapta.
• Elementul se așază pe locul rămas liber.
• Pașii se repetă până când partea neordonată rămâne vidă.

Pașii algoritmului

insertie(v, n):
    pentru i ← 2, n execută
        x ← v[i]
        j ← i - 1
        cât timp j ≥ 1 și v[j] > x execută
            v[j+1] ← v[j]
            j ← j - 1
        sfcât timp
        v[j+1] ← x
    sfpentru

void insertie(int v[], int n) {
    for (int i = 1; i < n; i++) {
        int x = v[i];
        int j = i - 1;

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

        v[j + 1] = x;
    }
}

def insertie(v):
    for i in range(1, len(v)):
        x = v[i]
        j = i - 1

        while j >= 0 and v[j] > x:
            v[j + 1] = v[j]
            j -= 1

        v[j + 1] = x

Exemplu. Tabloul 5, 1, 4, 2. Bara verticală arată hotarul dintre partea ordonată și cea neordonată.

Observație. Pe date aproape ordonate, fiecare element își găsește locul din una sau două comparații. Din acest motiv, metoda se folosește ca ultimă etapă în algoritmii de sortare eficienți, pentru subsecvențele scurte.

Ordonarea pe măsura citirii. Aceeași inserare se poate face chiar în timpul citirii: fiecare valoare nouă se așază pe locul ei între valorile citite până atunci, care formează deja un vector ordonat. După ultima citire, vectorul este ordonat.

int n, v[100], x;
cin >> n;
for (int i = 0; i < n; i++) {
    cin >> x;
    int j = i;
    while (j > 0 && v[j - 1] > x) {
        v[j] = v[j - 1];
        j--;
    }
    v[j] = x;
}

n = int(input())
v = []
for i in range(n):
    x = int(input())
    j = len(v)
    v.append(x)
    while j > 0 and v[j - 1] > x:
        v[j] = v[j - 1]
        j -= 1
    v[j] = x

Sortarea prin selecție

Cum funcționează algoritmul

• Tabloul se împarte tot în parte ordonată și parte neordonată, dar partea ordonată este la început vidă.
• Se caută poziția celui mai mic element din partea neordonată.
• Acesta se interschimbă cu primul element al părții neordonate.
• Elementul ajunge astfel la locul lui definitiv și trece în partea ordonată.
• Pașii se repetă până când în partea neordonată rămâne un singur element.

Pașii algoritmului