Algoritmul de sortare "Bubble Sort"

Sortare inseamna ordonarea in ordine crescatoare sau descrescatoare a elementelor unei colectii. In exemplul de mai jos am folosit un vector de numere intregi.
Exista doua variante ale algoritmului, prima este cea clasica si a doua cea imbunatatita. Ideea algoritmului este de a parcurge colectia (vectorul) de numere de la stanga la dreapta si de a compara numarul curent cu cel de dupa el (v[i] cu v[i+1]). Daca primul numar este mai mic sau egal cu al doilea atunci algoritmul continua altfel se interschimba cele doua valori. Se parcurge colectia de numere atat timp cat exista cel putin o pereche de numere care urmeaza a fi interschimbate. Colectia se parcurge de la primul element pana la penultimul si se compara fiecare element cu cel de dupa el.

void bubblesort(int v[], int n)
{
    bool sortat = false;
 
    while (!sortat)
    {
        sortat = true;
        for (int i = 0; i <= (n-2); i++)
        {
            if (v[i] > v[i+1])
            {
                int temp = v[i];
                v[i] = v[i+1];
                v[i+1] = temp;
                sortat = false;
            }
        }
    }
}

A doua varianta se bazeaza pe faptul ca dupa fiecare parcurgere a colectiei se acumuleaza maximele incepand de la dreapta la stanga. Dupa prima parcurgere pe ultima pozitie a vectorului va fi maximul dintre toate numerele, dupa a doua parcurgere pe penultima pozitie va fi maximul dintre toate numerele mai putin maximul care se afla pe ultima pozitie, la a treia parcurgere pe antepenultima pozitie va fi maximul dintre numerele de la prima pozitie pana la antepenultima pozitie, s.a.m.d. Se observa ca nu mai este nevoie de o parcurgere completa a colectiei de fiecare data si este sufient ca la fiecare parcurgere sa inspectam un numar de numere mai mic cu unu. La prima parcurgere se inspecteaza n numere, apoi n-1 numere apoi n-2 numere s.a.m.d.

void bubblesort2(int v[], int n)
{
    bool sortat = true;
  
    for (int i = n-2; i >= 0; i--)
    {
        sortat = true;
        for (int j = 0; j <= i; j++)
        {
            if (v[j] > v[j+1])
            {
                int temp = v[j];
                v[j] = v[j+1];
                v[j+1] = temp;
                sortat = false;
            }
        }
      
        if (sortat)
        {
            break; // vectorul este sortat
        }
    }
}