Sortarea prin metoda bulelor

Descrierea metodei în limbaj natural

Metoda bulelor ordonează elementele unui vector comparând numai elemente vecine. Se parcurge vectorul de la primul element spre ultimul și, la fiecare pas, se compară elementul curent cu cel imediat următor; dacă cele două nu se află în ordinea cerută, ele își schimbă locurile între ele.

O astfel de parcurgere completă a vectorului se numește etapă. La sfârșitul primei etape, cel mai mare element a ajuns cu siguranță pe ultima poziție: oriunde s-ar fi aflat, el a fost interschimbat la fiecare comparație și a fost împins până la capăt. La sfârșitul etapei a doua, al doilea element ca mărime ajunge pe penultima poziție, și așa mai departe. Numele metodei vine de la această deplasare: elementele mari urcă spre capătul vectorului ca bulele într-un lichid.

Etapele se reiau cât timp în etapa precedentă s-a făcut cel puțin o interschimbare. O etapă încheiată fără nicio interschimbare arată că toate perechile de elemente vecine sunt în ordine, deci întregul vector este ordonat, iar algoritmul se oprește. Fără această verificare, algoritmul nu ar avea criteriu de oprire.

Exemplificarea etapelor pentru 7 numere

Se ordonează crescător numerele 8, 3, 5, 1, 9, 2, 7.

În fiecare etapă, elementele îngroșate sunt cele ajunse definitiv la locul lor. Etapa a cincea nu produce nicio interschimbare, deci algoritmul se oprește: vectorul este ordonat crescător.

Se observă că numărul etapelor nu este dinainte cunoscut. Pentru acest vector au fost necesare cinci etape, dintre care ultima numai pentru a constata că ordonarea s-a încheiat.

Aprecierea complexității

În cazul cel mai nefavorabil, când vectorul este ordonat exact invers decât se cere, sunt necesare n−1 etape, iar în fiecare se fac până la n−1 comparații. Numărul comparațiilor este de ordinul lui n², deci complexitatea algoritmului este O(n²). Aceeași este și complexitatea în cazul mediu.

În cazul cel mai favorabil, când vectorul este deja ordonat, prima etapă nu produce nicio interschimbare, iar algoritmul se oprește după n−1 comparații: complexitatea devine O(n).

Din punctul de vedere al duratei de executare, metoda este potrivită pentru vectori de dimensiuni mici. Pentru volume mari de date, algoritmii cu complexitatea O(n·log n), cum este sortarea rapidă, sunt net mai eficienți.

Problema propusă

Enunț. La un concurs participă n elevi (n ≤ 100). Pentru fiecare se cunosc numele, format dintr-un singur cuvânt, și punctajul obținut, număr natural. Se cere afișarea clasamentului, în ordinea descrescătoare a punctajelor, iar la punctaje egale în ordinea alfabetică a numelor, și apoi afișarea numelor participanților care au obținut un punctaj strict mai mare decât media punctajelor.

Exemplu: pentru n = 5 și datele Ana 80, Bogdan 95, Carla 80, Dan 60, Elena 95, clasamentul este Bogdan 95, Elena 95, Ana 80, Carla 80, Dan 60, media punctajelor este 82, iar peste medie se află Bogdan și Elena.

Implementarea soluției.

#include <iostream>
#include <cstring>
using namespace std;

struct Participant {
    char nume[30];
    int punctaj;
};

int main() {
    Participant p[100], aux;
    int n;

    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> p[i].nume >> p[i].punctaj;

    /* Sortare prin metoda bulelor. Ordinea ceruta: punctaj descrescator,
       iar la punctaje egale nume crescator. */
    bool schimbat;
    do {
        schimbat = false;
        for (int i = 0; i < n - 1; i++)
            if (p[i].punctaj < p[i + 1].punctaj ||
                (p[i].punctaj == p[i + 1].punctaj &&
                 strcmp(p[i].nume, p[i + 1].nume) > 0)) {
                aux = p[i];
                p[i] = p[i + 1];
                p[i + 1] = aux;
                schimbat = true;
            }
    } while (schimbat);

    int suma = 0;
    for (int i = 0; i < n; i++)
        suma = suma + p[i].punctaj;
    float medie = (float)suma / n;

    cout << "Clasament:" << endl;
    for (int i = 0; i < n; i++)
        cout << i + 1 << ". " << p[i].nume << " " << p[i].punctaj << endl;

    cout << "Peste media " << medie << ":" << endl;
    for (int i = 0; i < n; i++)
        if (p[i].punctaj > medie)
            cout << p[i].nume << endl;

    return 0;
}

Descrierea soluției. Datele fiecărui participant se rețin într-o structură cu două câmpuri, iar participanții într-un vector de astfel de structuri. Prin interschimbarea structurilor întregi, nu numai a punctajelor, numele rămâne legat de punctajul lui pe tot parcursul sortării.

Sortarea folosește metoda bulelor, cu criteriul de ordonare cerut de problemă: două elemente vecine se interschimbă dacă punctajul primului este mai mic decât al celui de-al doilea sau dacă, la punctaje egale, numele primului urmează alfabetic după al celui de-al doilea. Compararea numelor se face cu funcția strcmp, care întoarce o valoare pozitivă când primul șir urmează după al doilea în ordinea alfabetică.

Variabila schimbat reține dacă în etapa curentă s-a făcut vreo interschimbare și dă condiția de oprire: etapele se reiau cât timp valoarea ei rămâne adevărată.

Media punctajelor se calculează după sortare, printr-o parcurgere separată a vectorului. Ordinea elementelor nu schimbă suma, deci calculul se poate face și înainte de sortare. Ultima parcurgere afișează numele celor cu punctaj strict mai mare decât media; fiindcă vectorul este deja ordonat descrescător, aceștia apar la început, în aceeași ordine ca în clasament.