Ordenar por selección en Java

O

 

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.

 

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