Ejercicio 38

#include <iostream>
#include "Ordenar.h"

using namespace std;

// método para mostrar los elementos del vector 
void mostrarVector(Ordenar *obj)
{
    cout << "============ ELEMENTOS DEL VECTOR ============" << endl;
    for (int i = 0; i < obj->getNumElementos(); i++)
    {
        cout << "Posicion " << i << ": " << obj->getVectorDatos(i) << endl;
    }
}

int main(void)
{
    // se crea un objeto de la clase Convertir (Instanciaciación) 
    Ordenar *obj = new Ordenar();
    // declaramos una variable de tipo entero llamada num_elementos  
    int num_elementos;
    // pedimos al usuario que digite el tamaño del vector 
    cout << "Digite el numero de elementos del vector" << endl;
    cout << ">> ";
    // guardamos el tamaño en la variable num_elementos  
    cin >> num_elementos;
    // encapsulamos la variable num_elementos  
    obj->setNumElementos(num_elementos);
    // llamamos al metodo que creara el vector crearVector()  
    obj->crearVector();
    // recorremos el vector con el ciclo for  
    for(int i = 0; i < obj->getNumElementos(); i++)
    {
        // declaramos una variable de tipo entero llamada dato  
        int dato;
        // pedimos al usuario que digite el elemento de cada posicion del vector 
        cout << "Digite el elemento de la posicion " << i << endl;
        cout << ">> ";
        // guardamos cada elemento temporalmente en la variable dato  
        cin >> dato;
        // encapsulamos la variable dato en la posicion actual de i  
        obj->setVectorDatos(i, dato);
    }

    // cuando se haya llenado el vector, se mostrara el mensaje 
    cout << "Vector lleno." << endl;

    // llamamos al metodo mostrarVector() y le pasamos como parametro el objeto, obj para mostrar los datos actuales del vector 
    mostrarVector(obj);
    // declaramos una variable de tipo entero llamada opcion  
    int opcion;
    // ahora el usuario debera digitar la opcion con la que desea ordenar sus datos del vector 
    cout << "====== Seleccione el Metodo de Ordenamiento ======" << endl << endl;
    cout << "1. Ordenamiento Burbuja" << endl;
    cout << "2. Ordenamiento por Intercambio" << endl;
    cout << "3. Ordenamiento por Seleccion" << endl;
    cout << "4. Ordenamiento por Shell" << endl;
    cout << "5. Ordenar por QuickSort" << endl;
    cout << ">> ";
    // se guarda en la variable opcion  
    cin >> opcion;
    // dependiendo de la opcion digitada, el condicional switch eligira el metodo para ordenar y mostrar los elemento del vector 
    switch(opcion)
    {
        case 1:
            obj->ordenarBurbuja();
            mostrarVector(obj);
            break;
        case 2:
            obj->ordenarIntercambio();
            mostrarVector(obj);
            break;
        case 3:
            obj->ordenarSeleccion();
            mostrarVector(obj);
            break;
        case 4:
            obj->ordenarShell();
            mostrarVector(obj);
            break;
        case 5:
            obj->ordenarQuickSort(0, obj->getNumElementos()-1);
            mostrarVector(obj);
            break;
        default:
            cout << "¡No selecciono una opción valida entre 1 y 5!" << endl;
            break;
    }
}

#ifndef ORDENAR_H
#define ORDENAR_H


class Ordenar
{
    public:
        Ordenar();
        virtual ~Ordenar();
        // se crean los metodos publicos: 
        void crearVector();
        void setVectorDatos(int p, int dato);
        int getVectorDatos(int p);
        void setNumElementos(int num);
        int getNumElementos();
        void cambiar(int p1, int p2);
        void ordenarBurbuja();
        void ordenarIntercambio();
        int posicionMenor(int inicio);
        void ordenarSeleccion();
        void ordenarShell();
        void ordenarQuickSort(int primero, int ultimo);
    protected:

    private:
        // se crean los atributos privados: 
        int *vectorDatos;
        int numElementos;
};

#endif // ORDENAR_H 

#include "Ordenar.h"
#include <iostream>

using namespace std;

Ordenar::Ordenar()
{
    // al inicializar el constructor se definiran los valores iniciales de los atributos 
    vectorDatos = NULL;
    numElementos = 0;
}

Ordenar::~Ordenar()
{
    //dtor 
}

