#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cstdlib>

using namespace std;

struct Tablou
{
    int t[1001];
    int n;

    /*
        Construieste un tablou cu lungime n care
    memoreaza peste tot valoarea val.
    */

    void Init(int dim, int val)
    {
        n = dim;
        for(int i = 0; i < n; i++)
            t[i] = val;
    }

    void Init(int dim)
    {
        srand(time(0));
        n = dim;
        for(int i = 0; i < n; i++)
            t[i] = rand() % 100;
    }

    void Afisare()
    {
        for(int i = 0; i < n; i++)
            cout << t[i] << " ";
        cout << "\n";
    }

    /*
        Cauta x in t si returneaza pozitia unde s-a gasit,
    sau -1 daca nu apare
    */
    int Cauta(int x)
    {
       for(int i = 0; i < n; i++)
           if(t[i] == x) return i;
       return -1;
    }

    void Insereaza(int p, int x)
    {
        if(p >= n) p = n;
        if(p < 0) p = 0;
        for(int i = n; i > p; i--)
            t[i] = t[i-1];
        t[p] = x;
        n++;
    }

    void Sterge(int p)
    {
        if(p >= n) return;
        if(p < 0) p = 0;
        for(int i = p; i < n; i++)
            t[i] = t[i+1];
        n--;
    }

    void QuickSort(int st, int dr)
    {
        int i, j, piv;
        piv = t[st];
        i = st+1;
        j = dr;
        while(i <= j)
        {
            if(t[i] <= piv) i++;
            if(t[j] >= piv) j--;
            if(i < j && t[i] > piv && t[j] < piv)
            {
                swap(t[i], t[j]);
                i++; j--;
            }
        }
        swap(t[st], t[i-1]);

        int m;
        m = i-1;
        if(st < m-1) QuickSort(st, m-1);
        if(m+1 < dr) QuickSort(m+1, dr);
    }

    void Sortare()
    {
        QuickSort(0, n-1);
    }

    void InserareCresc(int x)
    {
        Sortare();
        for(int i = 0; i < n; i++)
            if((x >= t[i]) && (x <= t[i+1]))
            {
                Insereaza(i+1, x);
                return;
            }

    }

    void SortParit()
    {
        int i, j;
        i = 0;
        j = n-1;
        while(i <= j)
        {
            while(t[i] % 2 == 0) i++;
            while(t[j] % 2 != 0) j--;
            if(i < j && t[i] % 2 != 0 && t[j] % 2 == 0)
            {
                swap(t[i], t[j]);
                i++; j--;
            }
        }
    }

    void VerifCresc()
    {
        for(int i = 0; i < n-1; i++)
            if(t[i] > t[i+1])
            {
                cout << "\nSir descrescator.";
                return;
            }
        cout << "\nSir crescator.";
    }
};

int main()
{
    Tablou a, b;
    //a.Init(20, 1);
    b.Init(10);
    //a.Afisare();
    //b.Afisare();

    //cout << "\n" << b.Cauta(27);

    /*
    b.Afisare();
    cout << "\n";
    b.Insereaza(1, 29);
    cout << "\n";
    b.Afisare();
    */

    /*
    b.Sterge(5);
    cout << "\n";
    b.Afisare();
    */

    /*
    b.Sortare();
    cout << "\n";
    b.Afisare();
    */

    /*
    b.Afisare();
    b.InserareCresc(21);
    cout << "\n";
    b.Afisare();
    */

    /*
    b.Afisare();
    cout << "\n";
    b.SortParit();
    b.Afisare();
    */

    b.Afisare();
    b.VerifCresc();
    cout << "\n";
    b.Sortare();
    b.Afisare();
    b.VerifCresc();
    return 0;
}