Algoritmos de ordenación en Java

A

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 más comunes son ordenar números de menor a mayor o viceversa, o ordenar cadenas lexicográficamente . Incluso puede definir sus propios criterios, y analizaremos 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. Analizaremos su complejidad de tiempo para compararlos y ver cuáles funcionan mejor.

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

  • Ordenamiento de burbuja
  • Tipo de inserción
  • Orden de selección
  • Combinar ordenar
  • Heapsort
  • Ordenación rápida
  • Ordenar en Java

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

Ordenamiento de burbuja

Explicación

La clasificación de burbujas funciona intercambiando 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 logramos hacer toda la iteración sin intercambiar en absoluto; entonces, todos los elementos que comparamos estaban en el orden deseado con sus elementos adyacentes y, por extensión, toda la matriz.

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 dos segundos 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 al menos se produjo un intercambio durante la primera pasada (en realidad hubo tres), debemos volver a revisar toda la matriz 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 Clasificación de burbujas es porque los números “burbujean” hacia la “superficie”. Si vuelve a analizar nuestro ejemplo, siguiendo un número en particular (4 es un gran ejemplo), verá que se mueve 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 de un cuerpo de agua.

Si desea leer un artículo detallado y dedicado a Bubble Sort, ¡lo tenemos cubierto!

Implementación

Vamos a implementar Bubble Sort de una manera similar a la que lo hemos presentado en palabras. Nuestra función entra en un ciclo while en el que pasa por todo el intercambio de matriz 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 continúa hasta que logramos pasar a través de toda la matriz sin intercambiar:

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 lo hubiera usado a[i] >= a[i+1]podría haber terminado con un bucle infinito, porque para elementos iguales esta relación siempre lo sería truey, por lo tanto, siempre los intercambiaría.

Complejidad del tiempo

Para averiguar la complejidad del tiempo de Bubble Sort, necesitamos mirar 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:

5 4 3 2 1

En la primera iteración, 5 “burbujearán 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 un total de 5 iteraciones.

Expanda esto a cualquier matriz de nelementos, y eso significa que necesita hacer niteraciones. Mirando el código, eso significaría que nuestro whileciclo puede ejecutarse el máximo de nveces.

Cada una de esas nveces estamos iterando a través de toda la matriz (bucle for en el código), lo que significa que la complejidad del 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 sortedverificación booleana, que finaliza el algoritmo si no hay intercambios dentro del ciclo interno, lo que significa que la matriz está ordenada.

Tipo de inserción

Explicación

La idea detrás de Insertion Sort es dividir la matriz en subarreglos ordenados y no ordenados.

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

Al expandirse, colocamos el nuevo elemento en su lugar apropiado dentro del subarreglo ordenado. Hacemos esto moviendo 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 está ordenada en orden 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 es de crucial importancia, 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 ordenada se amplió en un elemento, ahora tenemos cinco en lugar de cuatro elementos. Cada iteración hace esto y al final tendremos toda la matriz ordenada.

Si desea leer un artículo detallado y dedicado para el ordenamiento por inserción, ¡lo tenemos cubierto!

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

Una vez más, 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) .

Orden de selección

Explicación

La clasificación por selección también divide la matriz en una submatriz ordenada y no ordenada. Aunque, esta vez, el subarreglo ordenado se forma insertando el elemento mínimo del subarreglo sin clasificar 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 y repetimos el 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:

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é limitado por O (n ^ 2) .

Combinar ordenar

Explicación

Merge Sort utiliza la recursividad para resolver el problema de la clasificación de forma más eficiente que los algoritmos presentados anteriormente y, en particular, utiliza un enfoque de dividir y conquistar .

Usando ambos conceptos, dividiremos la matriz completa en dos submatrices y luego:

  • Ordene la mitad izquierda de la matriz (recursivamente)
  • Ordene la mitad derecha de la matriz (recursivamente)
  • Fusionar las soluciones

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 a la función, mientras que fusionamos las de flecha hacia arriba volviendo a subir. Así que sigue la flecha hacia abajo hasta la parte inferior del árbol y luego vuelve a subir y fusiona.

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

Si desea leer un artículo detallado y dedicado a Merge Sort, ¡lo tenemos cubierto!

Implementación

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

La base de nuestras asegura que la recursividad de salida cuando hemos terminado, o cuando righty leftcumplir con los demás. Encontramos un punto medio midy ordenamos los subarreglos a la izquierda y a la derecha de él de forma recursiva, fusionando finalmente nuestras soluciones.

Si reString nuestro gráfico de árbol, se preguntará por qué no creamos dos nuevas matrices más pequeñas y las pasamos. 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. De lo contrario, la lógica de nuestro árbol de recursividad permanece igual, sin embargo, 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, necesitaremos 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, 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:

 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 utiliza para calcular la complejidad temporal de los algoritmos recursivos. Para los algoritmos no recursivos, normalmente podríamos escribir la complejidad del tiempo preciso 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 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, anos dice cuántas veces llamamos a la recursividad y ben 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 puede que no lo sean.

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

