Elabore un algoritmo que permita ordenar los números de un vector, para ello se debe pedir al usuario el tamaño que tendrá el vector, ademas el usuario deberá escoger alguno de los siguientes métodos para ordenarlos:
- Ordenamiento por Burbuja
- Ordenamiento por Intercambio
- Ordenamiento por Selección
- Ordenamiento por Shell
- Ordenamiento por QuickSort
#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);
}
}
}
