Algoritmos de clasificación en Java

En este tutorial, implementaremos muchos algoritmos de clasificación en Java con ejemplos. Esto incluye la clasificación por burbujas, la clasificación por inserción, la clasificación por selección, la clasificación por fusión, la clasificación en montón y la clasificación rápida.

Introducción

Ordenar datos significa organizarlos en un cierto orden, a menudo en una estructura de datos similar a una matriz. Puede utilizar varios criterios de ordenación, siendo los más comunes la ordenación de números de menor a mayor o viceversa, o la ordenación de cadenas lexicográficamente. Incluso puede definir sus propios criterios, y veremos formas prácticas de hacerlo al final de este artículo.

Si está interesado en cómo funciona la clasificación, cubriremos varios algoritmos, desde soluciones ineficientes pero intuitivas hasta algoritmos eficientes que se implementan en Java y otros lenguajes.

Hay varios algoritmos de clasificación, y no todos son igualmente eficientes. Estaremos analizando su complejidad del tiempo para compararlos y ver cuales funcionan mejor.

La lista de algoritmos que aprenderá aquí no es exhaustiva, pero hemos compilado algunos de los más comunes y eficientes para ayudarlo a comenzar.

Nota: este artículo no se ocupará de la clasificación simultánea, ya que está destinado a principiantes.

Clasificación por burbujas {#clasificación por burbujas}

Explicación

La ordenación de burbujas funciona intercambiando elementos adyacentes si no están en el orden deseado. Este proceso se repite desde el comienzo de la matriz hasta que todos los elementos estén en orden.

Sabemos que todos los elementos están en orden cuando logramos hacer la iteración completa sin intercambiar nada; entonces, todos los elementos que comparamos estaban en el orden deseado con sus elementos adyacentes y, por extensión, la matriz completa.

Estos son los pasos para ordenar una matriz de números de menor a mayor:

  • 4 2 1 5 3: Los dos primeros elementos están en el orden incorrecto, así que los intercambiamos.

  • 2 4 1 5 3: Los segundos dos elementos también están en el orden incorrecto, así que intercambiamos.

  • 2 1 4 5 3: Estos dos están en el orden correcto, 4 < 5, así que los dejamos solos.

  • 2 1 4 5 3: Otro intercambio.

  • 2 1 4 3 5: Aquí está la matriz resultante después de una iteración.

Debido a que ocurrió al menos un intercambio durante el primer paso (en realidad hubo tres), debemos revisar toda la matriz nuevamente y repetir el mismo proceso.

Al repetir este proceso, hasta que no se realicen más intercambios, tendremos una matriz ordenada.

La razón por la que este algoritmo se llama Bubble Sort es porque los números parecen "burbujear" en la "superficie". Lo verás moviéndose lentamente hacia la derecha durante el proceso.

Todos los números se mueven a sus respectivos lugares poco a poco, de izquierda a derecha, como burbujas que se elevan lentamente desde un cuerpo de agua.

Si desea leer un artículo detallado y dedicado a Clasificación de burbujas, ¡lo tenemos cubierto!

Implementación

Vamos a implementar Bubble Sort de manera similar a como lo hemos presentado en palabras. Nuestra función entra en un bucle while en el que pasa por todo el arreglo cambiando según sea necesario.

Suponemos que la matriz está ordenada, pero si se demuestra que estamos equivocados durante la clasificación (si ocurre un intercambio), pasamos por otra iteración. El bucle while continúa hasta que logramos pasar por todo el conjunto sin intercambiar:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public static void bubbleSort(int[] a) {
    boolean sorted = false;
    int temp;
    while(!sorted) {
        sorted = true;
        for (int i = 0; i < array.length - 1; i++) {
            if (a[i] > a[i+1]) {
                temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
                sorted = false;
            }
        }
    }
}

Al usar este algoritmo, debemos tener cuidado con la forma en que establecemos nuestra condición de intercambio.

Por ejemplo, si hubiera usado a[i] >= a[i+1] podría haber terminado con un bucle infinito, porque para elementos iguales esta relación siempre sería verdadera y, por lo tanto, siempre los intercambiaría.

Complejidad del tiempo

Para determinar la complejidad del tiempo de Bubble Sort, debemos analizar el peor escenario posible. ¿Cuál es la cantidad máxima de veces que necesitamos pasar por toda la matriz antes de ordenarla? Considere el siguiente ejemplo:

1
5 4 3 2 1

En la primera iteración, 5 “saldrá a la superficie”, pero el resto de los elementos permanecerán en orden descendente. Tendríamos que hacer una iteración para cada elemento excepto 1, y luego otra iteración para comprobar que todo está en orden, por lo que un total de 5 iteraciones.

Expanda esto a cualquier matriz de n elementos, y eso significa que necesita hacer n iteraciones. Mirando el código, eso significaría que nuestro bucle while puede ejecutarse un máximo de n veces.

Cada una de esas n veces estamos iterando a través de toda la matriz (bucle for en el código), lo que significa que la complejidad de tiempo en el peor de los casos sería O(n^2).

Nota: La complejidad del tiempo siempre sería O(n^2) si no fuera por la verificación booleana ordenada, que finaliza el algoritmo si no hay ninguna. se intercambia dentro del bucle interno, lo que significa que la matriz está ordenada.

Clasificación por inserción

Explicación

La idea detrás de la ordenación por inserción es dividir la matriz en subarreglos ordenados y sin clasificar.

La parte ordenada tiene una longitud de 1 al principio y corresponde al primer elemento (más a la izquierda) de la matriz. Iteramos a través de la matriz y, durante cada iteración, expandimos la parte ordenada de la matriz en un elemento.

Al expandir, colocamos el nuevo elemento en su lugar adecuado dentro del subarreglo ordenado. Hacemos esto moviendo todos los elementos a la derecha hasta que encontramos el primer elemento que no tenemos que mover.

Por ejemplo, si en la siguiente matriz la parte en negrita se ordena de forma ascendente, ocurre lo siguiente:

  • 3 5 7 8 4 2 1 9 6: Tomamos 4 y recordamos que eso es lo que necesitamos insertar. Como 8 > 4, cambiamos.

  • 3 5 7 x 8 2 1 9 6: Donde el valor de x no tiene una importancia crucial, ya que se sobrescribirá inmediatamente (ya sea por 4 si es su lugar apropiado o por 7 si lo desplazamos ). Como 7 > 4, cambiamos.

  • 3 5 x 7 8 2 1 9 6

  • 3x5 7 8 2 1 9 6

  • 3 4 5 7 8 2 1 9 6

Después de este proceso, la parte ordenada se amplió en un elemento, ahora tenemos cinco en lugar de cuatro elementos. Cada iteración hace esto y al final tendremos todo el conjunto ordenado.

Si desea leer un artículo detallado y dedicado a Tipo de inserción, ¡lo tenemos cubierto!

Implementación

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
public static void insertionSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int current = array[i];
        int j = i - 1;
        while(j >= 0 && current < array[j]) {
            array[j+1] = array[j];
            j--;
        }
        // at this point we've exited, so j is either -1
        // or it's at the first element where current >= a[j]
        array[j+1] = current;
    }
}

Complejidad del tiempo

Nuevamente, tenemos que mirar el peor de los casos para nuestro algoritmo, y nuevamente será el ejemplo en el que toda la matriz desciende.

Esto se debe a que en cada iteración, tendremos que mover toda la lista ordenada en uno, que es O(n). Tenemos que hacer esto para cada elemento en cada matriz, lo que significa que estará delimitado por O(n^2).

Clasificación de selección

Explicación

Selection Sort también divide el arreglo en un subarreglo ordenado y no ordenado. Aunque, esta vez, el subarreglo ordenado se forma insertando el elemento mínimo del subarreglo no ordenado al final del arreglo ordenado, intercambiando:

  • 3 5 1 2 4

  • 1 5 3 2 4

  • 1 2 3 5 4

  • 1 2 3 5 4

  • 1 2 3 4 5

  • 1 2 3 4 5

Implementación

En cada iteración, asumimos que el primer elemento sin clasificar es el mínimo e iteramos a través del resto para ver si hay un elemento más pequeño.