// método para crear el vector en tiempo de ejecución, posteriormente se asignara su tamaño 
void Ordenar::crearVector()
{
    vectorDatos = new int[numElementos];
}

// métodos Setter y Getters de los atributos de la clase 
void Ordenar::setVectorDatos(int p, int dato)
{
    vectorDatos[p] = dato;
}

int Ordenar::getVectorDatos(int p)
{
    return vectorDatos[p];
}

void Ordenar::setNumElementos(int num)
{
    numElementos = num;
}

int Ordenar::getNumElementos()
{
    return numElementos;
}

// método que permite intercambiar los elementos de dos posiciones del vector 
void Ordenar::cambiar(int p1, int p2)
{
    int temp;
    temp = getVectorDatos(p1);
    setVectorDatos(p1, getVectorDatos(p2));
    setVectorDatos(p2, temp);
}

// método de ordenamiento Burbuja, este método compara elementos de la posición j 
// con la posición j+1 , es decir compara dos posiciones seguidas o continuas del vector 
void Ordenar::ordenarBurbuja()
{
    for (int i = 0; i < getNumElementos(); i++)
    {
        for (int j = 0; j < getNumElementos()-2; j++)
        {
            // ordeno de menor a mayor, si se quiere hacer de mayor a menor simplemente cambie el signo, aquí se
            // compara si el elemento de la izquierda j es mayor que el elemento contiguo de la derecha j+1 
            // si se cumple la condición los intercambia 
            if (getVectorDatos(j) > getVectorDatos(j+1))
            {
                // para hacer el intercambio en los elementos se llama al método cambiar 
                cambiar(j, j+1);
            }
        }
    }
}

// método de ordenamiento por intercambio, este método compara un elemento de la
// posición i con todos los que le siguen, es decir con los de la posición i+1 , i+2 , i+3 ... i+n  
void Ordenar::ordenarIntercambio()
{
    for (int i = 0; i < getNumElementos(); i++)
    {
        for (int j = i+1; j < getNumElementos(); j++)
        {
            // ordeno de menor a mayor, si se quiere hacer de mayor a menor simplemente cambie el signo, aquí compara
            // si el elemento de la posición i a la izquierda es mayor que el elemento de la posición j ubicado hacia la derecha 
            if (getVectorDatos(i) > getVectorDatos(j))
            {
                cambiar(i, j);
            }
        }
    }
}

// método auxiliar para buscar la posición del elemento mas pequeño del vector y realizar el intercambio 
int Ordenar::posicionMenor(int inicio)
{
    // variable para establecer la posición en el vector del elemento menor 
    int posMenor;
    // variable para representar el elemento menor del vector 
    int menorElemento;
    posMenor = inicio;
    // a continuación se asume que el elemento mas pequeño del vector esta en la primera posición 
    menorElemento = getVectorDatos(inicio);
    for (int i = inicio+1; i < getNumElementos(); i++)
    {
        // se compara si el elemento de la posición i es menor que el elemento menor 
        if (getVectorDatos(i) < menorElemento)
        {
            menorElemento = getVectorDatos(i);
            posMenor = i;
        }
    }
    // se devuelve la posición en donde esta el elemento menor del vector para realizar el intercambio hacia la primera posición 
    return posMenor;
}

// método que ordena el vector, llamando al método auxiliar posicionMenor() para realizar el intercambio 
void Ordenar::ordenarSeleccion()
{
    for (int i = 0; i < getNumElementos(); i++)
    {
        cambiar(i, posicionMenor(i));
    }
}

// los siguientes metodos de ordenamientos son algo complejos por lo que recomendamos buscar mas informacion adicional para entender 
void Ordenar::ordenarShell()
{
    int n, cont;
    n = (getNumElementos()-1)/2;
    while (n != 0)
    {
        cont = 1;
        while (cont != 0)
        {
            cont = 0;
            for(int i = n; i < getNumElementos(); i++)
            {
                if(getVectorDatos(i-n) > getVectorDatos(i))
                {
                    cambiar(i, i-n);
                    cont = cont + 1;
                }
            }
        }
        n = n/2;
    }
}

void Ordenar::ordenarQuickSort(int primero, int ultimo)
{
    int i, j, centro;
    int pivote;
    centro = (primero + ultimo)/2;
    pivote = getVectorDatos(centro);
    i = primero;
    j = ultimo;
    do
    {
        while ((i <= j) && (getVectorDatos(i) < pivote))
        {
            i = i + 1;
        }
        while((i <= j) && (getVectorDatos(j) > pivote))
        {
            j = j - 1;
        }
        if(i <= j)
        {
            cambiar(i, j);
            i = i + 1;
            j = j - 1;
        }
    }
    while (i <= j);

    if(primero < j)
    {
        ordenarQuickSort(primero, j);
    }
    if(i < ultimo)
    {
        ordenarQuickSort(i, ultimo);
    }
}

