ORDENAMIENTO

ORDENAMIENTO DE BURBUJA.

Concepto.

La Ordenación de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". También es conocido como el método del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar.

Descripcion.

Una manera simple de expresar el ordenamiento de burbuja en pseudocódigo es la siguiente:

La burbuja son dos términos de la lista seguidos, j y j+1, que se comparan, si el primero es menor que el segundo sus valores se intercambian.Este algoritmo realiza el ordenamiento de una lista a de n valores, en este caso de n términos numerados del 0 aln-1, consta de dos bucles anidados uno con el índice i, que da un tamaño menor al recorrido de la burbuja en sentido inverso de 2 a n, y un segundo bucle con el índice j, con un recorrido desde 0 hasta n-i, para cada iteración del primer bucle, que indica el lugar de la burbuja.

Esta comparación se repite en el centro de los dos bucles, dando lugar a la postre a una lista ordenada, puede verse que el número de repeticiones sola depende de n, y no del orden de los términos, esto es, si pasamos al algoritmo una lista ya ordenada, realizara todas las comparaciones exactamente igual que para una lista no ordenada, esta es una característica de este algoritmo, luego veremos una variante que evita este inconveniente.

Ejemplo:

Tenemos una lista de números que hay que ordenar:

El índice i hará un recorrido de 2 hasta n:Podemos ver que la lista que tiene cinco términos, luego:

Que en este caso será de 2 a 5. Para cada uno de los valores de i, j tomara sucesivamente los valores de 0 hasta n-i:

Para cada valor de j, obtenido en ese orden, se compara el valor del índice j con el siguiente:

Para el caso del ejemplo, tenemos que:                                                      Si el termino j es menor, en su caso podría se mayor, que el termino j+1, los valores se permutan, en caso contrario se continúa con la iteración.

Para la primera iteración del primer bucle:

y j tomara los valores de 0 hasta 3:

Ahora j vale 1 y se comparan  el 86 y el 48 Como 86 > 48, se permutan, dando lugar a una nueva lista.Cuando j vale 0, se comparan , el 55 y el 86, dado que 55 < 86 no se permutan el orden.

Se repite el proceso hasta que j valga 3, dando lugar a una lista parcialmente ordenada, podemos ver que el termino de mayor valor esta en el lugar más alto.

Ahora i vale 3, y j hará un recorrido de 0 a 2.

Primero j vale 0, se comparan , el 55 y el 48, como 55 > 48 se permutan dando lugar a la nueva lista.

Para j = 1 se compara el 55 con el 16 y se cambian de orden.

El algoritmo consiste en comparaciones sucesivas de dos términos consecutivos, ascendiendo de abajo a arriba en cada iteración, como la ascensión de las burbujas de aire en el agua, de ahí el nombre del procedimiento, en la primera iteración el recorrido ha sido completo, en el segundo se ha dejado él último termino, al tener ya el mayor de los valores, en los sucesivos sé ira dejando de realizar las ultimas comparaciones, como se puede ver.Para j = 2 se compara el 55 y el 82 y se dejan como están, finalizando el bucle con una lista mejor ordenada, puede verse que los dos valores más altos ya ocupan su lugar. No se ha realizado ninguna comparación con el termino cuarto, dado que ya se sabe que después del primer ciclo es el mayor de la lista.

Ahora ya i vale 4 y j recorrerá los valores de 0 a 1.

Cuando j vale 0, se comparan  esto es el 48 y el 16 dado que 48 es mayor que 16 se permutan los valores, dando lugar a una lista algo más ordenada que la anterior, desde esta nueva ordenación, j pasa a valer 1, con lo que se comparan los términos  el 48 y el 55 que quedan en el mismo orden.

En este caso la burbuja ha ascendido menos que en los casos anteriores, y la lista esta ya ordenada, pero el algoritmo tendrá que completarse, realizando una ultima iteración.

Hay que tener en cuenta que el bucle para realiza un número fijo de repeticiones y para finalizar tendrán que completarse, aun en el caso extremo, de que la lista estaría previamente ordenada.

