Métodos de ordenamiento
​
Es la operación de arreglar los registros de una tabla en algún orden secuencial de acuerdo a un criterio de ordenamiento. El ordenamiento se efectúa con base en el valorde algún campo en un registro. El propósito principal de un ordenamiento es el defacilitar las búsquedas de los miembros del conjunto ordenado.El ordenar un grupo de datos significa mover los datos o sus referencias para que queden en una secuencia tal que represente un orden, el cual puede ser numérico,alfabético o incluso alfanumérico, ascendente o descendente.
​
Método de Intercambio o de Burbuja:
​
Se basa en el principio de comparar pares de elementos adyacentes e intercambiarlos entre si hasta que estén todos ordenados. Supongamos que se desea clasificar en orden ascendente el vector o lista:
Los pasos a dar son:
- CompararA[1] yA[2] si están en orden, se mantienen como están, en caso contrario se intercambian entre si.
- A continuación se comparan los elementos 2 y 3; de nuevo se intercambian si es necesario.
- El proceso continua hasta que cada elemento del vector ha sido comparado con sus elementos adyacentes y se han realizado los intercambios necesarios.
​
Método de Selección:
​
DESCRIPCIÓN.
•Buscas el elemento más pequeño de la lista.
•Lo intercambias con el elemento ubicado en la primera posición de la lista.
•Buscas el segundo elemento más pequeño de la lista.
•Lo intercambias con el elemento que ocupa la segunda posición en la lista.
•Repites este proceso hasta que hayas ordenado toda la lista.
ANÁLISIS DEL ALGORITMO.
•Requerimientos de Memoria:
Al igual que el ordenamiento burbuja, este algoritmo sólo necesita una variable adicional para realizar los intercambios.
•Tiempo de Ejecución:
El ciclo externo se ejecutan
veces para una lista de elementos. Cada búsqueda requiere comparar todos los elementos no clasificados.
MÉTODO DE INSERCIÓN
El método de ordenación por 'inserción binaria'' es una mejora del método de inserción directa. Para lograr esta mejora se recurre a una búsqueda binaria en lugar de una búsqueda secuencial para insertar un elemento en la parte izquierda del arreglo, que ya se encuentra ordenado. El resto del procedimiento es similar al de inserción directa, es decir, se repite este mismo procedimiento desde el segundo término hasta el último elemento.
MÉTODO DE SHELL:
El método Shell es una versión mejorada del método de inserción directa. Este método también se conoce con el nombre de inserción con incrementos decrecientes. En el método de ordenación por inserción directa cada elemento se compara para su ubicación correcta en el arreglo, con los elementos que se encuentran en la parte izquierda del mismo. Si el elemento a insertar es más pequeño que el grupo de elementos que se encuentran a su izquierda, es necesario efectuar entonces varias comparaciones antes de su ubicación.
​
ORDENAMIENTO QUICK SORT:
​
El ordenamiento por partición (Quick Sort) se puede definir en una forma más conveniente como un procedimiento recursivo. Tiene aparentemente la propiedad de trabajar mejor para elementos de entrada desordenados completamente, que para elementos semiordenados. Esta situación es precisamente la opuesta al ordenamiento de burbuja.Este tipo de algoritmos se basa en la técnica "divide y vencerás", o sea es más rápido y fácil ordenar dos arreglos o listas de datos pequeños, que un arreglo o lista grande.
​
​
PROGRAMACION EN C++
#include<iostream>
#define MAX 1000
using namespace std;
int LEER(), i, n, A[100];
int MIRAR();
int BURBUJA(), j, aux;
int INSERSION(), k;
int SELECCION();
int SHELL();
int QUICK_SORT(int[], int), central;
int main()
{
int x;
do
{
cout<<"MENU DE OPCIONES"<<endl;
cout<<"################ \n";
cout<<"(1): LEER "<<endl;
cout<<"(2): MIRAR "<<endl;
cout<<"(3): ORDENAR POR EL METODO DE BURBUJA "<<endl;
cout<<"(4): ORDENAR POR EL METODO DE INSERSION "<<endl;
cout<<"(5): ORDENAR POR EL METODO DE SELECCION "<<endl;
cout<<"(6): ORDENAR POR EL METODO DE SHELL "<<endl;
cout<<"(7): ORDENAR POR EL METODO QUICK SORT "<<endl;
int opcion;
cout<<"ELIJA LA LA OPCION QUE DESEE: "; cin>>opcion;
cout<<endl;
switch(opcion)
{
case 1:
{
LEER();
}
break;
case 2:
{
MIRAR();
}
break;
case 3:
{
BURBUJA();
}
break;
case 4:
{
INSERSION();
}
break;
case 5:
{
SELECCION();
}
break;
case 6:
{
SHELL();
}
break;
case 7:
{
QUICK_SORT(A, n);
}
break;
default: cout<<"NO ES OPCION"<<endl;
}
cout<<"¿QUIERE ELEGIR OTRA OPCION DEL MENU?"<<endl;
cout<<"(1): SI "<<endl;
cout<<"(2): NO "<<endl;
cout<<"ELIJE SI O NO: "; cin>>x;
cout<<endl;
}
while(x==1);
system("pause");
return 0;
}
int LEER()
{
cout<<"INGRESE EL NUMERO DE ELEMENTOS DEL VECTOR: "; cin>>n;
for(i=0; i<n; i++)
{
cout<<i+1<<".- DIGITE UN NUMERO: "; cin>>A[i];
}
cout<<endl;
}
int MIRAR()
{
cout<<"ELEMENTOS DEL VECTOR"<<endl;
cout<<"==================== \n";
for(i=0; i<n; i++)
{
cout<<A[i]<<" ";
}
cout<<endl<<endl;
}
int BURBUJA()
{
cout<<"ORDENAMIENTO POR EL METODO BURBUJA \n";
cout<<"================================== \n";
for(i=0; i<n; i++)
{
for(j=0; j<n-1; j++)
{
if(A[j]>A[j+1])
{
aux=A[j];
A[j]=A[j+1];
A[j+1]=aux;
}
}
}
cout<<"ELEMENTOS DEL VECTOR ORDENADOS DE MENOR A MAYOR"<<endl;
for(i=0; i<n; i++)
{
cout<<A[i]<<" ";
}
cout<<endl<<endl;
cout<<"ELEMENTOS DEL GRUPO ORDENADOS DE MAYOR A MENOR \n";
i=n-1;
while(i>=0)
{
cout<<A[i]<<" ";
i--;
}
cout<<endl<<endl;
}
int INSERSION()
{
cout<<"ORDENAMIENTO POR EL METODO DE INSERCION \n";
cout<<"======================================= \n";
for(i=0; i<n; i++)
{
k=i;
aux=A[i];
while((k>0)&&(A[k-1]>aux))
{
A[k]=A[k-1];
k--;
}
A[k]=aux;
}
cout<<"LOS ELEMENTOS DEL VECTOR ORDENADOS DE MENOR A MAYOR \n";
i=0;
while(i<n)
{
cout<<A[i]<<" ";
i++;
}
cout<<endl<<endl;
cout<<"LOS ELEMENTOS DEL VECTOR ORDENADOS DE MAYOR A MENOR \n";
i=n-1;
while(i>=0)
{
cout<<A[i]<<" ";
i--;
}
cout<<endl<<endl;
}
int SELECCION()
{
cout<<"ORDENAMIENTO POR METODO DE SELECCION \n";
cout<<"==================================== \n";
for(i=0; i<n; i++)
{
k=i;
for(j=i+1; j<n; j++)
{
if(A[j]<A[k])
{
k=j;
}
}
aux=A[i];
A[i]=A[k];
A[k]=aux;
}
cout<<"LOS ELEMENTOS DEL VECTOR ORDENADOS DE MENOR A MAYOR \n";
i=0;
while(i<n)
{
cout<<A[i]<<" ";
i++;
}
cout<<endl<<endl;
cout<<"LOS ELEMENTOS DEL VECTOR ORDENADOS DE MAYOR A MENOR \n";
i=n-1;
while(i>=0)
{
cout<<A[i]<<" ";
i--;
}
cout<<endl<<endl;
}
int SHELL()
{
cout<<"ORDENAMIENTO POR EL METODO DE SHELL \n";
cout<<"=================================== \n";
i=n;
while(i>1)
{
i=i/2;
k=true;
while(k==true)
{
k=false;
j=0;
while((j+i)<n)
{
if(A[j]>A[j+i])
{
aux=A[j];
A[j]=A[j+i];
A[j+i]=aux;
k=true;
}
j++;
}
}
}
cout<<"LOS ELEMENTOS DEL VECTOR ORDENADOS DE MENOR A MAYOR \n";
i=0;
while(i<n)
{
cout<<A[i]<<" ";
i++;
}
cout<<endl<<endl;
cout<<"LOS ELEMENTOS DEL VECTOR ORDENADOS DE MAYOR A MENOR \n";
i=n-1;
while(i>=0)
{
cout<<A[i]<<" ";
i--;
}
cout<<endl<<endl;
}
int QUICK_SORT(int A[], int n)
{
cout<<"ORDENAMIENTO POR EL METODO DE QUICK SORT \n";
cout<<"======================================== \n";
int tope, ini, fin , pos;
int may[MAX],menor[MAX];
tope=0;
menor[tope]=0;
may[tope]=n-1;
while(tope>=0)
{
ini = menor[tope];
fin = may[tope];
tope--;
int izq,der,aux;
bool band;
izq=ini;
der=fin;
pos=ini;
band=true;
while(band==true)
{
while((A[pos]<A[der]) && ( pos!=der ))
der--;
if(pos==der)
band=false;
else
{
aux=A[pos];
A[pos]=A[der];
A[der]=aux;
pos=der;
}
while((A[pos]>A[izq]) && ( pos!=izq ))
izq++;
if(pos==izq)
band=false;
else
{
aux=A[pos];
A[pos]=A[izq];
A[izq]=aux;
pos=izq;
}
}
if(ini<=(pos-1))
{
tope++;
menor[tope]=ini;
may[tope]=pos-1;
}
if(fin>=(pos+1))
{
tope++;
menor[tope]=pos+1;
may[tope]=fin;
}
}
cout<<"LOS ELEMENTOS DEL VECTOR ORDENADOS DE MENOR A MAYOR \n";
i=0;
while(i<n)
{
cout<<A[i]<<" ";
i++;
}
cout<<endl<<endl;
cout<<"LOS ELEMENTOS DEL VECTOR ORDENADOS DE MAYOR A MENOR \n";
i=n-1;
while(i>=0)
{
cout<<A[i]<<" ";
i--;
}
cout<<endl<<endl;
}