// se importa paquete JOptionPane para dibujar un cuadro de dialogo en pantalla
// que muestre información o para llenar información. 

public class Main
{
    // método para mostrar los elementos del vector 
    public static void mostrarVector(Ordenar obj)
    {
        String datosVector = "";
        for (int i = 0; i < obj.getNumElementos(); i++)
        {
            datosVector = datosVector + String.valueOf("Posición " + i + ": " + obj.getVectorDatos(i) + "\n");
        }
        JOptionPane.showMessageDialog(null, "============ ELEMENTOS DEL VECTOR ============" + "\n" + datosVector);
    }
    public static void main(String[] args)
    {
        // se crea un objeto de la clase Convertir (Instanciaciación) 
        Ordenar obj = new Ordenar();
        // declaramos una variable de tipo entero llamada num_elementos y pedimos al usuario que digite el tamaño del vector 
        int num_elementos = Integer.parseInt(JOptionPane.showInputDialog(null, "Digite el Número de Elementos del Vector:"));
        // encapsulamos la variable num_elementos  
        obj.setNumElementos(num_elementos);
        // llamamos al metodo que creara el vector crearVector()  
        obj.crearVector();
        // recorremos el vector con el ciclo for  
        for(int i = 0; i < obj.getNumElementos(); i++)
        {
            // pedimos al usuario que digite el elemento de cada posicion del vector 
            int dato = Integer.parseInt(JOptionPane.showInputDialog(null, "Digitar Elemento de la Posición " + i + ": "));
            // encapsulamos la variable dato en la posicion actual de i  
            obj.setVectorDatos(i, dato);
        }
        // cuando se haya llenado el vector, se mostrara el mensaje 
        JOptionPane.showMessageDialog(null,"Vector Lleno");
        // llamamos al metodo mostrarVector() y le pasamos como parametro el objeto, obj para mostrar los datos actuales del vector 
        mostrarVector(obj);
        // declaramos una variable de tipo entero llamada opcion , ahora el usuario debera digitar la opcion con la que desea ordenar sus datos del vector 
        int opcion = Integer.parseInt(JOptionPane.showInputDialog("====== Seleccione el Metodo de Ordenamiento ====== \n" +
                "1. Ordenamiento Burbuja \n" +
                "2. Ordenamiento por Intercambio \n" +
                "3. Ordenamiento por Seleccion \n" +
                "4. Ordenamiento por Shell \n" +
                "5. Ordenar por QuickSort"));
        // dependiendo de la opcion digitada, el condicional switch eligira el metodo para ordenar y mostrar los elemento del vector 
        switch(opcion)
        {
            case 1:
                obj.ordenarBurbuja();
                mostrarVector(obj);
                break;
            case 2:
                obj.ordenarIntercambio();
                mostrarVector(obj);
                break;
            case 3:
                obj.ordenarSeleccion();
                mostrarVector(obj);
                break;
            case 4:
                obj.ordenarShell();
                mostrarVector(obj);
                break;
            case 5:
                obj.ordenarQuickSort(0, obj.getNumElementos()-1);
                mostrarVector(obj);
                break;    
            default:
                JOptionPane.showMessageDialog(null, "¡No selecciono una opción valida entre 1 y 5!");
                break;
        }
    }
}

public class Ordenar
{
    // se crean los atributos privados: 
    private int vectorDatos[];
    private int numElementos;
    
    public Ordenar()
    {
        // al inicializar el constructor se definiran los valores iniciales de los atributos 
        vectorDatos = null;
        numElementos = 0;
    }
    
    // método para crear el vector en tiempo de ejecución, posteriormente se asignara su tamaño 
    public void crearVector()
    {
        vectorDatos = new int[numElementos];
    }
    
    // métodos Setter y Getters de los atributos de la clase 
    public void setVectorDatos(int p, int dato)
    {
        vectorDatos[p] = dato;
    }

    public int getVectorDatos(int p)
    {
        return vectorDatos[p];
    }
    
    public void setNumElementos(int num)
    {
        numElementos = num;
    }
    