Los bucles finalizan y también el procedimiento, dejando la lista ordenada.Por último i vale 5 y j solo puede vale 0, con lo que solo se realizara una comparación de  el 16 y el 48, que ya están ordenados y se dejan igual.

Una variante que finaliza en caso de que la lista este ordenada, puede ser la siguiente, empleando un centinela ordenado, que detecta que no se ha modificado la lista en un recorrido de la burbuja, y que por tanto la lista ya esta ordenada, finalizando.

Programa.

01	public class DemoOrdenamiento

02

{

03	public static void main(String []args)

04

{

05	Ordenamiento datos=new Ordenamiento();

06	int sw,opcion;

07

08	datos.ingreso();

09

sw=1;

10

do{

11

12	System.out.println("0. Salir");

13	System.out.println("1. Burbuja Derecha Izquierda");

14	System.out.println("2. Burbuja de derecha a Izquierda");

15	System.out.println("3. Inserción Directa");

16	System.out.println("4. Selección Directa");

17	System.out.println("5. Metodo Shell");

18	System.out.println("6. Ordenamiento rápido");

19	System.out.print("Opcion ==> ");

20	opcion=Leer.datoInt();

21	if(opcion>0)

22

{

23	System.out.println("Arreglo antes de ordenar");

24	datos.reporte();

25

}

26

27	switch(opcion)

28

{

29	case 0: sw=0;break;

30	case 1: datos.burbuja_der_izq();break;

31	case 2: datos.burbuja_izq_der();break;

32	case 3: datos.baraja();break;

33	case 4: datos.seleccion_directa();break;

34	case 5: datos.shell();break;

35	case 6: datos.quicksort(datos.a,0,datos.n-1);break;

36

}

37

38	if(opcion>0)

39

{

40	System.out.println("Arreglo despues de ordenar");

41	datos.reporte();

42

}

43

44	}while(sw==1);

45

}

46

}

Video

ORDENAMIENTO QUICKSORT.

Concepto
Si bien el método de la burbuja era considerado como el peor método de ordenación simple o menos eficiente, el método Quicksort basa su estrategia en la idea intuitiva de que es más fácil ordenar una gran estructura de datos subdividiéndolas en otras más pequeñas introduciendo un orden relativo entre ellas. En otras palabras, si dividimos el array a ordenar en dos subarrays de forma que los elementos del subarray inferior sean más pequeños que los del subarray superior, y aplicamos el método reiteradamente, al final tendremos el array inicial totalmente ordenado. Existen además otros métodos conocidos, el de ordenación por montículo y el de shell.


Descripción del algoritmo
El algoritmo consta de los siguientes pasos:

·                     Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.

·                     Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.

·                     La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.

·                     Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.

·                     En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n·log n).

·                     En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array que le pasamos está ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente.

·                     En el caso promedio, el orden es O(n·log n).

No es extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmo se centren en la elección del pivote.

Demostración de un caso particular

Supongamos que el número de elementos a ordenar es una potencia de dos, es decir, n = 2^k para algún natural k. Inmediatamente k = log₂(n), donde k es el número de divisiones que realizará el algoritmo.
En la primera fase del algoritmo habrá n comparaciones. En la segunda fase el algoritmo instanciará dos sublistas de tamaño aproximadamente n/2. El número total de comparaciones de estas dos sublistas es: 2(n/2) = n. En la tercera fase el algoritmo procesará 4 sublistas más, por tanto el número total de comparaciones en esta fase es 4(n/4) = n.
En conclusión, el número total de comparaciones que hace el algoritmo es:
n + n + n + ..... + n = kn, donde k = log₂(n), por tanto el tiempo de ejecución del algoritmo en el mejor caso es O(n.log₂n).

Técnicas de elección del pivote

El algoritmo básico del método Quicksort consiste en tomar cualquier elemento de la lista al cual denominaremos como pivote, dependiendo de la partición en que se elija, el algoritmo será más o menos eficiente.

·                     Tomar un elemento cualquiera como pivote tiene la ventaja de no requerir ningún cálculo adicional, lo cual lo hace bastante rápido. Sin embargo, esta elección «a ciegas» siempre provoca que el algoritmo tenga un orden de O(n²) para ciertas permutaciones de los elementos en la lista.

