#include <iostream>

using namespace std;

int main()
{

//INTERSCHIMBARE DIRECTA
  /*n = 5
    v : 7 2 5 8 6
    i : 1 2 3 4 5
    */
    for(i=1; i<=n-1; i++)
        //cauta la dreapta elementului curent
        for(j=i+1; j<=n; j++)
        {
            // i=1 7>2 X ; 2>5;  2>8; 2>6
            // i=2 7>5 X; 5>8; 5>6
            // i=3 7>8; 7>6 X
            // i=4 8>7 X
            if(v[i]>v[j])
            {
                //interschimbare
                aux = v[i];
                v[i]= v[j];
                v[j]= aux;
                // 1 2 3 4 5 = i
                // 2 7 5 8 6
                // 2 5 7 8 6
                // 2 5 6 8 7
                // 2 5 6 7 8
            }
        }
//METODA BULELOR (BUBBLE SORT)
    /*n = 5
    v : 7 2 5 8 6
    i : 1 2 3 4 5
    */
    do
    {
        ok = 1; //presupun ca vectorul este sortat
        for(i=1; i<=n-1; i++)
        {
            // i=1 7>2 X
            // i=2 7>5 X
            // i=3 7>8
            // i=4 8>6 X
            // i=1 2>5
            // i=2 5>7
            // i=3 7>6 X
            // i=4 7>8
            if(v[i]>v[i+1])
            {
                //interschimbare
                aux = v[i];
                v[i]= v[i+1];
                v[i+1]= aux;
                ok=0;
                // 1 2 3 4 5
                // 2 7 5 8 6
                // 2 5 7 8 6
                // 2 5 7 6 8
                //se reia do while fiindca am ajuns la i=5 si ok==0
                // 2 5 6 7 8
            }
        }
    }
    while(ok==0);

//SORTARE SELECTIE MIN
    /*n = 5
    v : 7 2 5 8 6
    i : 1 2 3 4 5
    */
    for(i=1; i<=n-1; i++)
    {
        //initializam minimul cu valoarea curenta
        minim = v[i];
        poz_min = i;
        //cautam la dreapta un alt minim
        for(j=i+1; i<=n; j++)
        {
            // i=1 : minim=7, poz=1
            //       2<7 X minim = 2 poz =2
            //       5<2 8<2 6<2
            //facem interschimbarea
            // i=2 : minim=7, poz=2
            //       5<7 X minim = 5 poz=3
            //       8<5 6<5
            //facem interschimbarea
            // i=3 : minim=7, poz=3
            //      8<7 6<7X minim=6 poz=5
            //facem intersch
            // i=4 : minim = 8 poz=4
            //      7<8X minim=7 poz=5
            //facem intersc
            if(v[j]<minim)
            {
                minim=v[j];
                poz_min=j;

            }
        }
        //interschimbam elementul curent cu minimul din dreapta lui
        aux = v[i];
        v[i]= v[poz_min];
        v[poz_min]= aux;
        // 1 2 3 4 5
        // 2 7 5 8 6
        // 2 5 7 8 6
        // 2 5 6 8 7
        // 2 5 6 7 8
    }

//SORTARE SELECTIE MAX
   /*n = 5
    v : 7 2 5 8 6
    i : 1 2 3 4 5
    */
    //parcurg vectorul de la final la inceput
    for(i=n; i>=2; i--)
    {
        maxim=v[i];
        poz_max = i;
        //caut in stanga
        for(j=i-1; j>=1; j--)
        {
            // i=5 : maxim=6 poz=5
            //      8>6 X maxim=8 poz=4
            //      5>8 2>8 7>8
            //facem intersch
            // i=4 : maxim=6 poz=4
            //      5>6 2>6 7>6 X maxim=7 poz=1
            //facem intersch
            // i=3 : maxim=5 poz=3
            //      2>5 6>5 X maxim=6 poz=1
            //facem intersch
            // i=2 : maxim=2 poz=2
            //      5>2 X maxim=5 poz=1
            //facem intersch
            //memorez cea mai mare valoare de la stanga elementului curent
            if(v[j]>maxim)
            {
                maxim=v[j];
                poz_max = j;
            }
        }
        //interschimbare maxim cu element curent
        aux = v[i];
        v[i]= v[poz_max];
        v[poz_max]= aux;
        // 1 2 3 4 5
        // 7 2 5 6 8
        // 6 2 5 7 8
        // 5 2 6 7 8
        // 2 5 6 7 8
    }
    return 0;
}