Contenido principal
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
© 2024 Khan AcademyTérminos de usoPolítica de privacidadAviso de cookies
Análisis del ordenamiento de selección
Google ClassroomEl 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 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
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 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
¿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
¿Qué pasa si la secuencia a sumar va de 1 a
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
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 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 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 indexOfMinimum es alguna constante por indexOfMinimum es Al sumar los tiempos de ejecución para las tres partes tenemos
indexOfMinimum, swap y selectionSort. El término 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 Vamos a ver cómo el tiempo de ejecución de
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(4 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)
- 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]);(3 votos) - 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)
¿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)