Revisión y prueba de métodos de clasificación. Parte I

El otro día, en los comentarios de VKontakte, tuve una discusión con otro de los alumnos del proyecto. La esencia de la disputa era "quién ganará": un método sort()de una clase java.util.Arrayso implementaciones autoescritas de algoritmos simples: burbuja , inserción , selección , shell (algoritmo Shell). Para algunos, la respuesta a esta pregunta puede ser obvia, pero desde que surgió la disputa, a pesar de que cada parte tenía "fuentes respetadas" a favor de su punto de vista, se decidió realizar un estudio, estirando la materia gris en el proceso, implementando diversos algoritmos. TL;DR: java.util.Arrays.sort() es incondicionalmente el líder en matrices de 100.000 elementos o más; con un tamaño más pequeño, el método Shell a veces puede competir con él. El resto de los algoritmos considerados están completamente vacíos y sólo pueden ser útiles bajo algunas condiciones exóticas. Ahora veamos cómo se clasifican las matrices en nuestros súper dispositivos de silicio.

Orden de selección. Ordenar por selección

Comencemos con el método más simple y obvio. La esencia de esto nos la demuestra perfectamente Robert Sedgwick en su videoconferencia sobre Coursera (citaré la animación que comprimí mal en un gif): Ver Recorriendo la matriz desde el primer elemento, en cada paso Buscamos el elemento mínimo en el lado derecho, con el que intercambiamos el actual. Como resultado, reservamos la versión final de nuestra matriz en forma ordenada. Aquí está el código que implementa este algoritmo en Java:

public void sort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n; i ++) {
            int minIndex = min(array, i, n - 1);
            swap(array, i, minIndex);
        }
    }

