Ordenando los algoritmos en Java

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, los comunes son números de ordenación de menor a mayor o viceversa, o ordenación de cadenas por lexicografía . 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 realmente se implementan en Java y otros lenguajes.
Hay varios algoritmos de clasificación, y no todos son igualmente eficientes. Analizaremos la complejidad de su tiempo para compararlos y ver cuáles funcionan mejor.
La lista de algoritmos que aprenderá aquí no es de ninguna manera exhaustiva, pero hemos recopilado algunos de los más comunes y más eficientes para ayudarlo a comenzar:
Nota : este artículo no tratará con la clasificación concurrente, ya que está dirigido a principiantes.

Ordenamiento de burbuja

Explicación

El ordenamiento de burbujas funciona al intercambiar elementos adyacentes si no están en el orden deseado. Este proceso se repite desde el principio de la matriz hasta que todos los elementos están en orden.
Sabemos que todos los elementos están en orden cuando nos las arreglamos para hacer la iteración completa sin cambiarlos en absoluto, entonces todos los elementos que comparamos estaban en el orden deseado con sus elementos adyacentes, y por extensión, toda la matriz.
Aquí están 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, por lo que los intercambiamos.
  • 4 1 5 3: Los segundos dos elementos también están en el orden incorrecto, así que cambiamos.
  • 2 1 4 5 3: Estos dos están en el orden correcto, 4 <5, así que los dejamos en paz.
  • 2 1 4 5 3 : Otro swap.
  • 2 1 4 3 5: Aquí está la matriz resultante después de una iteración.
Debido a que al menos un intercambio ocurrió durante la primera pasada (en realidad fueron tres), necesitamos 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 Burbuja de clasificación es porque los números son "burbujeantes" a la "superficie". Si repasa nuestro ejemplo nuevamente, siguiendo un número en particular (4 es un gran ejemplo), lo verás moverse lentamente hacia la derecha durante el proceso.
Todos los números se mueven a sus lugares respectivos poco a poco, de izquierda a derecha, como burbujas que se elevan lentamente de un cuerpo de agua.

Implementación

