// lab08.cpp  (c) 2000 adolfo@di-mare.com

/** \file  lab08.cpp
    \brief Métodos de ordenamiento \c Burbuja(), \c Seleccion() e \c Insercion().

    Este programa implementa y usa los siguientes métodos de
    ordenamiento de vectores:
    - \c Burbuja()
    - \c Seleccion()
    - \c Insercion()

    \author Adolfo Di Mare <adolfo@di-mare.com>
    \date   2000
*/

#include <iostream> // #include <iostream.h>
#include <iomanip>  // setw()
#include <bool.h>

/// Graba en \c "cout" los primeros \c "n" valores almacenados en \c V[].
/// - Pone un punto "." de marca en la posición \c V[mk].
template <class T>
void Despliega( T  *V, const unsigned mk, const unsigned n ) {
    const unsigned ancho = 4;

    cout << "\n[MRK=" << mk << "] ==>";
    for (unsigned i=0; i<n; ++i) {
        if (i==mk && i>0) {
            cout << '.' << setw(ancho-1) << V[i];
        } else {
            cout << setw(ancho) << V[i];
        }
    }
    if (mk==n) {
        cout << '.';
    }
} // Despliega()

/** Ordena ascendentemente el vector \c V[] utilizando el método
    de la burbuja.
    - La cantidad de valores almacenados en \c V[] es \c "n".
    \pre
     La clase \c "T", contenida en el vector \c V[], debe tener
     definidas las siguientes operaciones:
     - <code> bool operator<< (T, T) </code>
     - <code> T.operator=(T) <code>
*/
template <class T>
void Burbuja(T V[], const unsigned n) {
    Despliega(V, n, n);
    for (unsigned i=n; i>0; ) {
        --i;
        for (unsigned j=0; j<i; ++j) {
            if (V[j+1] < V[j]) {
                T temp; temp = V[j];
                V[j] = V[j+1];      // intercambiar V[j] <==> V[j+1]
                V[j+1] = temp;
            }
        }
        Despliega(V, i, n);
    }
} // Burbuja()

/** Ordena ascendentemente el vector \c V[] utilizando el método
    de selección.
    - La cantidad de valores almacenados en \c V[] es \c "n".
    \pre
     La clase \c "T", contenida en el vector \c V[], debe tener
     definidas las siguientes operaciones:
     - <code> bool operator<< (T, T) </code>
     - <code> T.operator=(T) <code>
*/
template <class T>
void Seleccion(T V[], const unsigned n) {
    Despliega(V, n, n);
    for (unsigned i=0; i<n; ++i) {
        unsigned mrk = i;
        for (unsigned j=i+1; j<n; ++j) {
            if (V[j] < V[mrk]) {
                mrk = j;
            }
        }
        if (i!=mrk) {
            T temp = V[i];
            V[i] = V[mrk];      // intercambiar V[j] <==> V[mrk]
            V[mrk] = temp;
        }
        Despliega(V, i+1, n);
    }
} // Seleccion()

/** Ordena ascendentemente el vector \c V[] utilizando el método
    de inserción.
    - La cantidad de valores almacenados en \c V[] es \c "n".
    \pre
     La clase \c "T", contenida en el vector \c V[], debe tener
     definidas las siguientes operaciones:
     - <code> bool operator<< (T, T) </code>
     - <code> T.operator=(T) <code>
*/
template <class T>
void Insercion(T V[], const unsigned n) {
    T min_val;

    Despliega(V, (const unsigned)1, n);
    for (int i=1; i<n; i++) {
        min_val = V[i];
        int j = i;
        while ((j > 0) && (V[j-1] > min_val)) {
            V[j] = V[j-1];
            j = j-1;
        }
        V[j] = min_val;
        Despliega(V, (const unsigned)i+1, n);
    }
}

#if OLD
template <class T>
void Insercion(T V[], const unsigned n) {
    // Primero crea el "centinela" que es el más pequeño del vector
    unsigned i,j,centinela = 0;
    for (i=1; i<n;++i) {
        if ( V[i] < V[centinela] ) {
            centinela = i;
        }
    }
    T temp = V[0];         // intercambiar V[0] <==> V[centinela]
    V[0] = V[centinela];
    V[centinela] = temp;   // ahora V[0] es el menor del vector
    Despliega(V, i-i, n);  // (i-i)==0 ==> para que compile con BC++ v3.1

    for (i=1; i<n; ++i) {
        j = i;
        while (V[j] < V[j-1]) {
            T temp = V[j];     // intercambiar V[j] <==> V[j-1]
            V[j] = V[j-1];
            V[j-1] = temp;

            j = j-1;
        }
        Despliega(V, i, n);
    }
}
#endif

#define DIM(v) ( sizeof(v) / sizeof(*v) )

/// Programa principal.
int main() {
#if 1
    {   int   Vint[]   = { 5,2,4,1,7,3,6,8 };
        float Vfloat[] = { 5,2,4,1,7,3,6,8 };
        int   Rint[]   = { 8,7,6,5,4,3,2,1 };
        int   Mint[]   = { 8,2,4,1,7,3,6,5 };
        const unsigned DIMint  = DIM(Vint);
        const unsigned DIMfloat= DIM(Vfloat);

        cout << endl << endl <<"Burbuja";
        cout << endl; Burbuja(Vint,     DIMint);
        cout << endl; Burbuja(Rint,     DIMint);
        cout << endl; Burbuja(Mint,     DIMint);
        cout << endl; Burbuja(Vfloat,   DIMfloat);
    }

    {   int   Vint[]   = { 5,2,4,1,7,3,6,8 };
        float Vfloat[] = { 5,2,4,1,7,3,6,8 };
        int   Rint[]   = { 8,7,6,5,4,3,2,1 };
        int   Mint[]   = { 8,2,4,1,7,3,6,5 };
        const unsigned DIMint  = DIM(Vint);
        const unsigned DIMfloat= DIM(Vfloat);

        cout << endl << endl <<"Seleccion";
        cout << endl; Seleccion(Vint,   DIMint);
        cout << endl; Seleccion(Rint,   DIMint);
        cout << endl; Seleccion(Mint,   DIMint);
        cout << endl; Seleccion(Vfloat, DIMfloat);
    }
#endif
    {   int   Vint[]   = { 5,2,4,1,7,3,6,8 };
        float Vfloat[] = { 5,2,4,1,7,3,6,8 };
        int   Rint[]   = { 8,7,6,5,4,3,2,1 };
        int   Mint[]   = { 8,2,4,1,7,3,6,5 };
        const unsigned DIMint  = DIM(Vint);
        const unsigned DIMfloat= DIM(Vfloat);

        cout << endl << endl <<"Insercion";
        cout << endl; Insercion(Vint,   DIMint);
        cout << endl; Insercion(Rint,   DIMint);
        cout << endl; Insercion(Mint,   DIMint);
        cout << endl; Insercion(Vfloat, DIMfloat);
    }

    return 0;
} // main()

// EOF: lab08.cpp