El algoritmo de
ordenamiento "bubblesort" se basa en un recorrido secuencial de los datos con
intercambios simultáneos (swap) a partir de comparaciones. Para ello, utiliza una
variable temporal para evitar que los datos se pierdan al momento del swap.
Para demostrar este
algoritmo y analizar su eficiencia comúnmente se utiliza el ejemplo de un
arreglo de números enteros de una dimensión. En el siguiente programa utilizaremos un arreglo de
dos dimensiones. Nuestro objetivo será ver cómo se puede implementar este
algoritmo para ordenar una tabla en base a una columna en específico. Dicha
columna clave establecerá el orden de las filas y al momento de un swap se
moverá no solo el dato que se compara, sino también toda la fila que depende de
ese dato.
Si el arreglo está así:
Ordenado por la columna 1, de menor a mayor, queda así:
El programa está codificado
en lenguaje Java:
Código:
import java.util.Random;
/**
*
* author Joaquin Bolaños
*
* Demostración de ordenamiento de un arreglo
de dos dimensiones (tabla)
* en base a una de sus columnas, utilizando el
algoritmo bubblesort.
*
*
*/
public class BubleSort2D
{
public static void main(String[] args) {
int[][] arreglo = new int[10][2]; // La
tabla tendra 10 filas y dos columnas
int numero=0;
Random aleatorio = new Random();
// Generando datos para al tabla (enteros
aleatorios):
for (int i = 0; i<10 i="" o:p="">
{
for (int j=0; j<2 j="" o:p="">
{
numero = aleatorio.nextInt(10)
+ 1;
arreglo[i][j] = numero;
}
}
// Presentando el arreglo sin ordenar
System.out.println("ARREGLO SIN
ORDENAR:");
for (int i = 0; i<10 i="" o:p="">
{
for (int j=0; j<2 j="" o:p="">
{
System.out.print("" +
arreglo[i][j] + "-");
}
System.out.println("");
}
// Ordenando el arreglo por la columna
1 utlizando bublesort:
System.out.println("");
System.out.println("ARREGLO
ORDENADO POR LA COLUMNA 1:");
int temporal1, temporal2;
int menor = 0;
// Esta variable especifica en base a qué columna se va a ordenar el arreglo:
int columnaBase = 0;
for (int i = 0; i<10 i="" o:p="">
{
menor = arreglo[i][columnaBase];
for (int j = (i+1); j<10 j="" o:p="">
{
if (arreglo[j][columnaBase]
< menor)
{
// Variables de
almacenamiento temporal
// para evitar perder los
datos al momento del swap:
temporal1 = arreglo[i][0];
temporal2 = arreglo[i][1];
// Intercambios
arreglo[i][0] =
arreglo[j][0];
arreglo[i][1] =
arreglo[j][1];
arreglo[j][0] = temporal1;
arreglo[j][1] = temporal2;
menor =
arreglo[i][columnaBase];
}
}
}
// Presentando el arreglo ordenado por
la columna 1
for (int i = 0; i<10 i="" o:p="">
{
for (int j=0; j<2 j="" o:p="">
{
System.out.print("" +
arreglo[i][j] + "-");
}
System.out.println("");
}
}
}
Ejecución:
Del anterior código concluimos
que al ejecutar el algoritmo bubblesort para ordenar un arreglo bidimensional (tabla) en
base a una columna en específico:
- El número de intercambios a
realizar no necesariamente es igual al número de filas de la tabla.
- El número de variables
temporales a utilizar en este algoritmo será igual al número de columnas de la
tabla.
- Aunque sólo se ordena en
base a la columna clave, al momento de los intercambios se harán tantos swaps
como columnas tenga la tabla.
No hay comentarios:
Publicar un comentario