Ordenar por selección en Java

En este tutorial, repasaremos la teoría y la implementación de Selection Sort en Java. También exploraremos su complejidad de tiempo y espacio con ejemplos.

Introducción

La clasificación de datos es un problema frecuente en 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 se ordena la matriz. Buscar un elemento es mucho más rápido usando algoritmos como Búsqueda binaria que se basan en la suposición de que la matriz ya está ordenada.

Uno de los algoritmos más simples para ordenar datos es Ordenar por selección. Por lo general, se enseña en clases y tutoriales de programación para principiantes para explicar el concepto de clasificación, por lo que mantendremos este artículo muy amigable para principiantes.

Clasificación de selección

La ordenación por selección es un algoritmo de ordenación por comparación in situ que utiliza la fuerza bruta para ordenar 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 subarreglos:

  • Un subarreglo ordenado
  • Un subarreglo desordenado

El subarreglo ordenado está vacío al principio. En cada iteración, el elemento más pequeño de la matriz no ordenada 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 ordenada Matriz no ordenada Elemento mínimo de la matriz no ordenada [] [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] 16 [2, 5, 6, 7, 16] [20] 20 [2, 5, 6, 7, 16, 20] []


Implementación

El método selectionSort() toma solo un argumento, la matriz que debe ordenarse. Recorreremos la matriz no ordenada, que estará entre los índices i y j, encontraremos su mínimo y lo colocaremos en la matriz ordenada intercambiando:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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:

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

Esto imprimirá:

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

Complejidad de tiempo de clasificación de selección

Complejidad de 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 resultados es de crucial importancia. Imagine una aplicación de guía telefónica 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 al instante.

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 estimación del tiempo necesario para ejecutar un programa, independientemente del software.

La complejidad temporal promedio y en el peor de los casos de Clasificación por selección es O(n^2^). Esto hace que Selection Sort sea mucho más lento que muchos otros algoritmos de clasificación por comparación como Ordenar por fusión o Tipo de inserción que tienen la complejidad temporal en el peor de los casos (O(nlogn)). Curiosamente, O(nlogn) es lo mejor que se puede lograr con cualquier algoritmo de clasificación de comparación.

Análisis de la complejidad del tiempo

Demostrar que Selection Sort tiene una complejidad de tiempo cuadrática se reduce a calcular la cantidad de veces que se iterará el bucle interno. Podemos ver esto si repasamos el código línea por línea e intentamos aproximar el tiempo que lleva ejecutar cada línea de código:

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

Todo en el bloque interno del bucle se ejecutará n veces, donde n es la longitud de una matriz determinada:

1
int min = i;

min se inicializará a i exactamente n veces. Ahora viene la parte complicada:

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

Dado que este ciclo está anidado, se necesita un poco de matemática para calcular la cantidad 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:

1
(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 (n^2^ - n)/2. Simplificando esto, resulta en una complejidad de tiempo O(n^2^).

En pocas palabras, al calcular la complejidad de un algoritmo O(f(n)), necesitamos 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) = x^2^+13x+23

O(f(x)) sería la mayor potencia de x en la ecuación, que en este caso es x^2^.

Así es como funcionó después de ordenar una matriz que contenía 10,000 enteros en orden aleatorio:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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:


Hora(s) Selección Ordenar Primera ejecución 0.024 Segunda ejecución 0.020 Tercera Corrida 0.022 Cuarta Corrida 0.020 Quinta carrera 0.025 Sexta Corrida 0.022 Séptima Carrera 0.021 Ocho Correr 0.031 Novena Corrida 0.022 Décima Carrera 0.029

El tiempo de ejecución promedio fue de 0.0236 segundos, sin embargo, esto también dependerá en gran medida de su máquina.

Complejidad del espacio de clasificación de selección

La complejidad del espacio 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 del espacio de Selection Sort es constante (O(1)) porque está en el lugar, lo cual es excelente. La complejidad del peor de los casos de la ordenación por selección es, desafortunadamente, O(n^2^) también, lo que significa que incluso si el algoritmo obtiene una matriz ya ordenada como entrada, aún llevará 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 clasificación no debería ser tan notable, y la clasificación por selección podría incluso superar a otros algoritmos de divide y vencerás.

Donde brilla Selection Sort, es cuando la cantidad de intercambios debe ser mínima. En el peor de los casos, solo habrá intercambios n-1, que es el número mínimo posible de intercambios que deben realizarse. Esto es bastante intuitivo si considera que cada elemento se colocará en su lugar correcto en la matriz ordenada de inmediato.

Conclusión

Selection Sort es una ordenación de comparación in situ de fuerza bruta que encuentra continuamente el mínimo de un subarreglo no ordenado 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 es la más adecuada para el trabajo en mano.

Licensed under CC BY-NC-SA 4.0