Algoritmos de ordenaci贸n 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 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.

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *