03.m Método para Ordenar - La Burbuja (4911) Veremos como funciona el método de la burbuja, para arrastrar datos de un lado a otro e irlos ordenando. contact Created,Modified 2009-04-10 08:32:16, 2009-05-07 19:12:59 Author,Nick Gustavo Guillermo Perez, (madgus) [myblog]

Métodos para ordenar listas

Veremos a continuación algunos pocos métodos para ordenar listas de datos, esto nos servirá para poder aplicar la búsqueda binaria sobre una lista de datos, aunque en la actualizad esto ya casi no se utiliza debido a que los motores de bases de datos ordenan los resultados (resultsets) de manera que ya no es necesario ordenar, se delega la tarea a programas optimizados para hacer eso de manera extraordinariamente rápida como MySQL compilado para el procesador de la PC.

Método de la burbuja o Método de Ordenación por Selección

Este método es antiguo y obsoleto, pero sirve para aprender, por su simpleza y porque para pocos elementos no consume muchos recursos, la idea es la siguiente: tenemos una lista de datos desordenada y comparamos los dos primeros y sólo esos dos los ordenamos de mayor a menor, el paso siguiente es comparar el que sigue con el anterior y así sucesivamente hasta llegar al final, si contamos las comparaciones, fueron el total de los datos de la lista, menos una porque son de dos en dos. Con cada pasada por la lista un dato queda ordenado, y el nombre de burbuja es porque podríamos imaginarnos una burbuja que se lleva nuestro dato más grande hacia abajo o hacia arriba dependiendo como estemos recorriendo la lista y como estemos ordenando, si de mayor a menor o menor a mayor.

Ilustración 3: Método de la burbuja o Método de Ordenación por Selección, para ordenar datos

Como podemos ver, para que la lista quede ordenada en el ejemplo de la ilustración anterior, debemos repetir el procedimiento N-1 veces, pero también como podemos ver ya que el elemento más grande quedó ordenado, podemos reducir el espacio de la burbuja desde el primer elemento al N-1-i donde i es el número de veces que se ha recorrido la lista para ordenarla, de esa manera reducimos la cantidad de comparaciones, que hace la burbuja para quedarse con el elemento más grande.

Veamos un ejemplo:

1. public static void burbuja_mayormenor(int[] listado){

2. int temporal;

3. for (int j = 0; j < listado.length - 1; j++) {

4. for (int i = 0; i < listado.length - 1; i++) {

5. if (listado[i] < listado[i + 1]) {

6. temporal = listado[i + 1];

7. listado[i + 1] = listado[i];

8. listado[i] = temporal;

9. }

10. }

11. }

12. } //final metodo ordenar burbuja mayor menor

la función descrita arriba ordena de mayor a menor los elementos de la lista, la lista es un arreglo de números enteros que se recorre de la misma manera que en la Ilustración 3 sólo que se compara de manera que el más pequeño sea el que se queda, en la linea 3 repetimos el proceso N cantidad de veces, ya que la burbuja ordena de 1 elemento por pasada y el proceso de recorrido empieza en la línea 4, en la línea 5 se hace la comparación y dado el caso se dan vuelta los elementos utilizando una variable temporal del mismo tipo que almacena el arreglo.

Ahora veamos como acotar los recorridos para reducir la cantidad de comparaciones:

1. public static void ordenar_burbuja_mayormenor(int[] listado){

2. int temporal;

3. for (int j = listado.length - 1; j > 0; j--) {

4. for (int i = 0; i < j; i++) {

5. if (listado[i] < listado[i + 1]) {

6. temporal = listado[i + 1];

7. listado[i + 1] = listado[i];

8. listado[i] = temporal;

9. }

10. }

11. }

12. }//final metodo ordenar burbuja mayor menor

Este ejemplo es idéntico al anterior sólo que ahora la línea 3 no sólo se utiliza para contar la cantidad de veces que tenemos que recorrer el arreglo sino que va decreciendo para que el recorrido siempre sea un elemento menos, es decir el que quedó ordenado no se vuelve a comparar.

Nota: Queda como ejercicio para el lector construir las dos funciones inversas, las que ordenan de menor a mayor, y la que ordena de menor a mayor acotando las comparaciones.

leavecomment

---