Clasificación de cubos en Java

1. Introducción

En este artículo, nos sumergiremos en el algoritmo de clasificación de cubos. Comenzaremos con un poco de teoría, antes de trabajar en la implementación de Java junto con la prueba unitaria de nuestra solución. Finalmente, veremos la complejidad temporal de la clasificación de cubos.

2. La teoría de la clasificación por cubos

La clasificación de depósitos, a veces conocida como clasificación de contenedores, es un algoritmo de clasificación específico. La clasificación funciona distribuyendo los elementos que queremos clasificar en varios grupos clasificados individualmente. Al hacer esto, podemos reducir la cantidad de comparaciones entre los elementos y ayudar a reducir el tiempo de clasificación.

Echemos un vistazo rápido a los pasos necesarios para realizar una clasificación de depósito :

  1. Configure una matriz de nuestros depósitos inicialmente vacíos
  2. Distribuir nuestros elementos en sus cubos apropiados
  3. Ordenar cada cubo
  4. Concatenar los depósitos ordenados juntos para recrear la lista completa

3. Implementación de Java

Si bien este algoritmo no es específico del idioma, implementaremos el ordenamiento en Java. Repasemos la lista anterior paso a paso y escribamos el código para ordenar una lista de números enteros.

3.1. Configuración del depósito

Primero, necesitamos determinar un algoritmo de hash para decidir cuál de nuestros elementos se coloca en qué depósito:

private int hash(int i, int max, int numberOfBuckets) { return (int) ((double) i / max * (numberOfBuckets - 1)); }

Con nuestro método hash definido, ahora podemos especificar el número de bins como una raíz cuadrada del tamaño de la lista de entrada :

final int numberOfBuckets = (int) Math.sqrt(initialList.size()); List
    
      buckets = new ArrayList(numberOfBuckets); for(int i = 0; i < numberOfBuckets; i++) { buckets.add(new ArrayList()); }
    

Finalmente, necesitamos un método corto para determinar el número entero máximo en nuestra lista de entrada:

private int findMax(List input) { int m = Integer.MIN_VALUE; for (int i : input) { m = Math.max(i, m); } return m; }

3.2. Distribuyendo los elementos

Ahora que tenemos nuestros depósitos definidos, podemos distribuir cada elemento de nuestra lista de entrada en su depósito relevante usando el método hash :

int max = findMax(initialList); for (int i : initialList) { buckets.get(hash(i, max, numberOfBuckets)).add(i); } 

3.3. Clasificación de los cubos individuales

Con nuestros cubos definidos y llenos de enteros, usemos un Comparador para ordenarlos :

Comparator comparator = Comparator.naturalOrder(); for(List bucket : buckets){ bucket.sort(comparator); }

3.4. Concatenar nuestros baldes

Finalmente, necesitamos juntar nuestros depósitos para recrear la lista única. Dado que nuestros depósitos están ordenados, solo necesitamos recorrer cada depósito una vez y agregar los elementos a una lista maestra:

List sortedArray = new LinkedList(); for(List bucket : buckets) { sortedArray.addAll(bucket); } return sortedArray;

4. Prueba de nuestro código

Con nuestra implementación completa, escribamos una prueba unitaria rápida para asegurarnos de que funciona como se esperaba:

BucketSorter sorter = new IntegerBucketSorter(); List unsorted = Arrays.asList(80,50,60,30,20,10,70,0,40,500,600,602,200,15); List expected = Arrays.asList(0,10,15,20,30,40,50,60,70,80,200,500,600,602); List sorted = sorter.sort(unsorted); assertEquals(expected, sorted);

5. Complejidad del tiempo

A continuación, echemos un vistazo rápido a la complejidad temporal de realizar una clasificación de depósito.

5.1. Peor de los casos

En el peor de los casos, encontraríamos todos nuestros elementos en el mismo depósito y en orden inverso. Cuando ocurre este caso, estamos reduciendo nuestra clasificación de cubos a una clasificación simple en la que cada elemento se compara con cualquier otro elemento, lo que produce una complejidad de tiempo de O (n²) .

5.2. Escenario de caso promedio

En nuestro caso promedio, encontramos que los elementos se distribuyen de manera relativamente uniforme entre nuestros depósitos de entrada. Dado que cada uno de nuestros pasos requiere solo una iteración a través de nuestros depósitos de entrada, encontramos que nuestra clasificación de depósitos se completa en O (n) tiempo .

6. Conclusión

En este artículo, vimos cómo implementar una ordenación de cubos en Java. También analizamos la complejidad temporal del algoritmo de clasificación de cubos.

Como siempre, el código que se muestra en este artículo está disponible en GitHub.