//El programa fue compilado con Turbo C++ 3.0
//Descripcion de BUSQUEDA.CPP
//Los metodos de ordenacion que se desarrollaron son:
//Shell, Burbuja, Insercion, Sacudida,Seleccion y el Quicksort
//Nota.- El Quicksort se elaboro recursivamente e iterativamente.
//Los metodos de busqueda que se programaron fueron:
//Busqueda lineal y Busqueda Binaria.
//para que estos metodos funciones correctamente la lista debe estar ordenada.
#include <iostream.h>//para cout y cin
#include <conio.h> //para getch
#include <stdlib.h> //para exit y system
#define NUMEL 50
class BUSQUEDA{
private:
int izquierda,derecha,puntomedio,max,nums[NUMEL];
int elemento,ubicacion,ubicacion2,i;
public:
BusquedaBinaria(int[],int,int);
BusquedaLineal(int[],int,int);
MenuMain(void);
void Pedir(int *,int);
};
class ORDENACION{
private:
int min,indicemin,temp,movimientos;
int i,j,mitad,x;
int inter,opc;
int a[5];
OrdRap(int*,int,int);
void qs(int *,int,int);
public:
void Quicksort_Iterativo(int[],int);
Quicksort(int*,int);
Seleccion(int*,int);
Burbuja(int*,int);
Shell(int*,int);
Sacudida(int*,int);
Insercion(int*,int);
void Pedir(int*,int);
void Visualiza(int*,int,int,int);
Elementos();
MenuMain(void);
Menu_Asc_Des(void);
};
int ORDENACION::Quicksort(int *num,int numel)
{
int mov=OrdRap(num,0,numel-1);
return mov;
}
ORDENACION::OrdRap(int *num,int inf,int sup)
{
register int izq,der;
movimientos=0;
izq=inf; der=sup;
mitad=num[(izq+der)/2];
do{
while(num[izq]<mitad && izq < sup) izq++; movimientos++;
while(mitad<num[der] && der > inf) der--; movimientos++;
if(izq<=der){
x=num[izq],num[izq]=num[der],num[der]=x;
izq++; der--; movimientos++;
}
}while(izq<=der);
if(inf<der) OrdRap(num,inf,der);
if(izq<sup) OrdRap(num,izq,sup);
return movimientos;
}
void ORDENACION::Quicksort_Iterativo(int *num,int numel)
{
qs(num,0,numel-1);
}
void ORDENACION::qs(int *num,int inf,int sup)
{
struct TipoPila{
int inf,sup;
}Pila[NUMEL];
register int izq,der;
int mitad,x,p;
p=1,Pila[p].inf=inf,Pila[p].sup=sup;
do{
inf=Pila[p].inf,sup=Pila[p].sup,p--;
do{
izq=inf; der=sup;
mitad=num[(izq/der)/2];
do{
while(num[izq] < mitad && izq < sup) izq++;
while(mitad < num[der] && der > inf) der--;
if(izq<=der){
x=num[izq],num[izq]=num[der],num[der]=x;
izq++; der--;
}
}while(izq<=der);
if(izq<sup){
p++,Pila[p].inf=izq,Pila[p].sup=sup;
}
sup=der;
}while(inf<der);
}while(p);
}
ORDENACION::Insercion(int *num,int numel)
{
movimientos=0;
for(i=1;i<numel;++i){
temp=num[i];
for(j=i-1;(j>=0)&&(temp<num[j]);j--)
num[j+1]=num[j];
num[j+1]=temp;
movimientos++;
}
return movimientos;
}
ORDENACION::Shell(int *num,int numel)
{
movimientos=0;
a[0]=9;a[1]=5;a[2]=3;a[3]=2;a[4]=1;
for(register int k=0;k<5;k++){
temp=a[k];
for(i=temp;i<numel;++i){
x=num[i];
for(j=i-temp;(x<num[j])&&(j>=0);j=j-temp)
num[j+temp]=num[j];
num[j+temp]=x;
}
movimientos++;
}
return movimientos;
}
ORDENACION::Sacudida(int *num,int numel)
{
movimientos=0;
do{
inter=0;
for(i=numel-1;i>0;--i){
if(num[i-1]>num[i]){
temp=num[i-1];
num[i-1]=num[i];
num[i]=temp;
inter=1;
movimientos++;
}
}
for(i=1;i<numel;++i){
if(num[i-1]>num[i]){
temp=num[i-1];
num[i-1]=num[i];
num[i]=temp;
inter=1;
movimientos++;
}
}
}while(inter);
return movimientos;
}
ORDENACION::Seleccion(int *num,int numel)
{
movimientos=0;
for(i=0;i<(numel-1);i++){
min=num[i];
indicemin=i;
for(j=i+1;j<numel;++j){
if(num[j]<min){
min=num[j];
indicemin=j;
}
}
if(min<num[i]){
temp=num[i];
num[i]=min;
num[indicemin]=temp;
movimientos++;
}
}
return movimientos;
}
ORDENACION::Burbuja(int *num,int numel)
{
movimientos=0;
for(i=0;i<numel-1;i++){
for(j=1;j<numel;j++){
if(num[j]<num[j-1]){
temp=num[j];
num[j]=num[j-1];
num[j-1]=temp;
movimientos++;
}
}
}
return movimientos;
}
int BUSQUEDA::MenuMain(void)
{
int opc;
while(opc<1 || opc > 3){
system("cls");
gotoxy(29,9);
cout<<"METODOS DE BUSQUEDA.";
gotoxy(32,10); cout<<"1. Busqueda Lineal.";
gotoxy(32,11); cout<<"2. Busqueda Binaria.";
gotoxy(32,12); cout<<"3. Salir.";
gotoxy(32,14); cout<<"opcion-> ";
cin>>opc;
}
return opc;
}
int ORDENACION::MenuMain(void)
{
int opc;
while(opc < 1 || opc > 7)
{
system("cls");
gotoxy(29,9); cout<<"METODOS DE ORDENACION\n";
gotoxy(33,10); cout<<"1. Burbuja";
gotoxy(33,11); cout<<"2. Insercion";
gotoxy(33,12); cout<<"3. Quicksort";
gotoxy(33,13); cout<<"4. Shell";
gotoxy(33,14); cout<<"5. Seleccion";
gotoxy(33,15); cout<<"6. Sacudida";
gotoxy(33,16); cout<<"7. Salir.";
gotoxy(33,18); cout<<"Opcion-> ";
cin>>opc;
}
return opc;
}
void BUSQUEDA::Pedir(int *num,int n)
{
int i;
system("cls");
for(i = 0; i < n; i++)
{
gotoxy(22, i + 1);
cout<<"Ingresa valor "<<i+1<<": ";
cin>>num[i];
}
}
void ORDENACION::Pedir(int *num,int n)
{
system("cls");
for(i = 0; i < n; i++)
{
gotoxy(22, i + 1);
cout<<"Ingresa valor "<<i+1<<": ";
cin>>num[i];
}
}
int ORDENACION::Menu_Asc_Des(void)
{
int opc;
while(opc < 1 || opc > 2){
system("cls");
gotoxy(29,9); cout<<"METODOS DE ORDENACION\n";
gotoxy(33,10); cout<<"1. Ascendente\n";
gotoxy(33,11); cout<<"2. Descendente\n";
gotoxy(33,12); cout<<"Opcion: ";
cin>>opc;
}
return(opc);
}
BUSQUEDA::BusquedaBinaria(int lista[],int tamanho,int clave)
{
izquierda=0;
derecha=tamanho-1;
while(izquierda<=derecha)
{
puntomedio=((izquierda+derecha)/2);
if(clave==lista[puntomedio])
{
return puntomedio;
}
else if (clave>lista[puntomedio])
izquierda=puntomedio+1;
else
derecha=puntomedio-1;
}
return -1;
}
BUSQUEDA::BusquedaLineal(int lista[],int tamanho,int clave)
{
for(register int i=0;i<tamanho;i++)
{
if(lista[i]==clave)
return i;
}
return -1;
}
void ORDENACION::Visualiza(int *num, int numel,int opc,int mov)
{
if(numel >= 40) x = 1;
else x = 40 - numel;
do{
if(opc==1){
system("cls");
gotoxy(x-14,11); cout<<"Los movimientos que se hicieron son: ";
cout<<mov;
gotoxy(x-14,12); cout<<"Los Numeros Ordenados Ascendentemente son : ";
gotoxy(x,15);
for(i = 0; i<numel; i++)
cout<<num[i]<<" ";
getch();
}
if(opc==2){
system("cls");
gotoxy(x-14,11); cout<<"Los movimientos que se hicieron son: ";
cout<<mov;
gotoxy(x-14,12); cout<<"Los Numeros Ordenados Descendentemente son : "<<endl;
gotoxy(x,14);
for(int j = numel; j>0; j--)
cout<<num[j-1]<<" ";
getch();
}
}while(opc<1||opc>2);
}
void Ordenaciones(void)
{
int numel, opc,OPC;
char salir;
int num[NUMEL]={0};
ORDENACION p;
do{
system("cls");
gotoxy(19,12);
cout<<"Numero de elementos: ";
cin>>numel;
if(numel == 0){
cout<<"\n\t\t Numero no valido";
getch();
exit(1);
}
opc = p.MenuMain();
if(opc == 7){
exit(1);
}
p.Pedir(num, numel);
OPC=p.Menu_Asc_Des();
switch(opc)
{
case 1: int res=p.Burbuja(num, numel);
p.Visualiza(num, numel,OPC,res); break;
case 2: int res2=p.Insercion(num, numel);
p.Visualiza(num, numel,OPC,res2); break;
case 3: int res3=p.Quicksort(num, numel);
p.Visualiza(num, numel,OPC,res3); break;
case 4: int res4=p.Shell(num, numel);
p.Visualiza(num, numel,OPC,res4); break;
case 5: int res5=p.Seleccion(num, numel);
p.Visualiza(num, numel,OPC,res5); break;
case 6: int res6=p.Sacudida(num,numel);
p.Visualiza(num, numel,OPC,res6); break;
}
gotoxy(25,18);
cout<<"Desea volver a introducir datos (s/n): ";
cin>>salir;
}while(salir!='n');
system("cls");
}
void Busquedas(void)
{
BUSQUEDA b;
int numel, opc,clave;
char OPC;
int *num=NULL;
do{
system("cls");
gotoxy(19,12); cout<<"Numero de elementos: ";
cin>>numel;
if(numel == 0){
cout<<"\n\t\t Numero no valido";
getch();
exit(1);
}
opc = b.MenuMain();
if(opc == 3){
exit(1);
}
b.Pedir(num, numel);
switch(opc){
case 1: system("cls");
gotoxy(25,5);
cout<<"Numero a buscar: ";
cin>>clave;
int res1=b.BusquedaLineal(num,numel,clave);
if(res1==-1){
gotoxy(25,6);
cout<<"El Numero no se encontro en la lista.";
getch();
}
else{
gotoxy(25,6);
cout<<"El Numero si se encontro en la ubicacion del indice: "<<res1+1;
getch();
}
break;
case 2: system("cls");
gotoxy(25,5);
cout<<"Numero a buscar: ";
cin>>clave;
int res2=b.BusquedaBinaria(num,numel,clave);
if(res2==-1){
gotoxy(25,8);
cout<<"El Numero no se encontro en la lista.";
getch();
}
else{
gotoxy(25,8);
cout<<"El numero si se encontro en la ubicacion del indice: "<<res2+1;
getch();
}
break;
}
gotoxy(25,13);
cout<<"Desea Introducir mas datos (s/n): ";
cin>>OPC;
}while(OPC!='n');
system("cls");
}
int main(void)
{
int opc;
system("cls");
gotoxy(30,8); cout<<"Ordenacion y Busqueda.";
gotoxy(30,10); cout<<"1. Tipos de Ordenaciones.";
gotoxy(30,11); cout<<"2. Tipos de Busqueda.";
gotoxy(30,12); cout<<"3. Salir.";
gotoxy(30,14); cout<<"Opcion -> ";
cin>>opc;
switch(opc){
case 1: Ordenaciones();
break;
case 2: Busquedas();
break;
case 3: exit(0);
system("cls");
break;
}
return 0;
}
Todo codigos
gauss seidel ????
ResponderEliminar