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
Pseudocódigo del ordenamiento por selección
Hay muchas diferentes maneras de ordenar las cartas. Aquí hay una sencilla, llamada ordenamiento por selección, probablemente parecida a cómo ordenaste las cartas arriba:
- Encuentra la carta más baja. Intercámbiala con la primera carta.
- Encuentra la segunda carta más baja. Intercámbiala con la segunda carta.
- Encuentra la tercera carta más baja. Intercámbiala con la tercera carta.
- Repite encontrar la siguiente carta más baja e intercambiarla en la posición correcta hasta que el arreglo esté ordenado.
Este algoritmo se llama ordenamiento por selección porque selecciona repetidamente el siguiente elemento más bajo y lo intercambia a su lugar.
Tú mismo puedes ver el algoritmo a continuación. Empieza al usar "Paso" para ver cada paso del algoritmo y luego intenta usar "Reproducir" una vez que lo entiendas para ver todos los pasos hasta el final.
Después de verlo por ti mismo, ¿qué opinas sobre este algoritmo? ¿Qué partes parecen tomar más tiempo? ¿Cómo crees que sería su desempeño en arreglos grandes? Mantén esas preguntas en mente a medida que avanzas e implementas este algoritmo.
Encontrar el índice del elemento mínimo en un subarreglo
Uno de los pasos en el ordenamiento por selección es encontrar la siguiente carta más baja para ponerla en su lugar correcto. Por ejemplo, si el arreglo inicialmente tiene los valores [13, 19, 18, 4, 10], primero tenemos que encontrar el índice del valor más pequeño en el arreglo. Como 4 es el valor más pequeño, el índice del valor más pequeño es 3.
El ordenamiento por selección cambiaría el valor en el índice 3 con el valor en el índice 0, dando [4, 19, 18, 13, 10]. Ahora tenemos que encontrar el índice del segundo valor más pequeño para intercambiarlo al índice 1.
Puede ser difícil escribir el código que encuentre el índice del segundo valor más pequeño en un arreglo. Estoy seguro de que podrías hacerlo, pero hay una mejor manera. Observa que como el valor más pequeño ya fue intercambiado al índice 0, lo que realmente queremos es encontrar el valor más pequeño en la parte del arreglo que inicia en el índice 1.A una sección de un arreglo la llamamos un subarreglo, así que en este caso, queremos el índice del valor más pequeño en el subarreglo que comienza en el índice 1. Para nuestro ejemplo, si el arreglo completo es [4, 19, 18, 13, 10], entonces el valor más pequeño en el subarreglo que empieza en el índice 1 es 10, y tiene índice 4 en el arreglo original. Así que el índice 4 es la ubicación del segundo elemento más pequeño del arreglo completo.
Prueba esa estrategia en el siguiente desafío, y entonces tendrás la mayor parte de lo que necesitas para implementar todo el algoritmo de ordenamiento por selección.
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?
alguien sabe,como contestar la siguiente actividad??(8 votos)
var indexOfMinimum = function(array, startIndex) {
// Set initial values for minValue and minIndex,
// based on the leftmost entry in the subarray:
var minValue = array[startIndex];
var minIndex = startIndex;
for (var i = startIndex + 1; i < array.length; i++) {
if (array[i] < minValue) {
minIndex = i;
minValue = array[i];
}
}
// Loop over items starting with startIndex,
// updating minValue and minIndex as needed:
return minIndex;
};
var array = [18, 6, 66, 44, 9, 22, 14];
var index = indexOfMinimum(array, 2);
// For the test array [18, 6, 66, 44, 9, 22, 14],
// the value 9 is the smallest of [..66, 44, 9, 22, 14]
// Since 9 is at index 4 in the original array,
// "index" has value 4
println("The index of the minimum value of the subarray starting at index 2 is " + index + "." );
Program.assertEqual(index, 4);
Program.assertEqual(indexOfMinimum(array, 0), 1);
Program.assertEqual(indexOfMinimum(array, 4), 4);(7 votos)
alguien tiene el desafio implementa el ordenamiento por seleccion?(3 votos)- los numeros y letras q estan solos podemos agustarlos a otras varibles(2 votos)
- porque al algoritmo se le determina con el valor mas bajo(2 votos)
que otra forma hay de Encontrar el índice del elemento mínimo en un subarregloEncontrar el índice del elemento mínimo en un subarreglo(2 votos)
Porque se le denomina Indice 1.A y habrá mas de este tipo mas adelante??(2 votos)
Fue un error de puntuación, en realidad dice ...en el índice 1 a una sección..(2 votos)
- Este funciona pero no lo toma como bueno el ejercicio, ¿Por que sera?
var indexOfMinimum = function(array, startIndex) {
// Set initial values for minValue and minIndex,
// based on the leftmost entry in the subarray:
var minIndex=0;
for(var count = startIndex; startIndex< array.length; count++){
if (array[minIndex]<array[startIndex]) {
startIndex++;
}
else {
var minIndex = startIndex;
startIndex++;
}
}
// Loop over items starting with startIndex,
// updating minValue and minIndex as needed:
return minIndex;
};
var array = [18, 6, 66, 44, 9, 22, 14];
var index = indexOfMinimum(array,2);
// For the test array [18, 6, 66, 44, 9, 22, 14],
// the value 9 is the smallest of [..66, 44, 9, 22, 14]
// Since 9 is at index 4 in the original array,
// "index" has value 4
println("The index of the minimum value of the subarray starting at index 2 is " + index + "." );
Program.assertEqual(index, 4);
Program.assertEqual(indexOfMinimum(array, 0), 1);
Program.assertEqual(indexOfMinimum(array, 4), 4);(2 votos) 
Si se tiene el array = [ 1 , 1 , 0 , 2 ] y aplicándole el algoritmo como dice en el segundo párrafo, haciendo la analogía con las cartas, ya en la primera iteración el array quedaría ordenado porque queda: array = [ 0 , 1 , 1 , 2 ] . Pregunto es necesario seguir aplicando el algoritmo hasta que recorra todos los indices en el subarreglo tal como dice el párrafo 6 o se detiene en la primera iteración.(1 voto)- Todo depende de el codigo. Ahora si aplicamos el algoritmo tal cual como se nos muestra este finalizara cuando recorra todo el arreglo ( ya que no sabe que esta ordenado, pero claramente se puede modificar el algoritmo para hacerlo más "eficiente" ).
saludos!(1 voto)
- como sabemos que hicimos una buena selección o un subarreglo correctamente(1 voto)
- por que hay nos muestra la forma de organizacion(1 voto)
