ORDENAMIENTO
APLICACION
A pesar de que el ordenamiento es uno de los algoritmos más sencillos de implementar, su ordenO(n2) lo hace muy ineficiente para usar en listas que tengan más que un número reducido de elementos. Incluso entre los algoritmos de ordenamiento de orden O(n2), otros procedimientos como el ordenamiento por inserción son considerados más eficientes. Dada su simplicidad, el ordenamiento es utilizado para introducir el concepto de algoritmo de ordenamiento para estudiantes de ciencias de la computación. A pesar de esto, algunos investigadores como Owen Astrachan han criticado su popularidad en la enseñanza de ciencias de la computación, llegando a recomendar su eliminación de los planes de estudio. Sumado a esto, Jargon File, un libro ampliamente citado en la cultura hacker, lo denomina "el mal algoritmo genérico", y Donald Knuth, uno de los mayores expertos en ciencias de la computación, afirma que el ordenamiento "no parece tener nada para recomendar su uso, a excepción de un nombre pegajoso y el hecho de que conlleva a problemas teóricos interesantes". El ordenamiento es asintóticamente equivalente, en tiempos de ejecución, con el ordenamiento por inserción en el peor de los casos, pero ambos algoritmos difieren principalmente en la cantidad de intercambios que son necesarios. Resultados experimentales como los descubiertos por Astrachan han demostrado que el ordenamiento por inserción funciona considerablemente mejor incluso con listas aleatorias. Por esta razón, muchos libros de algoritmos modernos evitan usar el ordenamiento de burbuja, reemplazándolo por el ordenamiento por inserción. El ordenamiento interactúa vagamente con el hardware de las CPU modernas. Requiere al menos el doble de escrituras que el ordenamiento por inserción, el doble de pérdidas de cache, y asintóticamente más predicción de saltos. Varios experimentos de ordenamiento de cadenas en Java hechos por Astrachan muestran que el ordenamiento de burbuja es 5 veces más lento que el ordenamiento por inserción, y 40% más lento que el ordenamiento por selección.
EJEMPLO:
// USO DE VECTORES
#include<iostream>
#include<math.h>
using namespace std;
// ZONA DE DECLARACION PUBLICA
const int m=3, n=3, z=20;
int i, j, sumatoria, Busca, YY, XX, R, ZZ, Elementos, AUX;
int M[n][m]; // DECLARACION DE UNA MATRIZ
int V[z];
void LeerMatriz(); // DECLARACION FUNCIONES
void EscribirMatriz();
void Buscar(int YY);
int SumarElementos();
void LeerVector(int XX);
void EscribirVector(int XX);
void OrdenaVector(int XX);
void Vectorizando(int ZZ);
void Matriceando(int ZZ);
int main ()
{
int opcion;
do
{ //INICIO DEL DO - WHILE
cout<<"********* MENU DE UNA MATRIZ **********\n\n";
cout<<" 1) LECTURA DE LA MATRIZ n*m \n";
cout<<" 2) ESCRITURA DE LA MATRIZ n*m \n";
cout<<" 3) ENCONTRAR EL ELEMENTO \n";
cout<<" 4) SUMAR ELEMENTOS EN LA MATRIZ \n";
cout<<" 5) LECTURA DE UN VECTOR[z] \n";
cout<<" 6) ESCRITURA DE UN VECTOR[z] \n";
cout<<" 7) ORDENAR EL VECTOR[z] \n";
cout<<" 8) VECTORIZAR LA MATRIZ \n";
cout<<" 9) MATRICEAR EL VECTOR \n\n";
cout<<" DIGITE <0> PARA SALIR \n";
cout<<" Elija una Opcion < > \n\n";
cout<<"*************************************\n\n";
cout<<" ELIJA UNA OPCION : "; cin>>opcion;
//2)ASIGNACION
switch (opcion)
{ //INICIO DEL CASO 1
case 1:
{// CONTENIDO 1 (INICO)
cout<<"******* LECTURA DE LA MATRIZ ******\n\n";
LeerMatriz();
cout<<"************************************\n\n";
} //FIN DEL CASO 1
break;
case 2:
{//INICIO DEL CASO 2
cout<<"******* ESCRITURA DE LA MATRIZ ******\n\n";
EscribirMatriz();
cout<<"*********************************\n\n";
} //FIN DEL CASO 2
break;
case 3:
{//INICIO DEL CASO 3
cout<<"******* ENCONTRAR UN ELEMENTO DE LA MATRIZ ******\n\n";
cout<<"Ingrese el e-nesimo elemento a Buscar: "; cin>> Busca;
Buscar(Busca);
cout<<"*********************************\n\n";
} //FIN DEL CASO 2
break;
case 4:
{//INICIO DEL CASO 4
cout<<"******* SUMAR ELEMENTOS EN LA MATRIZ ******\n\n";
R = SumarElementos();
cout<<"LA SUMA DE LOS ELEMENTOS DE LA MATRIZ ES:"<< R<< endl;
cout<<"\n******************************************\n\n";
} //FIN DEL CASO 2
break;
case 5:
{//INICIO DEL CASO 5
cout<<"******* LECTURA DE UN VECTOR[z] ******\n\n";
cout<<"Ingrese el número de elementos del V[z]"; cin>>Elementos;
LeerVector(Elementos);
cout<<"\n******************************************\n\n";
} //FIN DEL CASO 2
break;
case 6:
{//INICIO DEL CASO 6
cout<<"******* ESCRITURA DE UN VECTOR[z] ******\n\n";
EscribirVector(Elementos);
cout<<"\n******************************************\n\n";
} //FIN DEL CASO 2
break;
case 7:
{//INICIO DEL CASO 7
cout<<"******* ORDENAR EL VECTOR[z] ******\n\n";
OrdenaVector(Elementos);
cout<<"\n******************************************\n\n";
} //FIN DEL CASO 2
break;
case 8:
{//INICIO DEL CASO 8
cout<<"******* VECTORIZAR LA MATRIZ ******\n\n";
cout<<"Ingrese el número de elementos del V[z]"; cin>>Elementos;
Vectorizando(Elementos);
cout<<"\n******************************************\n\n";
} //FIN DEL CASO 2
break;
case 9:
{//INICIO DEL CASO 9
cout<<"******* MATRICEAR EL VECTOR ******\n\n";
Matriceando(Elementos);
cout<<"\n******************************************\n\n";
} //FIN DEL CASO 2
break;
}// FIN DE SWITCH
}while (opcion !=0); // FIN DEL DO - WHILE
cout<<endl;cout<<"\n";
system("pause");
return 0;
} //FIN DEL PROGRAMA
// ZONA DE DESARROLLO DE FUNCIONES
void LeerMatriz()
{
cout<<endl;
cout<<"LECTURA DE LA MATRIZ M "<<endl;
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
{
cout<<"ingrese valor del elemento M["<<i<<"]["<<j<<"] = "; cin>>M[i][j];
}
cout<<endl;
}
void EscribirMatriz()
{
cout<<endl;
cout<<"ESCRITURA DE LA MATRIZ M "<<endl;
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
{
cout<<"El elemento M["<<i<<"]["<<j<<"] = "<<M[i][j]<<endl;
}
cout<<endl;
}
void Buscar(int YY)
{
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
{
if (M[i][j]==YY)
cout<<" Encontrmos al elemento M["<<i<<"]["<<j<<"] = "<<M[i][j] <<endl;
}
} // FIN DE BUSCAR
int SumarElementos()
{
sumatoria = 0;
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
{
sumatoria = sumatoria + M[i][j];
}
return sumatoria;
} // FIN DE SUMAR
void LeerVector(int XX)
{
cout<<endl;
cout<<"LECTURA DEL VECTOR V[z] "<<endl<<endl;
for(i=1; i<=XX; i++)
{
cout<<"Ingrese valor del elemento V["<<i<<"] = "; cin>>V[i];
}
cout<<endl;
}
void EscribirVector(int XX)
{
cout<<endl;
cout<<"ESCRITURA DEL VECTOR V[z] "<<endl<<endl;
for(i=1; i<=XX; i++)
{
cout<<"Elemento V["<<i<<"] = "<< V[i]<< endl;
}
cout<<endl;
} // FIN DEL ESCRIBIR
void OrdenaVector(int XX)
{
for(i=1; i<=XX; i++)
for(j=1; j<=XX-1; j++)
{
if(V[j] > V[j+1])
{
AUX = V[j];
V[j] = V[j+1];
V[j+1] = AUX;
}
}
EscribirVector(XX);
} // FIN DE ORDENA
void Vectorizando(int ZZ)
{
int k;
k=1;
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
{
V[k]=M[i][j];
k++;
}
}
void Matriceando(int ZZ)
{
int k;
k=1;
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
{
M[i][j] = V[k];
k++;
}
}