    public int getNumElementos()
    {
        return numElementos;
    }
    
    // método que permite intercambiar los elementos de dos posiciones del vector 
    public void cambiar(int p1, int p2)
    {
        int temp;
        temp = getVectorDatos(p1);
        setVectorDatos(p1, getVectorDatos(p2));
        setVectorDatos(p2, temp);
    }
    
    // método de ordenamiento Burbuja, este método compara elementos de la posición j 
    // con la posición j+1 , es decir compara dos posiciones seguidas o continuas del vector 
    public void ordenarBurbuja()
    {
        for (int i = 0; i < getNumElementos(); i++)
        { 
            for (int j = 0; j < getNumElementos()-2; j++)
            {
                // ordeno de menor a mayor, si se quiere hacer de mayor a menor simplemente cambie el signo, aquí se
                // compara si el elemento de la izquierda j es mayor que el elemento contiguo de la derecha j+1 
                // si se cumple la condición los intercambia 
                if (getVectorDatos(j) > getVectorDatos(j+1))
                {
                    // para hacer el intercambio en los elementos se llama al método cambiar 
                    cambiar(j, j+1);
                }
            }
        }
    }
    
    // método de ordenamiento por intercambio, este método compara un elemento de la
    // posición i con todos los que le siguen, es decir con los de la posición i+1, i+2, i+3... i+n  
    public void ordenarIntercambio()
    {
        for (int i = 0; i < getNumElementos(); i++)
        {
            for (int j = i+1; j < getNumElementos(); j++)
            {
                // ordeno de menor a mayor, si se quiere hacer de mayor a menor simplemente cambie el signo, aquí compara
                // si el elemento de la posición i a la izquierda es mayor que el elemento de la posición j ubicado hacia la derecha 
                if (getVectorDatos(i) > getVectorDatos(j))
                {
                    cambiar(i, j);
                }
            }
        }
    }
    
    // método auxiliar para buscar la posición del elemento mas pequeño del vector y realizar el intercambio 
    public int posicionMenor(int inicio)
    {
        // variable para establecer la posición en el vector del elemento menor 
        int posMenor;
        // variable para representar el elemento menor del vector 
        int menorElemento;
        posMenor = inicio;
        // a continuación se asume que el elemento mas pequeño del vector esta en la primera posición 
        menorElemento = getVectorDatos(inicio);
        for (int i = inicio+1; i < getNumElementos(); i++)
        {
            // se compara si el elemento de la posición i es menor que el elemento menor 
            if (getVectorDatos(i) < menorElemento)
            {
                menorElemento = getVectorDatos(i);
                posMenor = i;
            }
        }
        // se devuelve la posición en donde esta el elemento menor del vector para realizar el intercambio hacia la primera posición 
        return posMenor;
    }
    
    // método que ordena el vector, llamando al método auxiliar posicionMenor() para realizar el intercambio 
    public void ordenarSeleccion()
    {
        for (int i = 0; i < getNumElementos(); i++)
        {
            cambiar(i, posicionMenor(i));
        }
    }
    
    // los siguientes metodos de ordenamientos son algo complejos por lo que recomendamos buscar mas informacion adicional para entender 
    public void ordenarShell()
    {
        int n, cont;
        n = (getNumElementos()-1)/2;
        while (n != 0)
        {
            cont = 1;
            while (cont != 0)
            {
                cont = 0;
                for(int i = n; i < getNumElementos(); i++)
                {
                    if(getVectorDatos(i-n) > getVectorDatos(i))
                    {
                        cambiar(i, i-n);
                        cont = cont + 1;
                    }
                }
            }
            n = n/2;
        }
    }
    
    public void ordenarQuickSort(int primero, int ultimo)
    {
        int i, j, centro;
        int pivote;
        centro = (primero + ultimo)/2;
        pivote = getVectorDatos(centro);
        i = primero;
        j = ultimo;
        do
        {
            while ((i <= j) && (getVectorDatos(i) < pivote))
            {
                i = i + 1;
            }
            while((i <= j) && (getVectorDatos(j) > pivote))
            {
                j = j - 1;
            }
            if(i <= j)
            {
                cambiar(i, j);
                i = i + 1;
                j = j - 1;
            }
        }
        while (i <= j);
        
        if(primero < j)
        {
            ordenarQuickSort(primero, j);
        }
        if(i < ultimo)
        {
            ordenarQuickSort(i, ultimo);
        }
    }
}