ORDENACIONES MEJORADAS
ORDENACION MEJORADA (RAPIDA O QUICKSORT)
El algoritmo Quicksort (u ordenación rápida) es un método de ordenación mucho más elaborado que los dos anteriores y, por lo tanto, más difícil de comprender. Fue desarrollado en 1960 por C. R. Hoare. La versión que presentamos es recursiva, pero existen implementaciones equivalentes iterativas, más difíciles (todavía) de comprender, pero más rápidas.
La idea es la siguiente: tomemos un elemento cualquiera del vector (generalmente el elemento central), que llamaremos pivote. Buscamos a la derecha del pivote todos los elementos que deberían estar a la izquierda (porque sean más pequeños que el pivote) y, a la izquierda, todos los que deberían estar a la derecha (por ser más grandes) e intercambiémoslos.
El proceso de intercambio de pares se repetirá hasta que alcancemos el pivote. Entonces, sabremos que todos los elementos de la derecha del pivote son mayores que éste, y, los de la derecha, son menores.
Ahora dividimos el vector en dos mitades: a la izquierda del pivote y a la derecha del pivote. Procesaremos cada mitad con el mismo procedimiento: buscar un nuevo pivote e intercambiar elementos de la izquierda y de la derecha.
Repetiremos el proceso hasta que los vectores sean triviales (es decir, hasta que el pivote coincida con los extremos izquierdo y/o derecho).
void ordena_vector(int iz, int de)
{
int i, j, x, w; i = iz;
j = de;
x = v[(iz+de) / 2];
do
{
while (v[i] < x) i++;
while (x < v[j]) j--;
if (i <= j)
{
w = v[i];
v[i] = v[j];
v[j] = w;
i++;
j--;
}
}
while (i <= j);
w = v[i];
v[i] = v[de];
v[de] = w;
if (iz < j) ordena_vector(iz, j);
if (i < de) ordena_vector(i, de);
}
ORDENAMIENTO POR EL METODO DE SHELL
El método se denomina Shell en honor de su inventor Donald Shell.
El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones:
- El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".
- El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una posición cada vez.
El algoritmo Shell es una mejora de la ordenación por inserción, donde se van comparando elementos distantes, al tiempo que se los intercambian si corresponde. A medida que se aumentan los pasos, el tamaño de los saltos disminuye; por esto mismo, es útil tanto como si los datos desordenados se encuentran cercanos, o lejanos.
Es bastante adecuado para ordenar listas de tamaño moderado, debido a que su velocidad es aceptable y su codificación es bastante sencilla. Su velocidad depende de la secuencia de valores con los cuales trabaja, ordenándolos.
void shell_sort(int A[], int size)
{
int i, j, incrmnt, temp;
incrmnt = size/2;
while (incrmnt > 0)
{
for (i=incrmnt; i < size; i++)
{
j = i;
temp = A[i];
while ((j >= incrmnt) && (A[j-incrmnt] > temp))
{
A[j] = A[j - incrmnt];
j = j - incrmnt;
}
A[j] = temp;
}
incrmnt /= 2;
}
}
ORDENAMIENTO BURBUJA MEJORADO
void burbujam(int a[],int n){
int i,j=0,band=1,aux;
while(j<n && band==1){
band=0;
for(i=0;i<n;i++){
if(a[i]>a[i+1]){
aux=a[i];
a[i]=a[i+1];
a[i+1]=aux;
band=1;
}
}
printf("nPasada N§%dn",j);
ver(a,n);
j++;
}
}
