El ordenamiento por selección itera sobre los índices en el arreglo; para cada índice, el ordenamiento por selección llama indexOfMinimum y swap. Si la longitud del arreglo es n, hay n índices en el arreglo.
Como cada ejecución del cuerpo del bucle ejecuta dos líneas de código, podrías pensar que el ordenamiento por selección ejecuta 2, n líneas de código. ¡Pero no es cierto! Recuerda que indexOfMinimum y swap son funciones: cuando cualquiera de las dos se llama, se ejecutan algunas líneas de código.
¿Cuántas líneas de código se ejecutan por una sola llamada a swap? En la implementación usual, son tres líneas, de modo que cada llamada a swap se tarda un tiempo constante.
¿Cuántas líneas de código se ejecutan por una sola llamada a indexOfMinimum? Tenemos que contabilizar los bucles dentro de indexOfMinimum. ¿Cuántas veces se ejecuta este bucle en una llamada a indexOfMinimum? Depende del tamaño del subarreglo sobre el cual se esté iterando. Si el subarreglo es todo el arreglo (como en el primer paso), el cuerpo del bucle se ejecuta n veces. Si el subarreglo es de tamaño 6, entonces el cuerpo del bucle se ejecuta 6 veces.
Por ejemplo, digamos que todo el arreglo es de tamaño 8 y piensa acerca de cómo funciona el ordenamiento por selección.
  1. En la primera llamada de indexOfMinimum, tiene que ver cada valor en el arreglo, así que el cuerpo del bucle en indexOfMinimum se ejecuta 8 veces.
  2. En la segunda llamada de indexOfMinimum, tiene que ver cada valor en el subarreglo entre los índices 1 y 7, así que el cuerpo del bucle en indexOfMinimum se ejecuta 7 veces.
  3. En la tercera llamada, ve el subarreglo entre los índices 2 y 7; el cuerpo del bucle se ejecuta 6 veces.
  4. En la cuarta llamada, el subarreglo entre los índices 3 y 7; el cuerpo del bucle se ejecuta 5 veces.
  5. En la octava y última llamada de indexOfMimimum, el cuerpo del bucle se ejecuta solo 1 vez.
Si sumamos el total del número de veces que se ejecuta el cuerpo del bucle de indexOfMinimum, obtenemos 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36 veces.

Nota al margen: calcular la suma desde 1 hasta n

¿Cómo calculas la suma de 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 rápidamente? Aquí está un truco. Vamos a sumar los números de una manera astuta. Primero, sumamos 8 + 1, el valor más grande y el más pequeño. Obtenemos 9. Luego, sumamos 7 + 2, el segundo más grande y el segundo más pequeño. Interesante, volvemos a obtener 9. ¿Qué hay de 6 + 3? También 9. Por último, 5 + 4. Una vez más, ¡9! Entonces, ¿qué tenemos?
(8+1)+(7+2)+(6+3)+(5+4)=9+9+9+9=49=36 . \begin{aligned} (8 + 1) + (7 + 2) + (6 + 3) + (5 + 4) &= 9 + 9 + 9 + 9 \\ &= 4 \cdot 9 \\ &= 36 \ . \end{aligned}
Había cuatro pares de números, cada uno de los cuales sumó 9. Así que aquí está el truco general para sumar cualquier secuencia de enteros consecutivos:
  1. Suma el número más pequeño y el más grande.
  2. Multiplica por el número de parejas.
¿Qué pasa si el número de enteros en la secuencia es impar, de modo que no puedas emparejarlos todos? ¡No importa! Solo cuenta el número que no tiene pareja a la mitad de la secuencia como media pareja. Por ejemplo, vamos a sumar 1 + 2 + 3 + 4 + 5. Tenemos dos parejas completas (1 + 5 y 2 + 4, cada una que suma 6) y una "media pareja" (3, que es la mitad de 6), lo que da un total de 2.5 parejas. Multiplicamos 2, point, 5, dot, 6, equals, 15 y obtenemos la respuesta correcta.
¿Qué pasa si la secuencia a sumar va de 1 a n? A esta la llamamos una serie aritmética. La suma del número más pequeño y el más grande es n, plus, 1. Como hay n números en total, hay n, slash, 2 parejas (independientemente de si n es par o impar). Por lo tanto, la suma de números de 1 a n es left parenthesis, n, plus, 1, right parenthesis, left parenthesis, n, slash, 2, right parenthesis, que equivale a n, start superscript, 2, end superscript, slash, 2, plus, n, slash, 2. Intenta usar esta fórmula para n, equals, 5 y n, equals, 8.

Análisis asintótico del tiempo de ejecución para el ordenamiento por selección

El tiempo total de ejecución para el ordenamiento por selección tiene tres partes:
  1. El tiempo de ejecución para todas las llamadas a indexOfMinimum.
  2. El tiempo de ejecución para todas las llamadas a swap.
  3. El tiempo de ejecución para el resto del bucle en la función selectionSort.
Las partes 2 y 3 son fáciles. Sabemos que hay n llamadas a swap y que cada llamada tarda un tiempo constante. Al usar nuestra notación asintótica, el tiempo para todas las llamadas a swap es Θ(n) \Theta(n) . El resto del bucle en selectionSort en realidad solo está probando e incrementando la variable del bucle y llamando indexOfMinimum y swap, así que tarda un tiempo constante para cada una de las n iteraciones, para otro tiempo Θ(n) \Theta(n) .
Para la parte 1, el tiempo de ejecución para todas las llamadas a indexOfMinimum, ya hicimos la parte difícil. Cada iteración individual del bucle en indexOfMinimum tarda un tiempo constante. El número de iteraciones de este bucle es n en la primera llamada, luego n, minus, 1, luego n, minus, 2, y así sucesivamente. Vimos que esta suma, 1+2++(n1)+n 1 + 2 + \cdots + (n-1) + n , es una serie aritmética y se evalúa a left parenthesis, n, plus, 1, right parenthesis, left parenthesis, n, slash, 2, right parenthesis, o n, start superscript, 2, end superscript, slash, 2, plus, n, slash, 2. Por lo tanto, el tiempo total para todas la llamadas a indexOfMinimum es alguna constante por n, start superscript, 2, end superscript, slash, 2, plus, n, slash, 2. En términos de la notación Θ grande, no nos importa ese factor constante, ni tampoco el factor de 1/2 o el término de orden inferior. El resultado es que el tiempo de ejecución para todas las llamadas a indexOfMinimum es Θ(n2) \Theta(n^2) .
Al sumar los tiempos de ejecución para las tres partes tenemos Θ(n2) \Theta(n^2) para las llamadas a indexOfMinimum, Θ(n) \Theta(n) para las llamadas a swap y Θ(n) \Theta(n) para el resto del bucle en selectionSort. El término Θ(n2) \Theta(n^2) es el más significativo, así que decimos que el tiempo de ejecución del ordenamiento por selección es Θ(n2) \Theta(n^2) .
También observa que ningún caso es particularmente bueno ni malo para el ordenamiento por selección. El bucle en indexOfMinimum siempre va a hacer n, start superscript, 2, end superscript, plus, n, slash, 2 iteraciones, sin importar la entrada. Por lo tanto, podemos decir que el ordenamiento por selección se ejecuta en un tiempo Θ(n2) \Theta(n^2) para todos los casos.
Vamos a ver cómo el tiempo de ejecución de Θ(n2) \Theta(n^2) afecta el tiempo de ejecución real. Digamos que el ordenamiento por selección tarda aproximadamente n, start superscript, 2, end superscript, slash, 10, start superscript, 6, end superscript segundos en ordenar n valores. Vamos a empezar con un valor bastante pequeño de n, digamos n, equals, 100. Entonces el tiempo de ejecución del ordenamiento por selección es alrededor de 100, start superscript, 2, end superscript, slash, 10, start superscript, 6, end superscript, equals, 1, slash, 100 segundos. Eso parece ser bastante rápido. ¿Pero qué pasa si n, equals, 1000? Entonces el ordenamiento por selección se tarda alrededor de 1000, start superscript, 2, end superscript, slash, 10, start superscript, 6, end superscript, equals, 1 segundo. El arreglo creció en un factor de 10, pero el tiempo de ejecución aumentó 100 veces. ¿Qué pasa si n, equals, 1, comma, 000, comma, 000? Entonces el ordenamiento por selección se tarda 1, comma, 000, comma, 000, start superscript, 2, end superscript, slash, 10, start superscript, 6, end superscript, equals, 1, comma, 000, comma, 000 segundos, que es un poco más de 11.5 días. ¡Aumentar el tamaño del arreglo en un factor de 1000 aumenta el tiempo de ejecución un millón de veces!

Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.