Ordenar por selecci贸n en Java

     

    Introducci贸n

    La clasificaci贸n de datos es un problema frecuente en la inform谩tica. Dada una colecci贸n de elementos, el objetivo es reorganizarlos en alg煤n orden. Los ejemplos comunes son ordenar una matriz alfab茅ticamente o de menor a mayor.

    Los datos ordenados son mucho m谩s f谩ciles de manipular. Encontrar el elemento m谩s grande o m谩s peque帽o de una matriz se puede hacer en tiempo constante si la matriz est谩 ordenada. La b煤squeda de un elemento es mucho m谩s r谩pida si se utilizan algoritmos como Binary Search, que se basan en el supuesto de que la matriz ya est谩 ordenada.

    Uno de los algoritmos m谩s simples para ordenar datos es Orden de selecci贸n. Por lo general, se ense帽a en clases de programaci贸n para principiantes y tutoriales para explicar el concepto de clasificaci贸n, por lo que mantendremos este art铆culo para principiantes.

    Orden de selecci贸n

    La clasificaci贸n por selecci贸n es un algoritmo de clasificaci贸n por comparaci贸n in situ que utiliza la fuerza bruta para clasificar una matriz.

    In situ significa que el algoritmo utiliza una peque帽a cantidad constante de espacio para almacenamiento adicional.

    Se llama algoritmo de “fuerza bruta” porque utiliza la forma m谩s simple e ineficaz de calcular la soluci贸n. Sin embargo, lo compensa con su sencilla implementaci贸n.

    El algoritmo divide la matriz en dos submatrices:

    • Un subarreglo ordenado
    • Un subarreglo sin clasificar

    El subarreglo ordenado est谩 vac铆o al principio. En cada iteraci贸n, el elemento m谩s peque帽o de la matriz sin clasificar se agregar谩 al final de la matriz ordenada mediante intercambio. De esta forma, la matriz ordenada eventualmente contendr谩 todos los elementos de la matriz original.

    Una matriz de ejemplo que queremos ordenar en orden ascendente:

    Matriz ordenadaMatriz sin clasificarElemento m铆nimo de la matriz sin clasificar
    [][16, 5, 30, 6, 2, 7]2
    [2][16, 5, 20, 6, 7]5
    [2, 5][16, 20, 6, 7]6
    [2, 5, 6][16, 7, 20]7
    [2, 5, 6, 7][16, 20]diecis茅is
    [2, 5, 6, 7, 16][20]20
    [2, 5, 6, 7, 16, 20][]

    Implementaci贸n

    los selectionSort() El m茅todo toma solo un argumento, la matriz que necesita ser ordenada. Iteremos a trav茅s de la matriz sin clasificar, que estar谩 entre 铆ndices i y j, encuentre su m铆nimo y col贸quelo en la matriz ordenada intercambiando:

    public static void selectionSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            // min is the index of the smallest element with an index greater or equal to i
            int min = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[min]) {
                    min = j;
                }
            }
            // Swapping i-th and min-th elements
            int swap = nums[i];
            nums[i] = nums[min];
            nums[min] = swap;
        }
    }
    

    Probemos el c贸digo:

    int[] array = new int[]{16, 5, 30, 6, 7, 2};
    selectionSort(array);
    System.out.println(Arrays.toString(array));
    

    Esto imprimir谩:

    [2, 5, 6, 7, 16, 30]
    

    Complejidad de tiempo de clasificaci贸n de selecci贸n

    Complejidad del tiempo es una forma de describir cu谩nto tiempo necesita un algoritmo para terminar de ejecutarse en relaci贸n con el tama帽o de la entrada. Analizar el tiempo que tarda un algoritmo en dar salida es de vital importancia. Imagine una aplicaci贸n de directorio telef贸nico que tardar铆a un d铆a en ordenar todos los n煤meros despu茅s de agregar un nuevo n煤mero. Eso ser铆a mucho menos 煤til que la misma aplicaci贸n que lo har铆a casi instant谩neamente.

    El rendimiento depende tanto del hardware como del software, pero el mismo programa se puede ejecutar en muchos tipos diferentes de hardware. La notaci贸n Big-O facilita la aproximaci贸n del tiempo necesario para que un programa se ejecute, independientemente del software.

    La complejidad de tiempo promedio y en el peor de los casos de la clasificaci贸n por selecci贸n es O (n2). Esto hace que la clasificaci贸n por selecci贸n sea mucho m谩s lenta que muchos otros algoritmos de clasificaci贸n por comparaci贸n, como la clasificaci贸n por combinaci贸n o la clasificaci贸n por inserci贸n, que tienen la complejidad de tiempo en el peor de los casos (O (nlogn)). Curiosamente, O (nlogn) es lo mejor que se puede lograr con cualquier algoritmo de clasificaci贸n por comparaci贸n.

    An谩lisis de complejidad del tiempo

    Mostrar que la clasificaci贸n por selecci贸n tiene una complejidad de tiempo cuadr谩tica se reduce a calcular el n煤mero de veces que se repetir谩 el ciclo interno. Podemos ver esto si revisamos el c贸digo l铆nea por l铆nea e intentamos aproximar el tiempo que lleva ejecutar cada l铆nea de c贸digo:

    for (int i = 0; i < nums.length; i++) {
    

    Todo en el bloque interno del bucle se ejecutar谩 n tiempos, donde n es la longitud de una matriz dada:

    int min = i;
    

    min se inicializar谩 en i exactamente n veces. Ahora viene la parte complicada:

    for (int j = i + 1; j < nums.length; j++)
    

    Dado que este bucle est谩 anidado, se necesita un poco de matem谩ticas para calcular el n煤mero de veces que se ejecutar谩 el bloque de c贸digo que contiene. Vamos a resolverlo.

    Cuando i es igual a 0, j pasar谩 de 1 a n, lo que significa que cada instrucci贸n en el bloque interno se ejecutar谩 n veces. Cuando i aumenta a 1, j permanecer谩 entre 2 y n, lo que implica que el bloque interno se ejecutar谩 n-2 veces. Resumiendo esto:

    (n - 1) + (n - 2) + ... + 1
    

    La suma de una secuencia de n煤meros naturales se calcula usando algo llamado truco de Gauss y da como resultado (n2 – n) / 2. Simplificando esto, resulta en una complejidad de tiempo O (n2).

    En pocas palabras, al calcular la complejidad de un algoritmo O (f (n)), debemos buscar la potencia m谩s alta de n en la funci贸n f (n) y aislarla. Esto se debe a que cualquier parte de la ecuaci贸n que tenga una potencia menor no afectar谩 el resultado de manera significativa.

    Por ejemplo, tenemos la funci贸n f (x) = x2 + 13x + 23

    O (f (x)) ser铆a la potencia m谩s alta de x en la ecuaci贸n, que en este caso es x2.

    As铆 es como se realiz贸 despu茅s de ordenar una matriz que contiene 10,000 enteros en orden aleatorio:

    public static void main(String[] args) {
        int[] array = new int[10000];
        for (int i = 0; i < array.length; i++) {
              array[i] = i;
        }
    
        // Shuffle array
        Collections.shuffle(Arrays.asList(array));
    
        // Print shuffled collection
        System.out.println(Arrays.toString(array));
      
        long startTime = System.nanoTime();
        selectionSort(array);
        long endTime = System.nanoTime();
    		
        // Print sorted collection
        System.out.println(Arrays.toString(array));
    
        // Print runtime in seconds
        System.out.println("Selection Sort runtime: " + (endTime - startTime)/1000000000);
    }
    

    Ejecut谩ndolo 10 veces, este c贸digo produjo los siguientes resultados:

    Veces)Orden de selecci贸n
    Primer intento0,024
    Segunda ejecuci贸n0,020
    Tercera carrera0.022
    Cuarta carrera0,020
    Quinta carrera0,025
    Sexta carrera0.022
    S茅ptima carrera0.021
    Ocho correr0,031
    Novena carrera0.022
    D茅cima carrera0,029

    El tiempo de ejecuci贸n promedio fue de 0.0236 segundos, sin embargo, esto tambi茅n depender谩 principalmente de su m谩quina.

    Selecci贸n Ordenar la complejidad del espacio

    Complejidad espacial tambi茅n es un factor importante en el dise帽o de algoritmos. Nuestros programas est谩n limitados, no solo por el tiempo que necesitan para ejecutarse, sino tambi茅n por el uso de la memoria. Hay una cantidad limitada de memoria en cualquier computadora, por lo que un programador tambi茅n debe vigilar eso.

    La complejidad espacial de la clasificaci贸n por selecci贸n es constante (O (1)) porque est谩 en el lugar, lo cual es genial. En el peor de los casos, la complejidad del Orden de selecci贸n es, desafortunadamente, O (n2) tambi茅n, lo que significa que incluso si el algoritmo obtiene una matriz ya ordenada como entrada, todav铆a tomar谩 mucho tiempo devolver la matriz sin cambios.

    Este algoritmo tiene un rendimiento decente si la colecci贸n no tiene muchos elementos. Si la matriz tiene ~ 10 elementos, la diferencia de rendimiento entre los diferentes algoritmos de ordenaci贸n no deber铆a ser tan notable, y el ordenamiento por selecci贸n podr铆a incluso superar a otros algoritmos de divisi贸n y conquista.

    Donde brilla la ordenaci贸n por selecci贸n, es cuando la cantidad de intercambios debe ser m铆nima. En el peor de los casos, solo habr谩 n-1 swaps, que es el n煤mero m铆nimo posible de swaps que se deben realizar. Esto es bastante intuitivo si considera que cada elemento se colocar谩 en su lugar correcto en la matriz ordenada de inmediato.

    Conclusi贸n

    El ordenamiento de selecci贸n es un ordenamiento de comparaci贸n in situ de fuerza bruta que encuentra continuamente el m铆nimo de un subarreglo sin clasificar y lo coloca en la posici贸n correcta en el subarreglo ordenado. Debido a su simplicidad, a menudo es uno de los primeros algoritmos que se ense帽an en cursos de inform谩tica en todo el mundo.

    Incluso si se incorporan algoritmos m谩s eficientes, sigue siendo importante comprender la l贸gica subyacente y el an谩lisis de complejidad para evitar problemas comunes y asegurarse de que la herramienta que se utiliza sea la m谩s adecuada para el trabajo en cuesti贸n.

     

    Etiquetas:

    Deja una respuesta

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