#include <stdlib.h>
#include <stdio.h>

int set[20];

void Insertie(int nrElem)
{
    int i, j;
    int aux;

    for (i = 1; i < nrElem; i++)
    {
        aux = set[i];
        j = i - 1;
        while (j >= 0 && set[j] > aux)
        {
            set[j + 1] = set[j];
            j = j - 1;
        }
        set[j + 1] = aux;
    }

    printf("\nSortat prin insertie : ");
    for (i = 0; i < nrElem; i++)
    {
         printf("%d ", set[i]);
    }

}
void InsertiePerformanta(int nrElem)
{
    int i, j;
    int aux;
    int s, d, m;

    for (i = 1; i < nrElem; i++)
    {
        aux = set[i];
        s = 0; d = i-1;
        do
        {
            m = (s + d) / 2;
            if (aux < set[m])
            {
                d = m -1;
            }
            else
            {
                s = m + 1;
            }
        } while (s <= d);
        for (j = i - 1; j >= s; j--)
        {
            set[j + 1] = set[j];
        }
        set[j + 1] = aux;
    }

    printf("\nSortat prin insertie performanta : ");
    for (i = 0; i < nrElem; i++)
    {
        printf("%d ", set[i]);
    }
}
void Selectie(int nrElem)
{
    int aux, i, j;
    int min;

    for (i = 0; i < nrElem - 1; i++)
    {
        min = i;
        for (j = i + 1; j < nrElem; j++)
        {
            if (set[j] < set[min])
            {
                min = j;
            }
        }
        aux = set[i];
        set[i] = set[min];
        set[min] = aux;
    }
    printf("\nSortat prin selectie : ");
    for (i = 0; i < nrElem; i++)
    {
        printf("%d ", set[i]);
    }
}
void Bubblesort(int nrElem)
{
    int i, j;
    int aux;

    for ( j = 1; j < nrElem; j++)
    {
        for (i = 0; i < nrElem-1; i++)
        {
            if (set[i + 1] < set[i])
            {
                aux = set[i + 1];
                set[i + 1] = set[i];
                set[i] = aux;
            }
        }
    }
    printf("\nSortat prin bubblesort : ");
    for (i = 0; i < nrElem; i++)
    {
        printf("%d ", set[i]);
    }
}
void Shakersort(int nrElem)
{
    int st, dr, k, aux;
    st = 0;
    dr = nrElem - 1;
    do
    {
        for (int i = dr; i > st; i--)
        {
            if (set[i - 1] > set[i])
            {
                aux = set[i - 1];
                set[i - 1] = set[i];
                set[i] = aux;
                k = i;
            }
        }
        st = k;
        for (int i = st; i < dr; i++)
        {
            if (set[i] > set[i + 1])
            {
                aux = set[i];
                set[i] = set[i + 1];
                set[i + 1] = aux;
                k = i;
            }
        }
        dr = k;
    } while (st<dr);

    printf("\nSortat prin shackersort : ");
    for (int i = 0; i < nrElem; i++)
    {
        printf("%d ", set[i]);
    }
}
void Quicksort_Recursiv(int st, int dr)
{
    int i, j, x;
    int aux;

    i = st;
    j = dr;
    x = set[(st + dr) / 2];

    do
    {
        while (set[i] < x)
        {
            i++;
        }
        while (set[j] > x)
        {
            j--;
        }

        if (i <= j)
        {
            aux = set[i];
            set[i] = set[j];
            set[j] = aux;
            i++;
            j--;
        }


    } while (i <= j);

    if (st < j)
    {
        Quicksort(st, j);
    }
    if (dr > i)
    {
        Quicksort(i, dr);
    }

}

int main()
{
    FILE *f;

    int i=0;

    if (fopen_s(&f, "nr.txt", "r"))
    {
        printf("\nEroare la deschiderea fisierului ");
    }
    else
    {
        while (feof(f)==NULL)
        {
            fscanf_s(f, "%d", &set[i++]);
        }
    }

    //Insertie( i);
    //InsertiePerformanta(i);
    //Selectie(i);
    //Bubblesort(i);
    //Shakersort(i);
    //Quicksort_Recursiv(0, i - 1);
    system("pause");
    return 0;
}