public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
public static int min(int[] array, int begin, int end) {
        int minVal = array[begin];
        int minIndex = begin;
        for (int i = begin + 1; i <= end; i++) {
            if (array[i] < minVal) {
                minVal = array[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

El análisis del algoritmo muestra que es necesario revisar el resto de la matriz en cada pasada, es decir, necesitaremos exactamente N + (N-1) + (N-2) + ... + 1 = N^ 2/2 comparaciones. Por tanto, la complejidad del algoritmo es O (N^2). ¿Qué quiere decir esto? Esto significa que al aumentar 2 veces el número de elementos en la matriz (N), aumentaremos el tiempo de ejecución del algoritmo no en 2, sino en 2^2 = 4 veces. Al aumentar N 10 veces, aumentaremos el tiempo de funcionamiento 100 veces, y así sucesivamente. En mi computadora portátil de 2012 con un procesador Core i3 que ejecuta Ubuntu 14.4, obtuve el siguiente tiempo de actividad:

Tipo de inserción. Tipo de inserción

Aquí la idea es ligeramente diferente. Una vez más, pasemos a la animación del Doctor Sedgwick: Ver Lo que está por delante ni siquiera lo hemos visto todavía, y todo lo que dejamos atrás siempre permanece en orden. El punto es que “devolvemos” cada nuevo elemento de la matriz original al principio hasta que “descanse” sobre un elemento más pequeño. Por lo tanto, nuevamente tenemos N pases (para cada elemento de la matriz original), pero en cada paso, en la mayoría de los casos, no miramos el resto completo, sino solo una parte. Es decir, obtendremos la opción 1 + (N-1) + (N-2) + … + N = N^2/2 solo si tenemos que devolver cada elemento siguiente al principio, es decir, en el caso de la matriz de entrada ordenada "al revés" (desafortunada, desafortunada). En el caso de una matriz ya ordenada (aquí está la suerte), habrá un obsequio completo: en cada pasada solo hay una comparación y se deja el elemento en su lugar, es decir, el algoritmo funcionará en un tiempo proporcional a N. La complejidad del algoritmo estará determinado por el peor caso teórico, es decir, O (N^2). En promedio, el tiempo de operación será proporcional a N^2/4, es decir, dos veces más rápido que el algoritmo anterior. En mi implementación, debido al uso no óptimo de la permutación, el tiempo de ejecución fue mayor que el de la Selección. Planeo corregir y actualizar la publicación pronto. Aquí está el código y el resultado de su funcionamiento en la misma máquina:

public void sort(int[] array) {
        int length = array.length;
        for (int i = 1; i < length; i++) {
            for (int j = i; j >= 1; j--) {
                if (array[j] < array[j - 1])
                    swap(array, j, j - 1);
                else
                    break;
            }
        }
    }

Tipo de concha. Ordenar conchas

Un tipo inteligente, Donald Schell, notó en 1959 que los casos más costosos en el algoritmo de inserciones son cuando el elemento regresa muy lejos al principio de la matriz: en alguna pasada, devolvemos el elemento al principio un par de posiciones. , y en otra pasada casi toda la matriz hasta el principio es largo y largo. ¿Es posible hacer esto a la vez, saltando varios elementos? Y encontró esa manera. Consiste en realizar secuencialmente clasificaciones parciales especiales, generalmente llamadas clasificación d o, según Sedgwick, clasificación h (sospecho que h significa salto). La clasificación 3, por ejemplo, comparará el elemento en cuestión no con el anterior, sino que omitirá dos y comparará con el que está 3 posiciones atrás. Si se cambia, lo comparará nuevamente con el elemento 3 posiciones atrás y así sucesivamente. La conclusión es que la matriz resultante estará "ordenada en 3", es decir, la posición incorrecta de los elementos será inferior a 3 posiciones. Trabajar con este algoritmo de inserción será fácil y agradable. Por cierto, “1-sort” no es más que un simple algoritmo de inserción =) Al aplicar secuencialmente h-sort a la matriz con valores h decrecientes, podemos ordenar una matriz grande más rápido. Así es como se ve: Ver El desafío aquí es cómo elegir la secuencia correcta de ordenaciones parciales. En última instancia, el rendimiento del algoritmo depende de esto. La más común es la secuencia propuesta por Donald Knuth: h = h*3 + 1, es decir, 1, 4, 13, 40,... y así sucesivamente hasta 1/3 del tamaño del array. Esta secuencia proporciona un rendimiento decente y también es fácil de implementar. El análisis del algoritmo requiere toneladas de lenguaje y está más allá de mis capacidades. La amplitud del análisis también está determinada por las numerosas variantes de las secuencias h. Empíricamente, podemos decir que la velocidad del algoritmo es muy buena; compruébelo usted mismo: ¡ un millón de elementos en menos de un segundo! Y aquí está el código Java con la secuencia Knut.

public void sort(int[] array) {
        int h = 1;
        while (h*3 < array.length)
            h = h * 3 + 1;

        while(h >= 1) {
            hSort(array, h);
            h = h/3;
        }
    }

    private void hSort(int[] array, int h) {
        int length = array.length;
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h; j = j - h) {
                if (array[j] < array[j - h])
                    swap(array, j, j - h);
                else
                    break;
            }
        }
    }

Ordenamiento de burbuja. Método de burbuja

¡Este es un clásico! Casi todos los programadores novatos implementan este algoritmo. Es un clásico tan grande que el Dr. Sedgwick ni siquiera tenía una animación, así que tuve que hacer el trabajo yo mismo. Ver Aquí, en cada pasada, recorremos la matriz de principio a fin, intercambiando elementos vecinos que están desordenados. Como resultado, los elementos más grandes “flotan” (de ahí el nombre) hasta el final de la matriz. Comenzamos cada nueva pasada con optimismo esperando que el arreglo ya esté ordenado ( sorted = true). Al final del pasaje, si vemos que nos hemos equivocado, comenzamos un nuevo pasaje. La dificultad aquí es que, nuevamente, estamos atravesando (casi) toda la matriz en cada pasada. La comparación ocurre en cada paso, el intercambio ocurre en casi cada paso, lo que hace que este algoritmo sea uno de los más lentos (si consideramos los implementados racionalmente, y no los "sacudidas" y otros similares). Es interesante que formalmente la complejidad aquí también será igual a O(N^2), pero el coeficiente es mucho mayor que el de las inserciones y selecciones. Código de algoritmo:

public void sort(int[] array) {
        boolean isSorted;
        int nMinusOne = array.length - 1;
        for(int i = 0; i < nMinusOne; i++) {
            isSorted = true;
            for (int j = 0; j < nMinusOne - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    isSorted = false;
                }
            }
            if (isSorted)
                return;
        }
    }

Tiempo de funcionamiento: Siente la diferencia: ¡más de media hora con un millón de elementos! Conclusión: ¡ ¡¡Nunca uses este algoritmo!!!

Resumen de la primera parte

Como resultado, sugiero consultar la tabla general de estos algoritmos. También puede comparar con los resultados del método integrado java.util.Arrays.sort(). Parece una especie de magia: ¿qué podría ser más rápido que Shell? Escribiré sobre esto en la siguiente parte. Allí veremos algoritmos de clasificación rápida ampliamente utilizados, así como la clasificación por fusión, aprenderemos sobre la diferencia en los métodos para clasificar matrices a partir de primitivos y tipos de referencia, y también nos familiarizaremos con una interfaz muy importante en este asunto ;) A Comparablecontinuación puede estudiar un gráfico construido en escala logarítmica utilizando tablas de datos. Cuanto más plana sea la línea, mejor será el algoritmo =) Para aquellos que quieran descargar el proyecto completo y ejecutar pruebas por su cuenta, conserven el enlace: Java ¡Nos vemos en la siguiente parte! =)