Contenido principal
Ciencias de la computación
Curso: Ciencias de la computación > Unidad 1
Lección 4: Ordenamiento por selección- Ordenamiento
- Desafío: implementa el intercambio
- Pseudocódigo del ordenamiento por selección
- Desafío: encuentra el valor mínimo en un subarreglo
- Desafío: implementa el ordenamiento por selección
- Análisis del ordenamiento de selección
- Proyecto: visualizador del ordenamiento por selección
© 2023 Khan AcademyTérminos de usoPolítica de privacidadAviso de cookies
Análisis del ordenamiento de selección
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.
- En la primera llamada de
indexOfMinimum, tiene que ver cada valor en el arreglo, así que el cuerpo del bucle enindexOfMinimumse ejecuta 8 veces. - 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 enindexOfMinimumse ejecuta 7 veces. - En la tercera llamada, ve el subarreglo entre los índices 2 y 7; el cuerpo del bucle se ejecuta 6 veces.
- En la cuarta llamada, ve el subarreglo entre los índices 3 y 7; el cuerpo del bucle se ejecuta 5 veces.
- …
- En la octava y última llamada de
indexOfMinimum, 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?
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:
- Suma el número más pequeño y el más grande.
- 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, squared, 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:
- El tiempo de ejecución para todas las llamadas a
indexOfMinimum. - El tiempo de ejecución para todas las llamadas a
swap. - 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 \Theta, left parenthesis, n, right parenthesis. 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 \Theta, left parenthesis, n, right parenthesis.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, plus, 2, plus, \@cdots, plus, left parenthesis, n, minus, 1, right parenthesis, plus, 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, squared, slash, 2, plus, n, slash, 2. Por lo tanto, el tiempo total para todas la llamadas a indexOfMinimum es alguna constante por n, squared, 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 \Theta, left parenthesis, n, squared, right parenthesis.Al sumar los tiempos de ejecución para las tres partes tenemos \Theta, left parenthesis, n, squared, right parenthesis para las llamadas a
indexOfMinimum, \Theta, left parenthesis, n, right parenthesis para las llamadas a swap y \Theta, left parenthesis, n, right parenthesis para el resto del bucle en selectionSort. El término \Theta, left parenthesis, n, squared, right parenthesis es el más significativo, así que decimos que el tiempo de ejecución del ordenamiento por selección es \Theta, left parenthesis, n, squared, right parenthesis.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, squared, slash, 2, 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 \Theta, left parenthesis, n, squared, right parenthesis para todos los casos.Vamos a ver cómo el tiempo de ejecución de \Theta, left parenthesis, n, squared, right parenthesis afecta el tiempo de ejecución real. Digamos que el ordenamiento por selección tarda aproximadamente n, squared, 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, squared, 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, squared, 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, squared, 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.
¿Quieres unirte a la conversación?
otra formula muy interesante seria n ( n + 1 ) / 2.
donde n seria el primer numero de la secuencia.
Ejemplo: 8+7+6+5+4+3+2+1
n ( n + 1 ) / 2. formula
8 ( 8 + 1 ) / 2 sustituimos la formula
8 ( 9 ) / 2
72 / 2
36(7 votos)
o (n^2+n)/2, se puede reordenar de varias formas.(1 voto)
esta muy bien explicado, pero no termino de entender lo del bucle del: indexOfMinimum(3 votos)
Se refiere al bucle que realiza esa función para obtener el índice del valor mínimo del nuevo subarreglo, y que itera tantas veces como elementos tiene el subarreglo. ¿Está más claro?(1 voto)
- Así hice el visualizador por si alguien ocupa. saludos!
//solo para números de 2 dígitos
// 1. Algoritmos para indexar. Indexing algorithm
var indexOfMinimum = function(array, startIndex) {
var minValue = array[startIndex];
var minIndex = startIndex;
for(var i = minIndex + 1; i < array.length; i++) {
if(array[i] < minValue) {
minIndex = i;
minValue = array[i];
}
}
return minIndex;
};
// 2. Algoritmos de cambio de posición. Swapping algorithm
var swap = function(array, firstIndex, secondIndex) {
var temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
};
// 3. Algoritmos de cambio de ordenamiento. Sorting algorithm
var selectionSort = function(array) {
for(var i=0; i<array.length; i++){
var secondIndex = (indexOfMinimum(array,i));
//println("primer valor: "+ i+ " Segundo valor: "+ secondIndex);
swap(array,i,secondIndex);
}
};
// 4. Funcion imprimir arreglo. Array print function
var displayArray = function(array) {
textFont(createFont("monospace"), 12);
fill(235, 68, 68);
text(array,20,30);
};
// 5. Funcion ordenamiento por selección. Array print function
var selectionSort = function(array) {
for(var i=0; i<array.length; i++){
var secondIndex = (indexOfMinimum(array,i));
// Imprimir arreglo. Array print function
textFont(createFont("monospace"), 12);
fill(179, 13, 40);
var x=10;
var y=30;
text(array, x, y + 30*i);
// Selecciona menor valor en el sub arreglo en color amarillo. Yellow circle in lowest subarray´s value
fill(255, 231, 46, 98);
ellipse((x + 6)+(secondIndex*20),(y-5)+(i*30 ),18,18);
// Pinta linea de seguimiento del menor valor
// Cambiar posicines
swap(array,i,secondIndex);
// Pinta posición que debe tener el numero anterior y no dibuje mas circulos que los necesarios
if (i<array.length-1){
fill(46, 255, 46,150);
ellipse((x + 6)+(i*20),(y+25)+(i*30),18,18);
// Pinta linea de seguimiento del menor valor
line((x + 6)+(secondIndex*20),(y-5)+(i*30 ),(x + 6)+(i*20),(y+25)+(i*30));
}
else {
fill(255, 255, 255,150);
noStroke();
}
}
};
var array = [10, 16, 20, 14, 30, 12, 10];
selectionSort(array);(3 votos) - Creo que esta mal analizado ya que para la primera iteracion de indexOfMinimum no evaluo el numero contra si mismo si no una posicion +1, por lo tanto si son 8 numeros realizo 7 evaluaciones no 8 el total de iteraciones de indexOfMinimun seria 7+6+5+4+3+2+1(2 votos)
- Alguien sabe qué le tengo que añadir al código? funciona bien pero tengo que poner más Program.assertEqual(); para comprobarlo, y ya he puesto bastantes
var swap = function(array, firstIndex, secondIndex) {
var temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
};
var indexOfMinimum = function(array, startIndex) {
var minValue = array[startIndex];
var minIndex = startIndex;
for(var i = minIndex + 1; i < array.length; i++) {
if(array[i] < minValue) {
minIndex = i;
minValue = array[i];
}
}
return minIndex;
};
var selectionSort = function(array) {
var minIndex;
for(var x = 0; x<array.length; x++){
minIndex = indexOfMinimum(array,x);
swap(array,x,minIndex);
}
};
var array = [22, 11, 0, 99, 88, 9, 7, 42,80,90,900,523,453,-52,-1,+1.5];
var arreglo = [0,1,2,3,4,5,6,7,8,9];
var ordenar = [9,8,7,6,5,4,3,2,1,0,-1,-2];
var arr = [0,0,0,0,0,1,3,2,900,-80];
var neg = [-0,-1,-2,-3,-4,-2,-9];
selectionSort(array);
println("Array after sorting: " + array);
Program.assertEqual(array, [-52,-1, 0, 1.5,7, 9, 11, 22, 42, 80, 88, 90, 99,453,523,900]);
selectionSort(arreglo);
Program.assertEqual(arreglo, [0,1,2,3,4,5,6,7,8,9]);
selectionSort(ordenar);
Program.assertEqual(ordenar, [-2,-1,0,1,2,3,4,5,6,7,8,9]);
selectionSort(arr);
Program.assertEqual(arr, [-80,0,0,0,0,0,1,2,3,900]);
selectionSort(neg);
Program.assertEqual(neg, [-9,-4,-3,-2,-2,-1,-0]);(2 votos) 
¿cual es la finalidad del análisis asintotico?(1 voto)
como se llama el indice del ordenamiento?(1 voto)
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^2 + n/2 n
2
+n/2n, 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(0 votos)
¿que es el análisis asintonico ?(1 voto)- Puedes revisar la anterior lección para aprender sobre eso.(1 voto)
- Bastante clara la explicacion del tiempo de ejecución del algoritmo, y hacer las sumatorias del tiempo de ejecución de swap y selectionSort no tiene ningún sentido para valores grandes de "n", pero hasta que punto puede determinar obviar el tiempo de ejecucion para algoritmos que son constantes?. Gracias(1 voto)