$$
T (n) = Bigg {
comenzar {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 ordenar una matriz de la longitud n, Merge Sort se ejecutaría dos veces para matrices que tengan la mitad de la longitud de la matriz original.

Así que si tenemos a=2, b=2. El paso de fusión toma O (n) memoria, entonces k=1. Esto significa que la ecuación para Merge Sort sería la siguiente:

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

Si aplicamos El Teorema del Maestro, veremos que nuestro caso es el que a=b^kporque 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 memoria, existen 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 de un node 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 en términos de un montón binario específicamente, 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 node, todos sus hijos están en una relación determinada 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 node con un descendiente izquierdo tiene un subárbol izquierdo completo. En otras palabras, al agregar un node, 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 son más grandes.

En otras palabras, a medida que se mueve hacia abajo en el árbol, llega a 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:

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

8 5 6 3 1 2 4

Puede visualizarlo como una lectura del gráfico nivel por nivel, de izquierda a derecha. Lo que hemos logrado con esto es que si tomamos el kthelemento en la matriz, las posiciones de sus hijos son 2*k+1y 2*k+2(asumiendo que la indexación comienza en 0). Puede comprobarlo usted mismo.

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

Sabiendo esto, puede “max-apilar” fácilmente cualquier matriz dada. Para cada elemento, verifique si alguno de sus hijos es más pequeño que él. Si es así, intercambie uno de ellos con el padre y repita este paso de forma recursiva 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 de ellos mismos:

  • 6 1 8 3 5 2 4 : Ambos hijos son más pequeños que el padre, por lo que todo sigue igual.
  • 6 1 8 3 5 2 4: Como 5> 1, los intercambiamos. Apilamos 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: Debido a que 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 apilar 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 2 8 : acumulado
  • 2 5 4 3 1 6 8 : intercambiado
  • 5 2 4 2 1 6 8 : acumulado
  • 1 2 4 2 5 6 8 : intercambiado

Y así sucesivamente, estoy seguro de que puede ver cómo emerge el patrón.

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 estar hecho en O (1) , pero luego está esa molesta llamada recursiva.

¿Cuántas veces se llamará, 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 node, alrededor de la posición i/2. eso significa que, en el peor de los casos, realizará log n saltos 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 recorren toda la matriz, esto haría que la complejidad total de Heapsort 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 la dificultad de paralelizar.

Ordenación rápida

Explicación

Quicksort es otro algoritmo de Divide and Conquer. 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 correcto después del proceso. Luego, el algoritmo hace lo mismo de forma recursiva 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 temporal de Quicksort se puede expresar con la siguiente ecuación:

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

El peor de los casos es cuando el elemento más grande o más pequeño siempre se elige para pivotar. La ecuación se verí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 ya hemos aprendido varios algoritmos que se ejecutan en tiempo O (nlog n) como su peor caso, pero Quicksort se usa ampliamente.

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 posibles entradas.

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 costosas llamadas 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 funcionan.

Se comportarán de manera diferente con diferentes colecciones que se están ordenando, 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 mezclada de 10,000 enteros:

tiempo (ns) Ordenar por burbuja Ordenar por inserción Ordenar por selección Fusionar Ordenar Montón Ordenar Orden rápido

Primer intento266,089,47621,973,98966,603,0765,511,0695,283,4114,156,005
Segunda ejecución323,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 el peor en cuanto a rendimiento se refiere. Evite usarlo en producción si no puede garantizar que solo manejará 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 comprueba.

Ordenar en Java

Interfaz comparable

Si tiene sus propios tipos, puede resultar complicado implementar un algoritmo de clasificación independiente 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 Comparable<T>interfaz, donde Testá 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 del argumento, 0 si son iguales y un entero positivo si thises mayor.

En nuestro ejemplo, hicimos una clase Student, y cada estudiante se identifica por un año idy un año en que comenzaron sus estudios.

Queremos ordenarlos principalmente por generaciones, pero también en segundo lugar 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 así es como se usa 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 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 podríamos estar ordenando una colección de un tipo incorporado en un no- forma predeterminada.

Para ello, podemos utilizar la Comparatorinterfaz. Por ejemplo, tomemos nuestra Studentclase y ordenemos 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 ordenación en sí usa la ordenación por inserción para matrices más cortas que 47 y la ordenación rápida para el resto.

Se basa en una implementación específica de Quicksort de dos pivotes que garantiza que evita la mayoría de las causas típicas de degradación en rendimiento cuadrático, según la documentación JDK10 .

Conclusión

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

La ordenación es compatible con muchos lenguajes y las interfaces a menudo oscurecen lo que realmente le sucede al programador. Si bien esta abstracción es bienvenida y necesaria para un trabajo eficaz, a veces puede ser mortal para la eficiencia, y es bueno saber cómo implementar varios algoritmos y estar familiarizado con sus pros y contras, así como también cómo acceder fácilmente a las implementaciones integradas.

About the author

Ramiro de la Vega

Bienvenido a Pharos.sh

Soy Ramiro de la Vega, Estadounidense con raíces Españolas. Empecé a programar hace casi 20 años cuando era muy jovencito.

Espero que en mi web encuentres la inspiración y ayuda que necesitas para adentrarte en el fantástico mundo de la programación y conseguir tus objetivos por difíciles que sean.

Add comment

Sobre mi

Últimos Post

Etiquetas

Esta web utiliza cookies propias para su correcto funcionamiento. Al hacer clic en el botón Aceptar, aceptas el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Más información
Privacidad