Vamos a implementar Bubble Sort de la misma manera que lo hemos expresado en palabras. Nuestra función ingresa en un bucle while en el que pasa por todo el intercambio de arreglos según sea necesario.
Suponemos que la matriz está ordenada, pero si se demuestra que estamos equivocados al ordenar (si ocurre un intercambio), pasamos por otra iteración. El ciclo while sigue avanzando hasta que logramos pasar a través de toda la matriz sin intercambiar:
public static void bubbleSort(int[] array) {  
    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 utilizar este algoritmo, debemos tener cuidado al establecer nuestra condición de intercambio.
Por ejemplo, si lo 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 true, y por lo tanto siempre se intercambian.

Complejidad del tiempo

Para calcular la complejidad del tiempo de Bubble Sort, debemos analizar el peor escenario posible. ¿Cuál es el número máximo de veces que necesitamos pasar por toda la matriz antes de ordenarla? Considere el siguiente ejemplo:
5 4 3 2 1  
En la primera iteración, 5 "burbujeará hasta 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 verificar que todo está en orden, por lo que hay un total de 5 iteraciones.
Expande esto a cualquier conjunto de nelementos, y eso significa que necesitas hacer niteraciones. Mirando el código, eso significaría que nuestro whilebucle puede ejecutarse el máximo de nveces.
Cada una de esas nveces estamos iterando a través de toda la matriz (for-loop en el código), lo que significa que la complejidad del 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 sortedcomprobación booleana, que termina el algoritmo si no hay intercambios dentro del bucle interno, lo que significa que la matriz está ordenada.

Tipo de inserción

Explicación

La idea detrás de la ordenación de inserción es dividir la matriz en los subarreglos ordenados y no ordenados .
La parte ordenada tiene una longitud de 1 al principio y corresponde al primer elemento (el más a la izquierda) de la matriz. Recorremos la matriz y durante cada iteración, expandimos la porción ordenada de la matriz en un elemento.
Al expandir, colocamos el nuevo elemento en su lugar adecuado dentro del subarreglo ordenado. Hacemos esto desplazando todos los elementos hacia la derecha hasta que encontramos el primer elemento que no tenemos que cambiar.
Por ejemplo, si en la siguiente matriz la parte en negrita se ordena en orden ascendente, sucede lo siguiente:
  • 3 5 7 8 4 2 1 9 6: Tomamos 4 y recordamos que eso es lo que necesitamos insertar. Desde 8> 4, cambiamos.
  • 3 5 7 x 8 2 1 9 6: donde el valor de x no es de importancia crucial, ya que se sobrescribirá inmediatamente (ya sea por 4 si es su lugar apropiado o por 7 si cambiamos). Desde 7> 4, cambiamos.
  • 3 5 x 7 8 2 1 9 6
  • 3 x 5 7 8 2 1 9 6
  • 3 4 5 7 8 2 1 9 6
Después de este proceso, la parte clasificada se expandió en un elemento, ahora tenemos cinco en lugar de cuatro elementos. Cada iteración hace esto y al final tendremos toda la matriz ordenada.

Implementación

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 ver el peor de los casos para nuestro algoritmo, y nuevamente será el ejemplo donde toda la matriz está descendiendo.
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á limitado por O (n ^ 2) .

Selección de selección

Explicación

El orden de selección también divide la matriz en un subarreglo ordenado y no clasificado. Sin embargo, esta vez, el subarreglo ordenado se forma insertando el elemento mínimo del subarreglo sin clasificar al final de la matriz ordenada, 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 y el iterado en el resto para ver si hay un elemento más pequeño.
Una vez que encontramos el mínimo actual de la parte no clasificada de la matriz, la intercambiamos con el primer elemento y la consideramos parte de la matriz ordenada:
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é delimitado por O (n ^ 2) .

Fusionar clasificación

Explicación

Merge Sort utiliza la recursión para resolver el problema de la clasificación de manera más eficiente que los algoritmos presentados anteriormente, y en particular utiliza un enfoque de dividir y conquistar .
Usando estos dos conceptos, dividiremos la matriz completa en dos subarrays y luego:
  1. Ordenar la mitad izquierda de la matriz (recursivamente)
  2. Ordenar la mitad derecha de la matriz (recursivamente)
  3. Fusionar las soluciones
Fusionar ilustración de clasificación
Este árbol está destinado a representar cómo funcionan las llamadas recursivas. Las matrices marcadas con la flecha hacia abajo son aquellas para las que llamamos la función, mientras que estamos fusionando las flechas hacia arriba que van hacia arriba. Entonces, siga la flecha hacia abajo hasta la parte inferior del árbol, y luego vuelva a subir y fusionar.
En nuestro ejemplo, tenemos la matriz 3 5 3 2 1, por lo que la dividimos en 3 5 42 1Para clasificarlos, los dividimos en sus componentes. Una vez que hemos llegado al fondo, comenzamos a unirnos y clasificarlos a medida que avanzamos.

Implementación

La función básica funciona más o menos como se describe en la explicación. Solo estamos pasando índices leftrightque son índices del elemento más a la izquierda y más a la derecha del subarreglo que queremos ordenar. Inicialmente, estos deben ser 0array.length-1, dependiendo de la implementación.
La base de nuestra recursión asegura que salgamos cuando hayamos terminado, o cuándo rightcuando nos leftencontremos. Encontramos un punto medio mid, y ordenamos los subarreglos de izquierda a derecha de forma recursiva, fusionando nuestras soluciones en última instancia.
Si recuerdas el gráfico de nuestro árbol, podrías preguntarte por qué no creamos dos nuevos arreglos más pequeños y los 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 fusión, y esto solo serviría para empeorar la eficiencia de su memoria. Sin embargo, la lógica de nuestro árbol de recursión sigue siendo la misma, solo tenemos que seguir los índices que estamos usando:
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, tendremos que calcular la longitud de cada uno y hacer arreglos temporales para copiarlos, de modo que podamos cambiar libremente nuestro arreglo principal.
Después de copiar, pasamos por 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 avanzamos el iterador para ese subarreglo:
 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, tendremos que ser un poco matemáticos.
El teorema maestro se usa para calcular la complejidad del tiempo de los algoritmos recursivos. Para los algoritmos no recursivos, generalmente podríamos escribir la complejidad de tiempo precisa como una especie de ecuación, y luego usamos la notación Big-O para clasificarlos en clases de algoritmos de comportamiento similar.
El problema con los algoritmos recursivos es que la misma ecuación se vería así:
T(norte)=unaT(nortesegundo)+donortek
La ecuación en sí es recursiva! En esta ecuación, anos dice cuántas llamadas recursivas más pequeñas estamos dividiendo en nuestro problema y bnos dice qué tan grande es la entrada de esas llamadas recursivas.
El resto de la ecuación es la complejidad de fusionar todas esas soluciones en una al final. El teorema del maestro resuelve esta ecuación para nosotros:
T(norte)={O(nortelosolsegundouna),una>segundokO(norteklosolnorte),una=segundokO(nortek),una<segundok
Si T(n)es el tiempo de ejecución del algoritmo al ordenar una matriz de la longitud n, la Ordenación de fusión se ejecutará dos veces para las matrices que tengan la mitad de la longitud de la matriz original.
Así que si tenemos a=2b=2El paso de fusión toma la memoria O (n) , entonces k=1Esto significa que la ecuación para Merge Sort se vería de la siguiente manera:
T(norte)=2T(norte2)+donorte
Si aplicamos el Teorema del Maestro, veremos que nuestro caso es el que a=b^ktenemos porque tenemos 2=2^1Eso 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 hemos mostrado consume mucha memoria, hay versiones más complejas de Merge Sort que solo ocupan espacio O (1) .
Además, el algoritmo es extremadamente fácil de paralelizar, ya que las llamadas recursivas de un nodo se pueden ejecutar de forma completamente independiente desde ramas separadas. Si bien no vamos a ver cómo y por qué, ya que está fuera 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 de montón, que es que para cada nodo, todos sus hijos están en una relación dada con él. Además, un montón debe estar casi completo. Un árbol binario de profundidad casi completo dtiene un subárbol de profundidad d-1con la misma raíz que está completo, y en el que cada nodo con un descendiente izquierdo tiene un subárbol izquierdo completo. En otras palabras, al agregar un nodo, siempre vamos a la posición más a la izquierda en el nivel incompleto más bajo.
Si el montón es un montón máximo , entonces todos los niños 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 avanzas por el árbol, obtienes números cada vez más pequeños (min-heap) o números más y más grandes (max-heap). Aquí hay un ejemplo de un max-heap:
Max Heap
Podemos representar este máximo-montón en la memoria como una matriz de la siguiente manera:
8 5 6 3 1 2 4  
Puede visualizarlo como una lectura del nivel del gráfico por nivel, de izquierda a derecha. Lo que hemos logrado con esto es que si tomamos el kthelemento de la matriz, las posiciones de sus hijos son 2\*k+12\*k+2(asumiendo que la indexación comienza en 0). Puedes comprobarlo por ti mismo.
A la inversa, para el kthelemento la posición del padre es siempre (k-1)/2.
Sabiendo esto, usted puede fácilmente "hacer un máximo de heapificación" de cualquier matriz dada. Para cada elemento, compruebe 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 podría ser aún más grande que su otro hijo).
Las hojas no tienen hijos, por lo que son trivialmente un máximo de su propio montón :
  • 6 1 8 3 5 2 4 : Ambos niños son más pequeños que los padres, por lo que todo permanece igual.
  • 1 8 3 5 2 4: Porque 5> 1, los intercambiamos. Recursivamente nos apilamos para 5 ahora.
  • 5 8 3 1 2 4: Los dos niños son más pequeños, por lo que no sucede nada.
  • 5 8 3 1 2 4: Porque 8> 6, los intercambiamos.
  • 8 5 6 3 1 2 4: ¡Tenemos el montón ilustrado arriba!
Una vez que hemos aprendido a heapificar 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 apilar 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 8 : heapified
  • 2 5 4 3 1 6 8 : swapped
  • 5 2 4 2 6 8 : heapified
  • 1 2 4 2 5 6 8 : intercambiado
Y así sucesivamente, estoy seguro de que puedes ver el patrón emergente.

Implementación

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 miramos la heapify()función, todo parece hacerse 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 elemento primario de cada nodo, por lo que alrededor de la posición i/2eso significa que en el peor de los casos, log n salta antes de que llegue a la cima, por lo que la complejidad es O (log n) .
Debido a que heapSort()es claramente O (n) debido a que los bucles for-iteran a través de toda la matriz, esto haría que la complejidad total de Heapsort O (nlog n) .
Heapsort es una ordenación en el lugar, lo que significa que toma O (1) espacio adicional, en lugar de Merge Sort, pero también tiene algunos inconvenientes, como ser difícil de paralelizar.

Ordenación rápida

Explicación

Quicksort es otro algoritmo de Dividir y Conquistar. Selecciona un elemento de una matriz como pivote y ordena todos los demás elementos a su alrededor, por ejemplo, elementos más pequeños a la izquierda y más grandes a la derecha.
Esto garantiza que el pivote está en su lugar adecuado después del proceso. Luego, el algoritmo recursivamente hace lo mismo para las partes izquierda y derecha de la matriz.

Implementación

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 del tiempo de Quicksort se puede expresar con la siguiente ecuación:
T(norte)=T(k)+T(norte-k-1)+O(norte)
El peor de los casos es cuando el elemento más grande o más pequeño siempre se selecciona para pivote. La ecuación se vería así:
T(norte)=T(0)+T(norte-1)+O(norte)=T(norte-1)+O(norte)
Esto resulta ser O (n ^ 2) .
Esto puede sonar mal, ya que hemos aprendido múltiples algoritmos que se ejecutan en tiempo O (nlog n) como su peor caso, pero Quicksort es en realidad muy utilizado.
Esto se debe a que tiene un tiempo de ejecución promedio realmente bueno, también delimitado 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 la Combinación de clasificación es que no ocupa ningún 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

Dicho todo esto, a menudo es útil ejecutar todos estos algoritmos en su máquina varias veces para tener una idea de cómo se desempeñan.
Se comportarán de manera diferente con las distintas colecciones que se están clasificando, por supuesto, 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 aleatoria de 10,000 enteros:
tiempo (ns)Ordenamiento de burbujaTipo de inserciónSelección de selecciónMergeSortHeapSortOrdenación rápida
Primer intento266,089,47621.973.98966,603,0765,511,0695,283,4114,156,005
Segunda carrera323.692.59129,138,06880.963.2678,075,0236,420,7687,060,203
Tercera carrera303,853,05221,380,89691,810,6207,765,2588,009,7117,622,817
Cuarta Carrera410,171,59330,995,41196,545,4126,560,7225,837,3172,358,377
Quinta carrera315,602,32826,119,11095.742.6995,471,26014.629.8363,331,834
Sexta carrera286,841,51426.789.95490.266.1529,898,4654,671,9694,401,080
Séptima carrera384,841,82318,979,28972.569.4625,135,06010,348,8054,982,666
Ocho correr393,849,24934,476,528107,951,6458,436,10310,142,29513,678,772
Novena carrera306,140,83057,831,705138,244,7995,154,3435.654.1334,663,260
Décima carrera306.686.33934.594.40089,442,6025.601.5734,675,3903,148,027
Evidentemente podemos ver que Bubble Sort es lo 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 dando resultados similares, QuickSort tiende a ser un poco mejor y más consistente, lo que se comprueba.

Clasificación en Java

Interfaz comparable

Si tiene sus propios tipos, puede resultar complicado implementar un algoritmo de clasificación separado para cada uno. Es por eso que Java proporciona una interfaz que le permite utilizar Collections.sort()en sus propias clases.
Para hacer esto, su clase debe implementar la Comparable<T>interfaz, donde Tes su tipo, y anular un método llamado .compareTo().
Este método devuelve un entero negativo si thises más pequeño que el elemento de argumento, 0 si son iguales y un entero positivo si thises mayor.
En nuestro ejemplo, hemos hecho una clase Studenty cada estudiante se identifica por un año idy un año en que comenzaron sus estudios.
Queremos clasificarlos principalmente por generaciones, pero también de manera secundaria por ID:
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:
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));
}
Salida:
[220/14, 57/16, 75/16, 16/18, 52/19]

Interfaz de comparador

Podríamos querer 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 podríamos estar ordenando una colección de un tipo integrado en un forma predeterminada
Para ello, podemos utilizar la Comparatorinterfaz. Por ejemplo, tomemos nuestra Studentclase y clasifiquemos solo por ID:
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:
Arrays.sort(a, new SortByID());  
Salida:
[16/18, 52/19, 57/16, 75/16, 220/14]

Cómo funciona todo

Collection.sort()funciona llamando al Arrays.sort()método subyacente , mientras que la clasificación en sí misma utiliza la Clasificación por Inserción para matrices de menos de 47 y Quicksort para el resto.
Se basa en una implementación específica de Quicksort de dos ejes que garantiza que evita la mayoría de las causas típicas de la degradación en el rendimiento cuadrático, de acuerdo con la documentación de JDK10 .

Conclusión

La clasificación es una operación muy común con los conjuntos de datos, ya sea 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 idiomas y las interfaces a menudo ocultan 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 pros y sus contras, así como también cómo acceder fácilmente a las implementaciones integradas.

Acerca de: Programator

Somos Instinto Programador

0 comentarios:

Publicar un comentario

Dejanos tu comentario para seguir mejorando!

Con tecnología de Blogger.