Una vez que encontramos el mínimo actual de la parte no ordenada de la matriz, lo intercambiamos con el primer elemento y lo consideramos parte de la matriz ordenada:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public static void selectionSort(int[] array) {
    for (int i = 0; i < array.length; i++) {
        int min = array[i];
        int minId = i;
        for (int j = i+1; j < array.length; j++) {
            if (array[j] < min) {
                min = array[j];
                minId = j;
            }
        }
        // swapping
        int temp = array[i];
        array[i] = min;
        array[minId] = temp;
    }
}

Complejidad del tiempo

Encontrar el mínimo es O(n) para la longitud de la matriz porque tenemos que verificar todos los elementos. Tenemos que encontrar el mínimo para cada elemento de la matriz, haciendo que todo el proceso esté acotado por O(n^2).

Clasificación por combinación

Explicación

Merge Sort usa recursión para resolver el problema de ordenar de manera más eficiente que los algoritmos presentados anteriormente, y en particular usa [divide y conquistaras](https://en. wikipedia.org/wiki/Divide-and-conquer_algorithm) enfoque.

Usando estos dos conceptos, dividiremos la matriz completa en dos subarreglos y luego:

  1. Ordenar la mitad izquierda de la matriz (recursivamente)
  2. Ordenar la mitad derecha de la matriz (recursivamente)
  3. Combinar las soluciones

Merge Sort Illustration

Este árbol está destinado a representar cómo funcionan las llamadas recursivas. Las matrices marcadas con la flecha hacia abajo son para las que llamamos a la función, mientras fusionamos las de la flecha hacia arriba que vuelven a subir. Entonces, siga la flecha hacia abajo hasta la parte inferior del árbol, y luego vuelva a subir y fusione.

En nuestro ejemplo, tenemos la matriz 3 5 3 2 1, por lo que la dividimos en 3 5 4 y 2 1. Para ordenarlos, los dividimos aún más en sus componentes. Una vez que hemos llegado al final, comenzamos a fusionarlos y ordenarlos a medida que avanzamos.

Si desea leer un artículo detallado y dedicado a Ordenar por combinación, ¡lo tenemos cubierto!

Implementación

La función principal funciona más o menos como se describe en la explicación. Solo estamos pasando los índices ‘izquierda’ y ‘derecha’, que son índices del elemento más a la izquierda y más a la derecha del subarreglo que queremos ordenar. Inicialmente, estos deberían ser 0 y array.length-1, dependiendo de la implementación.

La base de nuestra recursividad asegura que salgamos cuando hayamos terminado, o cuando derecha e izquierda se encuentren. Encontramos un punto medio mid y clasificamos los subarreglos a la izquierda y a la derecha recursivamente, en última instancia, fusionando nuestras soluciones.

Si recuerda nuestro gráfico de árbol, es posible que se pregunte por qué no creamos dos nuevas matrices más pequeñas y las pasamos en su lugar. Esto se debe a que en arreglos realmente largos, esto causaría un gran consumo de memoria para algo que es esencialmente innecesario.

Merge Sort ya no funciona en el lugar debido al paso de combinación, y esto solo serviría para empeorar la eficiencia de la memoria. Sin embargo, la lógica de nuestro árbol de recursividad permanece igual, solo tenemos que seguir los índices que estamos usando:

1
2
3
4
5
6
7
public static void mergeSort(int[] array, int left, int right) {
    if (right <= left) return;
    int mid = (left+right)/2;
    mergeSort(array, left, mid);
    mergeSort(array, mid+1, right);
    merge(array, left, mid, right);
}

Para fusionar los subarreglos ordenados en uno, necesitaremos calcular la longitud de cada uno y crear arreglos temporales para copiarlos, de modo que podamos cambiar libremente nuestro arreglo principal.

Después de copiar, revisamos la matriz resultante y le asignamos el mínimo actual. Debido a que nuestros subarreglos están ordenados, simplemente elegimos el menor de los dos elementos que no se han elegido hasta ahora y movemos el iterador para ese subarreglo hacia adelante:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 void merge(int[] array, int left, int mid, int right) {
    // calculating lengths
    int lengthLeft = mid - left + 1;
    int lengthRight = right - mid;

    // creating temporary subarrays
    int leftArray[] = new int [lengthLeft];
    int rightArray[] = new int [lengthRight];

    // copying our sorted subarrays into temporaries
    for (int i = 0; i < lengthLeft; i++)
        leftArray[i] = array[left+i];
    for (int i = 0; i < lengthRight; i++)
        rightArray[i] = array[mid+i+1];

    // iterators containing current index of temp subarrays
    int leftIndex = 0;
    int rightIndex = 0;

    // copying from leftArray and rightArray back into array
    for (int i = left; i < right + 1; i++) {
        // if there are still uncopied elements in R and L, copy minimum of the two
        if (leftIndex < lengthLeft && rightIndex < lengthRight) {
            if (leftArray[leftIndex] < rightArray[rightIndex]) {
                array[i] = leftArray[leftIndex];
                leftIndex++;
            }
            else {
                array[i] = rightArray[rightIndex];
                rightIndex++;
            }
        }
        // if all the elements have been copied from rightArray, copy the rest of leftArray
        else if (leftIndex < lengthLeft) {
            array[i] = leftArray[leftIndex];
            leftIndex++;
        }
        // if all the elements have been copied from leftArray, copy the rest of rightArray
        else if (rightIndex < lengthRight) {
            array[i] = rightArray[rightIndex];
            rightIndex++;
        }
    }
}

Complejidad del tiempo

Si queremos derivar la complejidad de los algoritmos recursivos, vamos a tener que ser un poco matemáticos.

El teorema del maestro se usa para averiguar la complejidad temporal de los algoritmos recursivos. Para algoritmos no recursivos, normalmente podríamos escribir la complejidad temporal precisa como una especie de ecuación, y luego usamos [Notación O grande](/notacion-big-o-y-analisis-de-algoritmos-con-ejemplos-de- python/) para ordenarlos en clases de algoritmos de comportamiento similar.

El problema con los algoritmos recursivos es que esa misma ecuación se vería así:

$$
T(n) = aT(\frac{n}{b}) + cn^k
$$

¡La ecuación en sí es recursiva! En esta ecuación, a nos dice cuántas veces llamamos a la recursividad, y b nos dice en cuántas partes se divide nuestro problema. En este caso, puede parecer una distinción sin importancia porque son iguales para mergesort, pero para algunos problemas pueden no serlo.

El resto de la ecuación es la complejidad de fusionar todas esas soluciones en una sola al final. El Teorema del Maestro nos resuelve esta ecuación:

$$
T(n) = \Grande\{
\begin{matriz}
O(n^{log_ba}), & a>b^k \\ O(n^klog n), & a = b^k \\ O(n^k), & a < b^k
\end{matriz}
$$

Si T(n) es el tiempo de ejecución del algoritmo al clasificar una matriz de longitud n, Merge Sort se ejecutaría dos veces para matrices que tienen la mitad de la longitud de la matriz original.

Así que si tenemos a=2, b=2. El paso de fusión requiere memoria O(n), por lo que k=1. Esto significa que la ecuación para Merge Sort se vería de la siguiente manera:

$$
T(n) = 2T(\frac{n}{2})+cn
$$

Si aplicamos el Teorema del Maestro, veremos que nuestro caso es aquel donde a=b^k porque tenemos 2=2^1. Eso significa que nuestra complejidad es O(nlog n). Esta es una complejidad de tiempo extremadamente buena para un algoritmo de clasificación, ya que se ha demostrado que una matriz no se puede clasificar más rápido que O(nlog n).

Si bien la versión que mostramos consume mucha memoria, hay versiones más complejas de Merge Sort que ocupan solo O(1) espacio.

Además, el algoritmo es extremadamente fácil de paralelizar, ya que las llamadas recursivas desde un nodo se pueden ejecutar de forma completamente independiente desde ramas separadas. Si bien no entraremos en cómo y por qué, ya que está más allá del alcance de este artículo, vale la pena tener en cuenta las ventajas de usar este algoritmo en particular.

Heapsort

Explicación

Para comprender correctamente por qué funciona Heapsort, primero debe comprender la estructura en la que se basa: el montón. Hablaremos específicamente en términos de un montón binario, pero también puede generalizar la mayor parte de esto a otras estructuras de montón.

Un montón es un árbol que satisface la propiedad del montón, que es que para cada nodo, todos sus hijos están en una relación determinada con él. Además, un montón debe estar casi completo. Un árbol binario casi completo de profundidad d tiene un subárbol de profundidad d-1 con la misma raíz que está completo, y en el que cada nodo con descendiente izquierda tiene un subárbol izquierdo completo. En otras palabras, al agregar un nodo, siempre buscamos la posición más a la izquierda en el nivel incompleto más alto.

Si el montón es un montón máximo, entonces todos los hijos son más pequeños que el padre, y si es un montón mínimo, todos ellos son más grandes.

En otras palabras, a medida que avanza por el árbol, obtiene números cada vez más pequeños (min-heap) o números cada vez mayores (max-heap). Aquí hay un ejemplo de un montón máximo:

Max Heap

Podemos representar este montón máximo en la memoria como una matriz de la siguiente manera:

1
8 5 6 3 1 2 4

Puede imaginarlo leyendo el gráfico nivel por nivel, de izquierda a derecha. Lo que hemos logrado con esto es que si tomamos el elemento kth en la matriz, las posiciones de sus hijos son 2*k+1 y 2*k+2 (asumiendo que la indexación comienza en 0) . Puedes comprobar esto por ti mismo.

Por el contrario, para el elemento kth, la posición del padre siempre es (k-1)/2.

Sabiendo esto, puede fácilmente "max-heapify" cualquier matriz dada. Para cada elemento, comprueba si alguno de sus hijos es más pequeño que él. Si lo son, intercambie uno de ellos con el padre y repita recursivamente este paso con el padre (porque el nuevo elemento grande aún podría ser más grande que su otro hijo).

Las hojas no tienen hijos, por lo que son trivialmente * montones máximos * propios:

  • 6 1 8 3 5 2 4: Ambos hijos son más pequeños que el padre, por lo que todo permanece igual.

  • 6 1 8 3 5 2 4: Porque 5 > 1, los intercambiamos. Acumulamos recursivamente por 5 ahora.

  • 6 5 8 3 1 2 4: Ambos niños son más pequeños, así que no pasa nada.

  • 6 5 8 3 1 2 4: Porque 8 > 6, los intercambiamos.

  • 8 5 6 3 1 2 4: ¡Tenemos el montón que se muestra arriba!

Una vez que hemos aprendido a acumular una matriz, el resto es bastante simple. Intercambiamos la raíz del montón con el final de la matriz y acortamos la matriz en uno.

Volvemos a amontonar la matriz acortada y repetimos el proceso:

  • 8 5 6 3 1 2 4

  • 4 5 6 3 1 2 8: intercambiado

  • 6 5 4 3 1 2 8: amontonado

  • 2 5 4 3 1 6 8: intercambiado

  • 5 2 4 2 1 6 8: amontonado

  • 1 2 4 2 5 6 8: intercambiado

Y así sucesivamente, estoy seguro de que puedes ver el patrón emergente.

Implementación

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
static void heapify(int[] array, int length, int i) {
    int leftChild = 2*i+1;
    int rightChild = 2*i+2;
    int largest = i;

    // if the left child is larger than parent
    if (leftChild < length && array[leftChild] > array[largest]) {
        largest = leftChild;
    }

    // if the right child is larger than parent
    if (rightChild < length && array[rightChild] > array[largest]) {
        largest = rightChild;
    }

    // if a swap needs to occur
    if (largest != i) {
        int temp = array[i];
        array[i] = array[largest];
        array[largest] = temp;
        heapify(array, length, largest);
    }
}

public static void heapSort(int[] array) {
    if (array.length == 0) return;

    // Building the heap
    int length = array.length;
    // we're going from the first non-leaf to the root
    for (int i = length / 2-1; i >= 0; i--)
        heapify(array, length, i);

    for (int i = length-1; i >= 0; i--) {
        int temp = array[0];
        array[0] = array[i];
        array[i] = temp;

        heapify(array, i, 0);
    }
}

Complejidad del tiempo

Cuando observamos la función heapify(), todo parece estar hecho en O(1), pero luego está esa molesta llamada recursiva.

¿Cuántas veces se llamará eso, en el peor de los casos? Bueno, en el peor de los casos, se propagará hasta la parte superior del montón. Lo hará saltando al padre de cada nodo, alrededor de la posición i/2. eso significa que, en el peor de los casos, hará saltos log n antes de llegar a la cima, por lo que la complejidad es O(log n).

Debido a que heapSort() es claramente O(n) debido a los bucles for que iteran a través de toda la matriz, esto haría que la complejidad total de Heapsort sea O(nlog n).

Heapsort es una ordenación in situ, lo que significa que ocupa O(1) espacio adicional, a diferencia de Merge Sort, pero también tiene algunos inconvenientes, como que es difícil de paralelizar.

Ordenación rápida

Explicación

Quicksort es otro algoritmo Divide and Conquer. Elige un elemento de una matriz como pivote y ordena todos los demás elementos a su alrededor, por ejemplo, los elementos más pequeños a la izquierda y los más grandes a la derecha.

Esto garantiza que el pivote esté en su lugar correcto después del proceso. Luego, el algoritmo recursivamente hace lo mismo para las partes izquierda y derecha de la matriz.

Implementación

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
static int partition(int[] array, int begin, int end) {
    int pivot = end;

    int counter = begin;
    for (int i = begin; i < end; i++) {
        if (array[i] < array[pivot]) {
            int temp = array[counter];
            array[counter] = array[i];
            array[i] = temp;
            counter++;
        }
    }
    int temp = array[pivot];
    array[pivot] = array[counter];
    array[counter] = temp;

    return counter;
}

public static void quickSort(int[] array, int begin, int end) {
    if (end <= begin) return;
    int pivot = partition(array, begin, end);
    quickSort(array, begin, pivot-1);
    quickSort(array, pivot+1, end);
}

Complejidad del tiempo

La complejidad temporal de Quicksort se puede expresar con la siguiente ecuación:

$$
T(n) = T(k) + T(n-k-1) + O(n)
$$

El peor de los casos es cuando el elemento más grande o más pequeño se elige siempre para el pivote. Entonces la ecuación quedaría así:

$$
T(n) = T(0) + T(n-1) + O(n) = T(n-1) + O(n)
$$

Esto resulta ser O(n^2).

Esto puede sonar mal, ya que hemos aprendido varios algoritmos que se ejecutan en tiempo O(nlog n) como su peor caso, pero Quicksort en realidad se usa mucho.

Esto se debe a que tiene un tiempo de ejecución promedio realmente bueno, también limitado por O(nlog n), y es muy eficiente para una gran parte de las entradas posibles.

Una de las razones por las que se prefiere Merge Sort es que no ocupa espacio adicional, toda la clasificación se realiza en el lugar y no hay llamadas costosas de asignación y desasignación.

Comparación de rendimiento {#comparación de rendimiento}

Dicho todo esto, a menudo es útil ejecutar todos estos algoritmos en su máquina varias veces para tener una idea de cómo funcionan.

Por supuesto, funcionarán de manera diferente con las diferentes colecciones que se están clasificando, pero incluso con eso en mente, debería poder notar algunas tendencias.

Ejecutemos todas las implementaciones, una por una, cada una en una copia de una matriz mezclada de 10,000 enteros:


time(ns) Clasificación de burbuja Clasificación de inserción Clasificación de selección Clasificación de fusión Clasificación de pila Clasificación rápida Primera ejecución 266.089.476 21.973.989 66.603.076 5.511.069 5.283.411 4.156.005 Segunda Ejecución 323,692,591 29,138,068 80,963,267 8,075,023 6,420,768 7,060,203 Tercera Ejecución 303.853.052 21.380.896 91.810.620 7.765.258 8.009.711 7.622.817 Cuarta Ejecución 410.171.593 30.995.411 96.545.412 6.560.722 5.837.317 2.358.377 Quinta Ejecución 315.602.328 26.119.110 95.742.699 5.471.260 14.629.836 3.331.834 Sexta Ejecución 286.841.514 26.789.954 90.266.152 9.898.465 4.671.969 4.401.080 Séptima Ejecución 384.841.823 18.979.289 72.569.462 5.135.060 10.348.805 4.982.666 Ocho Carrera 393.849.249 34.476.528 107.951.645 8.436.103 10.142.295 13.678.772 Novena Ejecución 306.140.830 57.831.705 138.244.799 5.154.343 5.654.133 4.663.260 Décima Ejecución 306.686.339 34.594.400 89.442.602 5.601.573 4.675.390 3.148.027


Evidentemente, podemos ver que Bubble Sort es el peor cuando se trata de rendimiento. Evite usarlo en producción si no puede garantizar que manejará solo colecciones pequeñas y no detendrá la aplicación.

HeapSort y QuickSort son los mejores en cuanto a rendimiento. Aunque están generando resultados similares, QuickSort tiende a ser un poco mejor y más consistente, lo que se verifica.

Clasificación en Java

Interfaz comparable

Si tiene sus propios tipos, puede ser engorroso implementar un algoritmo de clasificación separado para cada uno. Es por eso que Java proporciona una interfaz que le permite usar Collections.sort() en sus propias clases.

Para hacer esto, su clase debe implementar la interfaz Comparable<T>, donde T es su tipo, y anular un método llamado .compareTo().

Este método devuelve un entero negativo si this es menor que el elemento del argumento, 0 si son iguales y un entero positivo si this es mayor.

En nuestro ejemplo, hemos creado una clase ‘Estudiante’, y cada estudiante se identifica con un ‘id’ y un año en que comenzó sus estudios.

Queremos ordenarlos principalmente por generaciones, pero también en segundo lugar por ID:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static class Student implements Comparable<Student> {
    int studentId;
    int studentGeneration;

    public Student(int studentId, int studentGeneration) {
        this.studentId = studentId;
        this.studentGeneration = studentGeneration;
    }

    @Override
    public String toString() {
        return studentId + "/" + studentGeneration % 100;
    }

    @Override
    public int compareTo(Student student) {
        int result = this.studentGeneration - student.studentGeneration;
        if (result != 0)
            return result;
        else
            return this.studentId - student.studentId;
    }
}

Y aquí está cómo usarlo en una aplicación:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public static void main(String[] args) {
    Student[] a = new SortingAlgorithms.Student[5];
    a[0] = new Student(75, 2016);
    a[1] = new Student(52, 2019);
    a[2] = new Student(57, 2016);
    a[3] = new Student(220, 2014);
    a[4] = new Student(16, 2018);

    Arrays.sort(a);

    System.out.println(Arrays.toString(a));
}

Producción:

1
[220/14, 57/16, 75/16, 16/18, 52/19]

Interfaz del comparador

Es posible que queramos ordenar nuestros objetos de una manera poco ortodoxa para un propósito específico, pero no queremos implementar eso como el comportamiento predeterminado de nuestra clase, o quizás estemos ordenando una colección de un tipo integrado en un no -modo por defecto.

Para ello, podemos utilizar la interfaz Comparator. Por ejemplo, tomemos nuestra clase ‘Estudiante’ y clasifiquemos solo por ID:

1
2
3
4
5
public static class SortByID implements Comparator<Student> {
    public int compare(Student a, Student b) {
        return a.studentId - b.studentId;
    }
}

Si reemplazamos la llamada de clasificación en main con lo siguiente:

1
Arrays.sort(a, new SortByID());

Producción:

1
[16/18, 52/19, 57/16, 75/16, 220/14]

Cómo funciona todo

Collection.sort() funciona llamando al método subyacente Arrays.sort(), mientras que la ordenación en sí usa Ordenación por inserción para matrices de menos de 47 y Quicksort para el resto.

Se basa en una implementación específica de dos pivotes de Quicksort que evita la mayoría de las causas típicas de degradación en rendimiento cuadrático, según la [documentación JDK10](https://docs.oracle.com/javase/10 /docs/api/java/util/Arrays.html#sort(byte%5B%5D)).

Conclusión

La clasificación es una operación muy común con los conjuntos de datos, ya sea para analizarlos más a fondo, acelerar la búsqueda mediante el uso de algoritmos más eficientes que se basan en la clasificación de los datos, filtrar datos, etc.

La clasificación es compatible con muchos lenguajes y las interfaces a menudo oscurecen lo que realmente le está sucediendo al programador. Si bien esta abstracción es bienvenida y necesaria para un trabajo efectivo, a veces puede ser mortal para la eficiencia, y es bueno saber cómo implementar varios algoritmos y estar familiarizado con sus ventajas y desventajas, así como también cómo acceder fácilmente a los algoritmos integrados. en implementaciones.