Hace mucho tiempo que no escribía un entrada en este blog, la verdad la jornada laboral me consume todo el tiempo, asique cansado, pero a la vez contento porque mi memoria de título(Primer Post) a sido seleccionada para exposición oral en dos congresos internacionales mas: CITIC 2010 y JIISIC 2010.
Este post, trata de distintos tipos de algoritmos de ordenación, los típicos que vemos en la universidad, asique me pareció buena idea, publicar esta entrada como guía. Eh implementado cada algoritmo en un programa escrito en lenguaje C, por lo tanto, como siempre, si quieren el programa sólo tienen que pedirlo.
Ordenación por Selección: Este algoritmo es muy sencillo y funciona de la siguiente forma: se busca el elemento más pequeño del Vector y se intercambia con el que esta en la primera posición, después se busca el segundo mas pequeño y se intercambia con el elemento de la segunda posición y continua así hasta que el vector este ordenado.
Ejemplo:Se ubica el elemento más pequeño del vector
| 5 | 10 | 8 | 1 | 9 |
Se intercambia con el que esta en la primera posición
| 1 | 10 | 8 | 5 | 9 |
Luego se ubica el segundo elemento más pequeño y se intercambia con el de la segunda
Posición
| 1 | 10 | 8 | 5 | 9 |
| 1 | 5 | 8 | 10 | 9 |
.
.
| 1 | 5 | 8 | 9 | 10 |
Así hasta quedar completamente ordenado.
El Algoritmo de este método es:
El bucle for hace referencia al intercambio de n veces del vector, y la variable i guarda la posición a intercambiar
for (i = 1; i <= n; i++)
{
el bucle while encuentra el elemento menor del vector que corresponde y se almacena en la variable min y la posición del elemento en la variable j
while (j<=n)
{
if (a[j] <= min)
{min = a[j]; pos = j ;}
j++;
}
hace el intercambio correspondiente con el menor encontrado
a [pos]=a[i];
a[i] =min;
j = i + 1;
min = 1000000;
}
Ordenación por Inserción: Este método funciona de la siguiente forma: el elemento considerado se inserta moviendo una posición a la derecha a todos los elementos mayores que el e insertando a continuación el elemento en la posición vacante.
Ejemplo:Se compara la posición 2 con el 1 y se intercambia si es menor
| 5 | 6 | 8 | 1 | 9 |
Luego se compara la posición 3 con la 2
| 5 | 6 | 8 | 1 | 9 |
Luego la posición 4 con la 3, como la posición 4 es menor que la posición 3 entonces se intercambia sucesivamente hasta quedar ordenado
| 5 | 6 | 8 | 1 | 9 |
Se mueven todos los elementos mayores a la derecha
| _ | 5 | 6 | 8 | 9 |
Y se inserta el elemento en la posición correspondiente
| 1 | 5 | 6 | 8 | 9 |
El algoritmo de este método es:
a[0]=0; // elemento menor posible del vector
El bucle for hace referencia al ciclo de n-1 veces del método
for (i = 2; i< = n; i++)
{
j = i;
la variable var almacena el valor correspondiente a evaluar
var = a [i];
el ciclo while mueve todos los valores mayores que var a la derecha
while (a [j-1]>=var)
{
a[j] = a [j-1]; // intercambio
j--;
}
a[j]=var;
}
Método de Ordenación de Burbuja: En este método se efectúan tantos pasos en el Vector como sea necesario, intercambiando elementos adyacentes entre si, cuando en algún paso no se necesite intercambios el vector estar ordenado.
Ejemplos:
Compara la 2 posición con la 1, si esta es menor se intercambian
| 5 | 8 | 6 | 1 | 9 |
Luego se compara la 3 posición con la 2, y se intercambian
| 5 | 6 | 8 | 1 | 9 |
Luego se compara la 4 posición con la 3, y se intercambian
| 5 | 6 | 1 | 8 | 9 |
Luego se compara la n posición con la n-1 y si es menor se intercambian
| 5 | 6 | 1 | 8 | 9 |
Este procedimiento se hace n-1 veces hasta que el vector este completamente ordenado.
El algoritmo para este método es:
El bucle for hace referencia al ciclo de n-1 veces del método
for (i = 1; i<= n-1; i++)
{
este bucle for compara y ordena todos los elementos adyacentes entre sí , esto se repite
n-1 veces gracias al primer bucle for quedando el vector completamente ordenado
for (j = 1; j <n; j++)
{
el if compara los elementos adyacentes y si es menor el de la izq se intercambia, la variable var almacena el valor a intercambiar
if (a[j] >= a [j + 1])
{var = a [j + 1];
a [j + 1] = a[j];
a[j] = var;
}
}
}
Método de Ordenación Shell: La idea de este método es reorganizar el archivo para que tenga la propiedad de que tomando todos los elementos h-ésimos se obtenga un Archivo ordenado, Entonces estará h-ordenado o sea esta constituido por h archivos ordenados independientes y entrelazados entre sí.
Ejemplo:
Este ejemplo muestra la operación de la ordenación Shell para incrementos decrecientes
De 13, 4, 1
En el primer paso se toma la primera posición y se compara con la posición 13, y si es menor se intercambia.
| 5 | 6 | 8 | 7 | 4 | 6 | 9 | 2 | 3 | 3 | 4 | 2 | 1 |
Intercambio
| 1 | 6 | 8 | 7 | 4 | 6 | 9 | 2 | 3 | 3 | 4 | 2 | 5 |
En el segundo paso la serie es de 4 por lo tanto se divide el vector en partes de a 4 se compara y se ordena hasta que estos elementos queden ordenados
| 1 | 6 | 8 | 7 | 4 | 6 | 9 | 2 | 3 | 3 | 4 | 2 | 5 |
1 5 9 13
| 1 | 6 | 8 | 7 | 3 | 6 | 9 | 2 | 4 | 3 | 4 | 2 | 5 |
Luego se analiza las posiciones 2, 6, 10
| 1 | 6 | 8 | 7 | 4 | 6 | 9 | 2 | 3 | 3 | 4 | 2 | 5 |
2 6 10
Se comparan y se ordenan
| 1 | 3 | 8 | 7 | 4 | 6 | 9 | 2 | 3 | 6 | 4 | 2 | 5 |
Luego se compara las posiciones 3, 7, 11: 4, 8, 12 respectivamente
| 1 | 3 | 4 | 7 | 4 | 6 | 8 | 2 | 3 | 6 | 9 | 2 | 5 |
3 7 11
| 1 | 3 | 4 | 2 | 4 | 6 | 8 | 2 | 3 | 6 | 9 | 7 | 5 |
4 8 12
En el 3 paso la serie es de 1 luego el vector se divide en n partes, Este ultimo paso es
El método de inserción con la ventaja que ningún elemento tiene que desplazarse muy lejos
| 1 | 3 | 4 | 2 | 4 | 6 | 8 | 2 | 3 | 6 | 9 | 7 | 5 |
| 1 | 3 | 4 | 2 | 4 | 6 | 8 | 2 | 3 | 6 | 9 | 7 | 5 |
| 1 | 2 | 3 | 4 | 4 | 6 | 8 | 2 | 3 | 6 | 9 | 7 | 5 |
| 1 | 2 | 2 | 3 | 4 | 4 | 6 | 8 | 3 | 6 | 9 | 7 | 5 |
| 1 | 2 | 2 | 3 | 3 | 4 | 4 | 6 | 8 | 6 | 9 | 7 | 5 |
| 1 | 2 | 2 | 3 | 3 | 4 | 4 | 6 | 6 | 8 | 9 | 7 | 5 |
| 1 | 2 | 2 | 3 | 3 | 4 | 4 | 6 | 6 | 7 | 8 | 9 | 5 |
| 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | 6 | 6 | 7 | 8 | 9 |
Quedando la lista finalmente ordenada
El algoritmo de este método es:
Este for muestra el incremento de la serie (16, 10, 7,…., 3), con la variable h como indicador de los h subarchivos del vector.
for (h = 1; j <= n/9; h = 3*h+1);
Este for divide la variable h en 3
for (; h>0; h/=3)
la variable i del for indica la siguiente posición a comparar
for (i=h+1; i<=n; i+=1)
{
La variable v es la variable pivote
v = a[i]; j = i;
En este ciclo while se compara y se intercambian los valores con la variable pivote
while (j>h && a [j-h]>v)
{a [j]=a [j-h]; j - = h;}
a[j] =v;
}
Método de Ordenación Quicksort: Esta es probablemente la técnica más rápida conocida. Fue desarrollada por C.A.R. Hoare en 1960.Su funcionamiento es el siguiente.
Eliges un elemento de la lista. Puede ser cualquiera .Lo llamaremos elemento de división. Buscas la posición que le corresponde en la lista ordenada. Acomodas los elementos de la lista a cada lado del elemento de división, de manera que a un lado queden todos los menores que él y al otro los mayores. En este momento el elemento de división separa la lista en dos sublistas. Realizas esto de forma recursiva para cada sublista mientras éstas tengan un largo mayor que 1. Una vez terminado este proceso todos los elementos estarán ordenados.
Comenzamos con la lista completa. El elemento divisor será el 4: | 5 | 3 | 7 | 6 | 2 | 1 | 4 |
Comparamos con el 5 por la izquierda y el 1 por la derecha.
| 5 | 3 | 7 | 6 | 2 | 1 | 4 |
5 es mayor que cuatro y 1 es menor. Intercambiamos:
| 1 | 3 | 7 | 6 | 2 | 5 | 4 |
Avanzamos por la izquierda y la derecha:
| 1 | 3 | 7 | 6 | 2 | 5 | 4 |
3 es menor que 4: avanzamos por la izquierda. 2 es menor que 4: nos mantenemos ahí.
| 1 | 3 | 7 | 6 | 2 | 5 | 4 |
7 es mayor que 4 y 2 es menor: intercambiamos.
| 1 | 3 | 2 | 6 | 7 | 5 | 4 |
Avanzamos por ambos lados:
| 1 | 3 | 2 | 6 | 7 | 5 | 4 |
En este momento termina el ciclo principal, porque los índices se cruzaron. Ahora intercambiamos a[i] con a [der]
| 1 | 3 | 2 | 4 | 7 | 5 | 6 |
Aplicamos recursivamente a la sublista de la izquierda. Tenemos lo siguiente:
| 1 | 3 | 2 |
1 es menor que 2: avanzamos por la izquierda. 3 es mayor: avanzamos por la derecha. Como se intercambiaron los índices termina el ciclo. Se intercambia lista[i] con lista[sup]:
| 1 | 2 | 3 |
Al llamar recursivamente para cada nueva sublista (lista[0]-lista[0] y lista[2]-lista[2]) se retorna sin hacer cambios (condición 5.).Para resumir te muestro cómo va quedando la lista:
Segunda sublista: a [4] - a [6]
| 7 | 5 | 6 |
| 5 | 7 | 6 |
| 5 | 6 | 7 |
Para cada nueva sublista se retorna sin hacer cambios (se cruzan los índices).
Finalmente, al retornar de la primera llamada se tiene el arreglo ordenado:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
El algoritmo para este método es:
Este if verifica que no se crucen los límites
if (der>izq)
{
la variable v contiene el valor de la partición
v = a [der]; i = izq-1; j = der;
for (;;)
{
Se clasifican los subarchivos
while (a [++i] <v);
while (a [--j]>v);
Sale del bucle cuando se Cruzan los punteros
if (i>=j) break;
Se intercambia los valores del vector
var = a[i]; a[i] = a[j]; a[j] = var;
}
Se ordena recursivamente los dos subarchivos, con el método divide y vencerás
var = a[i]; a[i] = a [der]; a [der] = var;
quicksort (izq, i-1);
quicksort (i+1, der);
}
Método de Ordenación por Residuo: En este método se aprovecha el hecho de que las claves pueden considerarse como números de algún intervalo finito, este tipo de métodos de ordenación se denominan ordenación por residuos. Este método funciona de la siguiente manera, se reordenan los registros de un archivos de manera que todas aquellas claves que comiencen con el Bit 0 se coloquen delante de todas las que comiencen con el Bit 1, para esto se examina el archivo empezando por la izquierda para encontrar una clave que empiece con el Bit 1 y empezando por la derecha para encorar una clave que empiece con el Bit 0, intercambiándolas recursivamente y continuando así hasta que se crucen los punteros.
Ejemplo:La tabla esta inicialmente desordenada
| 9 | = | 1 | 0 | 0 | 1 |
| 6 | = | 0 | 1 | 1 | 0 |
| 7 | = | 0 | 1 | 1 | 1 |
| 2 | = | 0 | 0 | 1 | 0 |
| 8 | = | 1 | 0 | 0 | 0 |
| 10 | = | 1 | 0 | 1 | 0 |
| 1 | = | 0 | 0 | 0 | 1 |
| 5 | = | 0 | 1 | 0 | 1 |
| 4 | = | 0 | 1 | 0 | 0 |
| 3 | = | 0 | 0 | 1 | 1 |
Se Analiza el Bit mas izquierdo de los números y se ordena
| 6 | = | 0 | 1 | 1 | 0 |
| 7 | = | 0 | 1 | 1 | 1 |
| 2 | = | 0 | 0 | 1 | 0 |
| 1 | = | 0 | 0 | 0 | 1 |
| 5 | = | 0 | 1 | 0 | 1 |
| 4 | = | 0 | 1 | 0 | 0 |
| 3 | = | 0 | 0 | 1 | 1 |
| 9 | = | 1 | 0 | 0 | 1 |
| 8 | = | 1 | 0 | 0 | 0 |
| 10 | = | 1 | 0 | 1 | 0 |
Luego se ordena de la misma manera con el Bit que sigue, dejando los 1 hasta el principio del Bit 0 ordenado anteriormente
| 2 | = | 0 | 0 | 1 | 0 |
| 1 | = | 0 | 0 | 0 | 1 |
| 3 | = | 0 | 0 | 1 | 1 |
| 6 | = | 0 | 1 | 1 | 0 |
| 7 | = | 0 | 1 | 1 | 1 |
| 5 | = | 0 | 1 | 0 | 1 |
| 4 | = | 0 | 1 | 0 | 0 |
| 9 | = | 1 | 0 | 0 | 1 |
| 8 | = | 1 | 0 | 0 | 0 |
| 10 | = | 1 | 0 | 1 | 0 |
Luego se ordena el siguiente Bit
| 1 | = | 0 | 0 | 0 | 1 |
| 2 | = | 0 | 0 | 1 | 1 |
| 3 | = | 0 | 0 | 1 | 1 |
| 5 | = | 0 | 1 | 0 | 1 |
| 4 | = | 0 | 1 | 0 | 0 |
| 6 | = | 0 | 1 | 1 | 0 |
| 7 | = | 0 | 1 | 1 | 1 |
| 9 | = | 1 | 0 | 0 | 1 |
| 8 | = | 1 | 0 | 0 | 0 |
| 10 | = | 1 | 0 | 1 | 0 |
Finalmente se ordena el primer Bit de los elementos, quedando la tabla ordenada
| 1 | = | 0 | 0 | 0 | 1 |
| 2 | = | 0 | 0 | 1 | 1 |
| 3 | = | 0 | 0 | 1 | 1 |
| 4 | = | 0 | 1 | 0 | 0 |
| 5 | = | 0 | 1 | 0 | 1 |
| 6 | = | 0 | 1 | 1 | 0 |
| 7 | = | 0 | 1 | 1 | 1 |
| 8 | = | 1 | 0 | 0 | 0 |
| 9 | = | 1 | 0 | 0 | 1 |
| 10 | = | 1 | 0 | 1 | 0 |
El algoritmo de este método es:
Este if verifica que no se crucen las variables izq y der
if (der > izq && b > 0)
{
Las variables i y j toman los valores limites
i = izq; j = der;
while (j != i)
{
Estos ciclos while compara los bits de los datos del vector
while (! c[i].bits (b, 1) && i < j) i++;
while (c[j].bits (b, 1) && j > i) j--;
Intercambia los valores
Intercambio (i, j);
}
Este if aumenta j si c[der].bit es falso o sea si no ha llegado al limite
if (!c[der].bits(b,1)) J++;
Llama recursivamente a la función residuos
residuos (izq, j-1, b-1);
residuos (j, der, b-1);
}
