Unidad 6: Ordenamientos Internos

Introducción:

En esta Unidad explicaremos 4 algoritmos para el Ordenamiento de Arreglos en Memoria Ram.

A continuación mencionaremos los diferentes métodos para ordenar:

  1. Burbuja
  2. ShellSort
  3. RadixSort
  4. QuickSort

Burbuja

Definición:

El método de la burbuja es una comparación lineal con cada uno de los elementos, el elemento que sea menor contra el que se esta comparado intercambiaran posiciones. Este método no es recomendado para grandes comparaciones, ya que es un proceso muy lento y requiere de una gran cantidad de Memoria Ram.

Programa:

#include <conio.h>
#include <iostream.h>
class Lista
{
private:
int Lista[10],N;
public:
Lista()
{
for(int i=0;i<10;i++)
Lista[i]=0;
N=0;
}
void Burbuja(void)
{
if(N!=0)
{
int i,j,aux;
for(i=0;i<9;i++)
for(j=i+1;j<10;j++)
if(Lista[i]<Lista[j])
{
aux=Lista[i];
Lista[i]=Lista[j];
Lista[j]=aux;
}
cout<<"Lista Ordenada..."<<endl;
return;
}
cout<<"Lista Vacia..."<<endl;
}
void Busqueda(int Elem)
{
if(N!=0)
{
for(int i=0;i<N;i++)
if(Lista[i]==Elem)
{
cout<<"El "<<Elem<<" esta en la Lista"<<endl;
return;
}
}
cout<<"Lista Vacia..."<<endl;
return;
}
void Insertar(int Elem)
{
if(N<10)
{
Lista[N]=Elem;
N++;
cout<<"El "<<Elem<<" fue Insertado"<<endl;
return;
}
cout<<"Lista Llena... Imposible Insertar"<<endl;
return;
}
void Eliminar(int Elem)
{
if(N!=0)
{
for(int i=0;i<N;i++)
if(Lista[i]==Elem)
{
Lista[i]=0;
Burbuja();
N--;
return;
}
}
cout<<"Lista Vacia... Imposible Eliminar..."<<endl;
return;
}
void Recorrido()
{
if(N!=0)
{
for(int i=0;i<N;i++)
cout<<Lista[i]<<endl;
}
cout<<"Lista Vacia..."<<endl;
}
}tec;
main()
{
int op=0,res;
while(op!=6)
{
clrscr();
cout<<"\n1) Recorrido\n2) Ordenar\n3) Busqueda\n4) Insercion\n5) Eliminar un Dato\n6) Salir"<<endl;
gotoxy(1,1);
cout<<"Que deseas hacer: ";
cin>>op;
gotoxy(1,10);
switch (op)
{
case 1:
tec.Recorrido();
break;
case 2:
tec.Burbuja();
break;
case 3:
cout<<"Que Numero de Control deseas buscar?"<<endl;
cin>>res;
tec.Busqueda(res);
break;
case 4:
cout<<"Que Numero Deseas Insertar?"<<endl;
cin>>res;
tec.Insertar(res);
break;
case 5:
cout<<"Que Numero de Control deseas Eliminar?"<<endl;
cin>>res;
tec.Eliminar(res);
break;
case 6:
cout<<"Salida...";
break;
default:
cout<<"Opcion Erronea"<<endl;
break;
}
getch();
}
}

ShellSort

Definición:

Esta forma de ordenación es muy parecida a la ordenación con burbuja. La diferencia es que no es una comparación lineal, sino que trabaja con una segmentación entre los datos. Por lo tanto es un buen método, pero no el mejor para implementarlos en grandes arreglos.

Programa:

#include <conio.h>
#include <iostream.h>
class Lista
{
private:
int Lista[10],N;
public:
Lista()
{
for(int i=0;i<10;i++)
Lista[i]=0;
N=0;
}
void ShellSort(void)
{
if(N!=0)
{
int salto,aux,i;
for(salto=6/2;salto!=0;salto/=2)
{
for(i=salto;i<6;i++)
if(Lista[i-salto]<Lista[i])
{
aux=Lista[i];
Lista[i]=Lista[i-salto];
Lista[i-salto]=aux;
}
}
cout<<"Lista Ordenada..."<<endl;
return;
}
cout<<"Lista Vacia..."<<endl;
}
void Busqueda(int Elem)
{
if(N!=0)
{
for(int i=0;i<N;i++)
if(Lista[i]==Elem)
{
cout<<"El "<<Elem<<" esta en la Lista"<<endl;
return;
}
}
cout<<"Lista Vacia..."<<endl;
return;
}
void Insertar(int Elem)
{
if(N<10)
{
Lista[N]=Elem;
N++;
cout<<"El "<<Elem<<" fue Insertado"<<endl;
return;
}
cout<<"Lista Llena... Imposible Insertar"<<endl;
return;
}
void Eliminar(int Elem)
{
if(N!=0)
{
for(int i=0;i<N;i++)
if(Lista[i]==Elem)
{
Lista[i]=0;
ShellSort();
N--;
return;
}
}
cout<<"Lista Vacia... Imposible Eliminar..."<<endl;
return;
}
void Recorrido()
{
if(N!=0)
{
for(int i=0;i<N;i++)
cout<<Lista[i]<<endl;
}
cout<<"Lista Vacia..."<<endl;
}
}tec;
main()
{
int op=0,res;
while(op!=6)
{
clrscr();
cout<<"\n1) Recorrido\n2) Ordenar\n3) Busqueda\n4) Insercion\n5) Eliminar un Dato\n6) Salir"<<endl;
gotoxy(1,1);
cout<<"Que deseas hacer: ";
cin>>op;
gotoxy(1,10);
switch (op)
{
case 1:
tec.Recorrido();
break;
case 2:
tec.ShellSort();
break;
case 3:
cout<<"Que Numero de Control deseas buscar?"<<endl;
cin>>res;
tec.Busqueda(res);
break;
case 4:
cout<<"Que Numero Deseas Insertar?"<<endl;
cin>>res;
tec.Insertar(res);
break;
case 5:
cout<<"Que Numero de Control deseas Eliminar?"<<endl;
cin>>res;
tec.Eliminar(res);
break;
case 6:
cout<<"Salida...";
break;
default:
cout<<"Opcion Erronea"<<endl;
break;
}
getch();
}
}

RadixSort

Definición:

Este ordenamiento se basa en los valores de los dígitos reales en las representaciones de posiciones de los números que se ordenan. Es decir… toma un número y lo descompone en sus unidades, decenas, centenas, etc… de esta manera va determinando las posiciones de cada uno de ellos.

Programa:

#include <math.h>
#include <conio.h>
#include <iostream.h>
class Lista
{
private:
int Lista[10],Temp[10],Elementos,N;
public:
Lista()
{
for(int i=0;i<10;i++)
Lista[i]=0;
N=9;
Elementos=0;
}
void Ordenar()
{
if(N!=9)
{
RadixSort(0,Elementos,Lista,Temp);
RadixSort(1,Elementos,Temp,Lista);
RadixSort(2,Elementos,Lista,Temp);
RadixSort(3,Elementos,Temp,Lista);
cout<<"Lista Ordenada..."<<endl;
return;
}
cout<<"Lista Vacia..."<<endl;
}
void RadixSort (int byte, int N, int *fuente, int *dest)
{
int cont[256];
int ind[256];
int i;
memset(cont,0,sizeof(cont));
for(i=0;i<10;i++)
cont[((fuente[i])>>(byte*8))&0xff]++;
ind[0]=0;
for(i=1;i<256;i++)
ind[i]=ind[i-1]+cont[i-1];
for(i=0;i<10;i++)
dest[ind[((fuente[i])>>(byte*8))&0xff]++]=fuente[i];
}
void Busqueda(int Elem)
{
if(N!=9)
{
for(int i=0;i<N;i++)
if(Lista[i]==Elem)
{
cout<<"El "<<Elem<<" esta en la Lista"<<endl;
return;
}
}
cout<<"Lista Vacia..."<<endl;
return;
}
void Insertar(int Elem)
{
if(N!=-1)
{
Elementos++;
Lista[N]=Elem;
N--;
cout<<"El "<<Elem<<" fue Insertado"<<endl;
return;
}
cout<<"Lista Llena... Imposible Insertar"<<endl;
return;
}
void Eliminar(int Elem)
{
if(N!=9)
{
for(int i=0;i<N;i++)
if(Lista[i]==Elem)
{
Lista[i]=0;
Ordenar();
N++;
Elementos--;
return;
}
}
cout<<"Lista Vacia... Imposible Eliminar..."<<endl;
return;
}
void Recorrido()
{
if(N!=9)
{
for(int i=9;i!=N;i--)
cout<<Lista[i]<<endl;
return;
}
cout<<"Lista Vacia..."<<endl;
}
}tec;
main()
{
int op=0,res;
while(op!=6)
{
clrscr();
cout<<"\n1) Recorrido\n2) Ordenar\n3) Busqueda\n4) Insercion\n5) Eliminar un Dato\n6) Salir"<<endl;
gotoxy(1,1);
cout<<"Que deseas hacer: ";
cin>>op;
gotoxy(1,10);
switch (op)
{
case 1:
tec.Recorrido();
break;
case 2:
tec.Ordenar();
break;
case 3:
cout<<"Que Numero de Control deseas buscar?"<<endl;
cin>>res;
tec.Busqueda(res);
break;
case 4:
cout<<"Que Numero Deseas Insertar?"<<endl;
cin>>res;
tec.Insertar(res);
break;
case 5:
cout<<"Que Numero de Control deseas Eliminar?"<<endl;
cin>>res;
tec.Eliminar(res);
break;
case 6:
cout<<"Salida...";
break;
default:
cout<<"Opcion Erronea"<<endl;
break;
}
getch();
}
}

