Sortări

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

void citire(int vect[], int& dim)
{
    ifstream f("sortări.in");
    f >> dim;
    for (int i = 0; i < dim; i++)
        f >> vect[i];
}

void afisare(int vect[], int dim)
{
    for (int i = 0; i < dim; i++)
        cout << vect[i] << ' ';
    cout << endl;
}

// Sortarea prin interschimbare
void SortareInterschimbare(int vect[], int dim)
{
    for (int i = 0; i < dim - 1; i++)
        for (int j = i + 1; j < dim; j++)
            if (vect[i] > vect[j])
                swap(vect[i], vect[j]);
}

// Sortarea prin selectie
void SortareSelectie(int vect[], int dim)
{
    for (int i = 0; i < dim; i++)
    {
        int min = vect[i], poz = i;

        for (int j = i + 1; j < dim; j++)
            if (vect[j] < min)
            {
                min = vect[j];
                poz = j;
            }
        swap(vect[i], vect[poz]);
    }
}

// Sortarea prin metoda bulelor
void SortareBule(int vect[], int dim)
{
    bool ok = 0;
    do
    {
        ok = 0;
        for (int i = 0; i < dim - 1; i++)
            if (vect[i] > vect[i + 1])
            {
                ok = 1;
                swap(vect[i], vect[i + 1]);
            }
    } while (ok == 1);
}

// Sortare prin interclasare
int vectAux[30];
void SortareInterclasare(int vect[], int st, int dr)
{
    if (st < dr)
    {
        int mij = (st + dr) / 2;
        SortareInterclasare(vect, st, mij);
        SortareInterclasare(vect, mij + 1, dr);

        //Interclasare
        int i = st, j = mij + 1, k = 0;
        while (i <= mij && j <= dr)
            if (vect[i] < vect[j])
                vectAux[++k] = vect[i++];
            else
                vectAux[++k] = vect[j++];
        while (i <= mij)
            vectAux[++k] = vect[i++];
        while (j <= dr)
            vectAux[++k] = vect[j++];

        for (i = st, j = 1; i <= dr; i++, j++)
            vect[i] = vectAux[j];
    }
}

// Sortarea rapida
void QuickSort(int vect[], int stanga, int dreapta)
{
    int i = stanga, j = dreapta;
    int pivot = vect[(stanga + dreapta) / 2];

    /*Partitionare */
    while (i <= j)
    {
        while (vect[i] < pivot) //> pt descr
            i++;
        while (vect[j] > pivot) //< pt descr
            j--;
        if (i <= j)
        {
            int tmp = vect[i];
            vect[i] = vect[j];
            vect[j] = tmp;
            i++;
            j--;
        }
    }

    /* Recursivitate */
    if (stanga < j)
        QuickSort(vect, stanga, j);
    if (i < dreapta)
        QuickSort(vect, i, dreapta);
}

// BucketSort
int maxVect(int vect[], int dim)
{
    int max = -1;
    for (int i = 0; i < dim; i++)
        if (max < vect[i])
            max = vect[i];
    return max;
}

void BucketSort(int vect[], int dim, int max)
{
    int vectAux[10] = { 0 };

    for (int i = 0; i < dim; i++)
        vectAux[vect[i]]++;

    int index = 0;
    for (int i = 0; i <= max; i++)
        for (int j = 0; j < vectAux[i]; j++)
            vect[index++] = i;
}

// CountingSort
void CountingSort(int vect[], int dim, int max)
{
    int vectCount[30] = { 0 }, vectSort[30] = { 0 };

    for (int i = 0; i < dim; i++)
        vectCount[vect[i]]++;

    for (int i = 1; i <= max; i++)
        vectCount[i] += vectCount[i - 1];

    for (int i = 0; i < dim; i++)
        vectSort[vectCount[vect[i]] - 1] = vect[i];

    for (int i = 0; i < dim; i++)
        vect[i] = vectSort[i];
}

int main()
{
    int dim, vect[30] = { 0 };
    citire(vect, dim);

    /*
    SortareInterschimbare(vect, dim);
    cout << "Sortarea prin interschimbare: \n";
    afisare(vect, dim);

    SortareSelectie(vect, dim);
    cout << "Sortarea prin selectia minimului: \n";
    afisare(vect, dim);

    SortareBule(vect, dim);
    cout << "Sortarea prin metoda bulelor: \n";
    afisare(vect, dim);

    SortareInterclasare(vect, 0, dim - 1);
    cout << "Sortarea prin interclasare: \n";
    afisare(vect, dim);

    QuickSort(vect, 0, dim - 1);
    cout << "Sortarea rapida: \n";
    afisare(vect, dim);
    */

    int vect1[30] = { 0, 12, 2, 3, 4, 0, 9, 5 };

    /*
    BucketSort(vect1, 8, maxVect(vect1, 8));
    cout << "Bucket Sort: \n";
    afisare(vect1, 8);
    */

    CountingSort(vect1, 8, maxVect(vect1, 8));
    cout << "Counting Sort: \n";
    afisare(vect1, 8);

    return 0;
}