Cuatro algoritmos de ordenación para ordenar una lista de elementos

COMPARTIR 0 TWITTEAR

algoritmos_ordenacion

Siguiendo con nuestro de programación en esta ocasión vamos a ver los algoritmos más conocidos para ordenar una lista de elementos. Estos algoritmos los podemos clasificar en dos grandes grupos según su complejidad:

  • Algoritmos de complejidad cuadrática: Ordenamiento de burbuja (Bubblesort), ordenamiento por selección (Selection Sort) y ordenamiento por inserción (Insertion sort) entre otros, hay muchos más.
  • Algoritmos de complejidad cuasi lineal o O(nlog(n)): solo veremos el rrdenamiento rápido o Quicksort pues para mi es el más sencillo de implementar y uno de los más eficaces aunque presente un cierto grado de inestabilidad.

Algoritmos de ordenación

Debemos tener claro lo que deben hacer estos algoritmos y básicamente es que a partir de una lista de elementos nuestros algoritmos la deben ordenar correctamente. Una práctica habitual, y como se debe empezar a desarrollar, es desarrollar siempre las pruebas más triviales antes de ponerse a desarrollar el algoritmo. También es recomendable definir las cabeceras de los métodos, para que no de errores de compilación la prueba.

Vamos a definir las cabeceras de nuestra clase. Nos centraremos únicamente en los métodos públicos, pues en la JUnits únicamente debemos interesarnos por el comportamiento de los métodos a los que podrá acceder el cliente.

package source;

public class Ordena {

/**
 * Ordenación por el método de Burbuja
 * 
 * @param a
 *            array de enteros, después de la llamada quedará ordenado
 */
public static void burbuja(int[] a) {

}

/**
 * Ordenación por inserción directa
 * 
 * @param a
 *            array de enteros, después de la llamada quedará ordenado
 */
public static void insercion(int[] a) {

}

/**
 * Ordenación por el método rápido (quicksort) 
 */
public static void rapido(int[] v) {

}

/**
 * Ordenación por selección
 * 
 * @param v
 *            array de enteros, después de la llamada quedará ordenado
 */
public static void seleccion(int[] v) {

}

}

Vamos a definir la siguiente prueba unitaria:

package pruebas;
import static org.junit.Assert.*;
import org.junit.Test;
import source.Ordena;

@SuppressWarnings("static-access")
public class OrdenacionTest {

Ordena o = new Ordena();

@Test
public void testBurbuja() {
    int[] comprueba = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int[] ordenados = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int[] inverso = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
    int[] random = { 1, 0, 4, 3, 5, 10, 8, 9, 2, 6, 7 };

    o.burbuja(ordenados);
    assertArrayEquals(comprueba, ordenados);
    o.burbuja(inverso);
    assertArrayEquals(comprueba, inverso);
    o.burbuja(random);
    assertArrayEquals(comprueba, random);

}

@Test
public void testSeleccion() {
    int[] comprueba = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int[] ordenados = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int[] inverso = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
    int[] random = { 1, 0, 4, 3, 5, 10, 8, 9, 2, 6, 7 };

    o.seleccion(ordenados);
    assertArrayEquals(comprueba, ordenados);
    o.seleccion(inverso);
    assertArrayEquals(comprueba, inverso);
    o.seleccion(random);
    assertArrayEquals(comprueba, random);

}

@Test
public void testRapido() {
    int[] comprueba = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int[] ordenados = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int[] inverso = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
    int[] random = { 1, 0, 4, 3, 5, 10, 8, 9, 2, 6, 7 };

    o.rapido(ordenados);
    assertArrayEquals(comprueba, ordenados);
    o.rapido(inverso);
    assertArrayEquals(comprueba, inverso);
    o.rapido(random);
    assertArrayEquals(comprueba, random);

}

@Test
public void testInserccion() {
    int[] comprueba = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int[] ordenados = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int[] inverso = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
    int[] random = { 1, 0, 4, 3, 5, 10, 8, 9, 2, 6, 7 };

    o.insercion(ordenados);
    assertArrayEquals(comprueba, ordenados);
    o.insercion(inverso);
    assertArrayEquals(comprueba, inverso);
    o.insercion(random);
    assertArrayEquals(comprueba, random);

}
}

Con la pruebas listas ya estamos preparados para programar nuestros algoritmos de ordenación. Algunos de los métodos utilizan una serie de algoritmos auxiliares:

private static void permuta(int[] a, int i, int j) {
    int t;
    t = a[i];
    a[i] = a[j];
    a[j] = t;
}

Lo que hace es cambiar dos elementos de sitio

private static int particion(int[] v, int iz, int de) {
    int i, pivote;
    permuta(v, (iz + de) / 2, iz);
    // el pivote es el de centro y se cambia con el primero
    pivote = v[iz];
    i = iz;
    for (int s = iz + 1; s <= de; s++)
        if (v[s] <= pivote) {
            i++;
            permuta(v, i, s);
        }
    permuta(v, iz, i);// se restituye el pivote donde debe estar
    return i; // retorna la posicion en que queda el pivote
}