QuickSort

Definición:

Probablemente este será el mejor de los métodos que mencionamos en esta unidad. Este divide aleatoriamente el arreglo para comparar si un elemento es mayor o menor. Dependiendo el resultado lo partirá ya sea por la izquierda o derecha, de esta forma se repite el procedimiento para ordenarlos.

Programa:

#include <conio.h>
#include <iostream.h>
class Lista
{
private:
int Lista[10],N;
public:
Lista()
{
for(int i=0;i<10;i++)
Lista[i]=0;
N=1;
}
int Dividir(int menor,int mayor)
{
int izq,dch,temp;
izq=menor;
dch=mayor;
while(izq<dch)
{
while(Lista[dch]>Lista[menor])
dch--;
while((izq<dch)&&(Lista[izq]<=Lista[menor]))
izq++;
if(izq<dch)
{
temp=Lista[izq];
Lista[izq]=Lista[dch];
Lista[dch]=temp;
}
}
temp=Lista[dch];
Lista[dch]=Lista[menor];
Lista[menor]=temp;
return dch;
}
void QuickSort(int menor,int mayor)
{
if(N!=1)
{
int medio;
if(menor<mayor)
{
medio=Dividir(menor,mayor);
QuickSort (menor,medio-1);
QuickSort (medio+1,mayor);
}
cout<<"Lista Ordenada..."<<endl;
}
cout<<"Lista Vacia..."<<endl;
}
void Busqueda(int Elem)
{
if(N!=0)
{
for(int i=0;i<N;i++)
if(Lista[i]==Elem)
{
cout<<"El "<<Elem<<" esta en la Lista"<<endl;
return;
}
}
cout<<"Lista Vacia..."<<endl;
return;
}
void Insertar(int Elem)
{
if(N<11)
{
Lista[10-N]=Elem;
N++;
cout<<"El "<<Elem<<" fue Insertado"<<endl;
return;
}
cout<<"Lista Llena... Imposible Insertar"<<endl;
return;
}
void Eliminar(int Elem)
{
if(N!=0)
{
for(int i=0;i<N;i++)
if(Lista[i]==Elem)
{
Lista[i]=0;
QuickSort(0,9);
N--;
return;
}
}
cout<<"Lista Vacia... Imposible Eliminar..."<<endl;
return;
}
void Recorrido()
{
if(N!=1)
{
for(int i=1;i!=N;i++)
cout<<Lista[10-i]<<endl;
}
cout<<"Lista Vacia..."<<endl;
}
}tec;
main()
{
int op=0,res;
while(op!=6)
{
clrscr();
cout<<"\n1) Recorrido\n2) Ordenar\n3) Busqueda\n4) Insercion\n5) Eliminar un Dato\n6) Salir"<<endl;
gotoxy(1,1);
cout<<"Que deseas hacer: ";
cin>>op;
gotoxy(1,10);
switch (op)
{
case 1:
tec.Recorrido();
break;
case 2:
tec.QuickSort(0,9);
break;
case 3:
cout<<"Que Numero de Control deseas buscar?"<<endl;
cin>>res;
tec.Busqueda(res);
break;
case 4:
cout<<"Que Numero Deseas Insertar?"<<endl;
cin>>res;
tec.Insertar(res);
break;
case 5:
cout<<"Que Numero de Control deseas Eliminar?"<<endl;
cin>>res;
tec.Eliminar(res);
break;
case 6:
cout<<"Salida...";
break;
default:
cout<<"Opcion Erronea"<<endl;
break;
}
getch();
}
}
Politica de Privacidad