·                     Otra opción puede ser recorrer la lista para saber de antemanoqué elemento ocupará la posición central de la lista, para elegirlo como pivote. Esto puede hacerse en O(n) y asegura que hasta en el peor de los casos, el algoritmo sea O(n·log n). No obstante, el cálculo adicional rebaja bastante la eficiencia del algoritmo en el caso promedio.

·                     La opción a medio camino es tomar tres elementos de la lista - por ejemplo, el primero, el segundo, y el último - y compararlos, eligiendo el valor del medio como pivote.

Técnicas de reposicionamiento

Una idea preliminar para ubicar el pivote en su posición final sería contar la cantidad de elementos menores que él, y colocarlo un lugar más arriba, moviendo luego todos esos elementos menores que él a su izquierda, para que pueda aplicarse la recursividad.
Existe, no obstante, un procedimiento mucho más efectivo. Se utilizan dos índices: i, al que llamaremos índice izquierdo, y j, al que llamaremos índice derecho. El algoritmo es el siguiente:

·                     Recorrer la lista simultáneamente con i y j: por la izquierda con i (desde el primer elemento), y por la derecha con j (desde el último elemento).

·                     Cuando lista[i] sea mayor que el pivote y lista[j] sea menor, se intercambian los elementos en esas posiciones.

·                     Repetir esto hasta que se crucen los índices.

·                     El punto en que se cruzan los índices es la posición adecuada para colocar el pivote, porque sabemos que a un lado los elementos son todos menores y al otro son todos mayores (o habrían sido intercambiados). 

Operaciones
   Las operaciones de ordenamiento con quicksort, son el de elegir un pivote, el cual va a ser las comparaciones, y asi poder hacer comparaciones, ya que al tener el pivote podremos saber al momento de hacer las comparaciones, si movemos a la izquierda o a la derecha.

Video

Programa.

Bibliografia
http://es.wikipedia.org/wiki/Quicksort
http://www.genbetadev.com/algoritmos/implementando-el-algoritmo-quicksort

ORDENAMIENTO SHELLSORT.

Shellsort

Ordenamiento de disminución incremental.
Nombrado así debido a su inventor Donald Shell.
Ordena subgrupos de elementos separados K unidades (respecto de su posición en el arreglo) del arreglo original. El valor K es llamado incremento.
Después de que los primeros K subgrupos han sido ordenados (generalmente utilizando INSERCION DIRECTA), se escoge un nuevo valor de K más pequeño, y el arreglo es de nuevo partido entre el nuevo conjunto de subgrupos. Cada uno de los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de K.
Eventualmente el valor de K llega a ser 1, de tal manera que el subgrupo consiste de todo el arreglo ya casi ordenado.
Al principio del proceso se escoge la secuencia de decrecimiento de incrementos; el último valor debe ser 1.
"Es como hacer un ordenamiento de burbuja pero comparando e intercambiando elementos."
Cuando el incremento toma un valor de 1, todos los elementos pasan a formar parte del subgrupo y se aplica inserción directa.
El método se basa en tomar como salto N/2 (siendo N el número de elementos) y luego se va reduciendo a la mitad en cada repetición hasta que el salto o distancia vale 1.
Procedimiento Shell Sort;
const
MAXINC = _____;
incrementos = array[1..MAXINC] of integer;
var
j,p,num,incre,k:integer;
begin
for incre := 1 to MAXINC do begin /* para cada uno de los incrementos */
k := inc[incre]; /* k recibe un tipo de incremento */
for p := k+1 to MAXREG do begin /* inserción directa para el grupo que se encuentra cada K posiciones */
num := reg[p];
j := p-k;
while (j>0) AND (num < reg[j]) begin
reg[j+k] := reg[j];
j := j - k;
end;
reg[j+k] := num;
end
end
end;

Recorrido	Salto	Lista Ordenada	Intercambio
1	3	2,1,4,0,3,5,6	(6,2), (5,4), (6,0)
2	3	0,1,4,2,3,5,6	(2,0)
3	3	0,1,4,2,3,5,6	Ninguno
4	1	0,1,2,3,4,5,6	(4,2), (4,3)
5	1	0,1,2,3,4,5,6	Ninguno

video