Algoritmul de Interclasare

Algoritmul presupune interclasarea a doua colectii de obiecte ordonate crescator si scrierea rezultatului intr-o a treia colectie astfel incat colectia rezultata sa fie ordonata crescator si sa contina toate elementele din cele doua colectii initiale. Daca un element apare in ambele colectii atunci va aparea de doua ori in colectia rezultata.

In exemplul de mai jos este o functie C++ care ia ca argumente doi vectori de numere intregi ordonate crescator si interclaseaza cei doi vectori intr-un al treilea care este dat ca ultim argument functiei. Functia intoarce lungimea vectorului rezultat care este intotdeauna suma lungimilor celor doi vectori initiali. Ultimul argument al functiei este folosit ca parametru de iesire.

int Interclasare(int v1[], int n1, int v2[], int n2,
            int v[])
{
    int i = 0; // index pentru v1
    int j = 0; // index pentru v2
    int k = 0; // index pentru vectorul rezultat v

    // scriu in v cel mai mic numar dintr v1[i] si v2[j] si avansez cu indexul corespunzator
    while (i < n1 && j < n2)
    {
        if (v1[i] <= v2[j])
        {
            v[k] = v1[i];
            i++;
        }
        else
        {
            v[k] = v2[j];
            j++;
        }
        k++;
    }

    if (i < n1)
    {
        // scriu in v ce a mai ramas din v1
        for (; i < n1; i++)
        {
            v[k] = v1[i];
            k++;
        }
    }
    else if (j < n2)
    {
        // scriu in v ce a mai ramas din v2
        for (; j < n2; j++)
        {
            v[k] = v2[j];
            k++;
        }
    }

    return k;
}

Algoritmul de sortare "Selection Sort"

Algoritmul de "Sortare prin selectie" este un algoritm pentru sortarea in ordine crescatoare sau descrescatoare a unei colectii de obiecte. In exemplul de mai jos am folosit un vector de numere intregi.

Algoritmul consta in parcurgerea repetata a vectorului pe secvente din ce in ce mai mici si aducerea pe prima pozitie a secventei parcurse a minimului din aceasta secventa. La prima parcurgere se aduce pe prima pozitie a vectorului minimul dintre toate numerele, la a doua parcurgere (de la al doilea element pana la ultimul) se aduce pe a doua pozitie minimul dintre numerele de la pozitia a doua pana la ultimul. A treia parcurgere se face de la al treilea element pana la ultimul si minimul se aduce pe pozitia a treia s.a.m.d. Ultima parcurgere va compara doar ultimele doua elemente ale vectorului.

void SelectSort(int v[], int n)
{
    for (int i = 0; i < n-1; i++)
    {
        int minim = v[i];
        int indmin = i;

        for (int j = i+1; j < n; j++)
        {
            if (v[j] < minim)
            {
                indmin = j;
                minim = v[j];
            }
        }

        if (indmin != i)
        {
            int temp = v[i];
            v[i] = v[indmin];
            v[indmin] = temp;
        }
    }
}

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
        }
    }
}