Método que va subdividiendo la lista en listas más pequeñas. Es un procedimiento recursivo denominado divide y vencerás.

Burbuja

El funcionamiento del algoritmo lo podéis ver desde su entrada de la wikipedia

Código:

public static void burbuja(int[] a) {
    int n = a.length;
    for (int i = 0; i <= n - 2; i++)
        for (int j = n - 1; j > i; j--)
            if (a[j - 1] > a[j])
                permuta(a, j - 1, j);
}

Inserción

El funcionamiento del algoritmo lo podéis ver desde su entrada de la wikipedia

Código:

public static void insercion(int[] a) {
    int n = a.length;
    for (int i = 1; i <= n - 1; i++) {
        int x = a[i];
        int j = i - 1;
        while (j >= 0 && x < a[j]) {
            a[j + 1] = a[j];
            j = j - 1;
        }
        a[j + 1] = x;
    }
}

Selección

El funcionamiento del algoritmo lo podéis ver desde su entrada de la wikipedia

Código:

public static void seleccion(int[] v) {
    int n = v.length;
    int posmin;
    for (int i = 0; i < n - 1; i++) {
        posmin = i;
        for (int j = i + 1; j < n; j++)
            if (v[j] < v[posmin])
                posmin = j;// posicion del mas pequeño
        permuta(v, i, posmin);
    } // for
}

Quicksort

El funcionamiento del algoritmo lo podéis ver desde su entrada de la wikipedia

Código:

private static void rapirec(int[] v, int iz, int de) {
    int m;
    if (de > iz) {
        m = particion(v, iz, de);
        rapirec(v, iz, m - 1);
        rapirec(v, m + 1, de);
    }
}

public static void rapido(int[] v) {
    rapirec(v, 0, v.length - 1);
}

Que algoritmo es mejor

Como siempre para comprobar esto tenemos que medir tiempos. Para ello haremos usado de tres métodos auxiliares para generar listas de tamaños grandes. Ponemos los siguientes métodos en nuestra clase pruebas:

/**
 * Este método da valores ordenados
 */
private void ordenDirecto(int[] a) {
    int n = a.length;
    for (int i = 0; i < n; i++)
        a[i] = i;
}

/**
 * Este método da valores ordenados
 */
private void ordenInverso(int[] a) {
    int n = a.length;
    for (int i = 0; i < n; i++)
        a[i] = n - i - 1;
}

/**
 * Este método da valores aleatorios a un vector de enteros, utiliza para
 * ello la clase Random del paquete java.util
 */
private void aleatorio(int[] a) {
    Random r = new Random();
    int n = a.length;
    for (int i = 0; i < n; i++)
        a[i] = r.nextInt(1000000);// valores entre 0 y 999999
}

Y para medir los tiempos podemos usar un método similar a este:

@Test
public void testTiempos() {
    for (int n = 10000; n < 1000000000; n *= 2) {
        int[] v = new int[n];
        ordenDirecto(v); // forma de generar la lista
        double t1 = System.currentTimeMillis();
        o.seleccion(v); // ordenación
        double t2 = System.currentTimeMillis();
        System.out.println("n=" + n + "**TIEMPO=" + (t2 - t1));
    }
}

Vamos cambiando la forma de generar cada lista y el método de ordenación. Cuando lo hagamos con todas las combinaciones posibles tendremos un Excel similar a este. Debemos fijarnos que los algoritmos que hemos hecho solo funcionan para listas de enteros, podemos hacer que los algoritmos funcionen para cualquier tipo de objeto Comparable debemos hacer que nuestro método tenga por parámetro un tipo T comparable.

public void insercionComparable(T[] a) {
    int n = a.length;
    for (int i = 1; i <= n - 1; i++) {
        T x = a[i];
        int j = i - 1;
        while (j >= 0 && x.compareTo(a[j]) < 0) {
            a[j + 1] = a[j];
            j = j - 1;
        }
        a[j + 1] = x;
    }
}

Y además tenemos que acotar la genericidad de nuestra clase añadiendo el siguiente código a la cabecera de nuestra clase Ordena:

public class Ordena <T extends Comparable<T>> 

Podemos probar que funciona con por ejemplo objetos de tipo Persona con la siguiente prueba:

@Test
public void testInserccionGenerico() {
    Persona[] comprueba = { new Persona(0), new Persona(1), new Persona(2),
            new Persona(3), new Persona(4), new Persona(5), new Persona(6) };
    Persona [] random = { new Persona(5), new Persona(3), new Persona(2),
            new Persona(1), new Persona(4), new Persona(0), new Persona(6) };

    o.insercionComparable(random);
    assertArrayEquals(comprueba, random);
 }

Hasta aquí el artículo de hoy. Como siempre aquí tenéis el código fuente empleado.

Archivado en Algoritmia, Curso de Programación, Java
COMPARTIR 0 TWITTEAR

Comentarios (19)

Usa tu cuenta de Facebook para dejar tu opinión.

¿Te ha gustado? ¡No te pierdas nada más!

follow us in feedly

Otras webs de Difoosion