Hola,
No sé bien cómo funciona el algoritmo de ordenación por selección, ¿podéis ayudarme? por ejemplo... ¿Cómo se resolvería la siguiente pregunta?
Sea el array [10,3,15,2,1,18] ¿cuántas iteraciones deberá ejecutarse del algoritmo de ordenación por selección para que quede totalmente ordenado en sentido ascendente?
A. 2
B. 4
C. 6
D. 8
La respuesta es la B... ¿pero cómo se hace?
¡Muchas gracias!
Test 12 pregunta 99 [Solucionada]
-
cantimploro
- PreparaTIC XXI
- Mensajes: 1010
- Registrado: 20 Jul 2010, 09:09
- Agradecido: 0
- Agradecimiento recibido: 0
Re: Test 12 pregunta 99
Hombre, esto haces una búsqueda en google y tienes varias páginas explicando cómo funciona, en la primera ya te lo dice...
Lo que haces en cada iteración es intercambiar el primer valor no ordenado por el menor de los no ordenados.
Primera iteración: 1,3,15,2,10,18
Segunda: 1,2,15,3,10,18
Tercera: 1,2,3,15,10,18
Cuarta: 1,2,3,10,15,18
Es decir en la cuarta ya está ordenado que es lo que dice la respuesta b. Técnicamente esto no es correcto, porque el algoritmo necesita de más iteraciones. Me explico. Usando la terminología [lista de ya ordenados][lista de no ordenados] para describir la lista, y (x,y) para describir el par de números a intercambiar:
[][10,3,15,2,1,18] -> (10,1) -> [1][3,15,2,10,18]
[1][3,15,2,10,18] -> (3, 2) -> [1,2][15,3,10,18]
[1,2][15,3,10,18] -> (15,3) -> [1,2,3][15,10,18]
[1,2,3][15,10,18] -> (15,10) -> [1,2,3,10][15,18]
Vale, aquí ya está ordenado, pero el algoritmo aún no lo "sabe". Para el algoritmo sólo los primeros cuatro elementos [1,2,3,10] están ordenados, y el resto, aún están por verificar. Por ejemplo, si el 18 viniera antes que el 15 sería necesaria una operación de intercambio más. Por lo tanto hace falta al menos una iteración más, en la que (en este caso) no se producirá intercambio:
[1,2,3,10][15,18] -> [1,2,3,10,15][18]
Ahora así, como solo queda un elemento, está ordenado por definición, por lo que [1,2,3,10,15][18] ~ [1,2,3,10,15,18][]
Es decir, el bucle exterior del algoritmo itera n-1 veces, aunque no todas ellas tienen por qué desembocar en un intercambio. La pregunta correcta debería haber sido: ¿cuántas operaciones de intercambio se producen para ordenar este array por el método de ordenación por selección?
Aceptemos pulpo como animal de compañía (sobre todo si se llama Paul)... pero si una de las respuestas fuera 5 y alguien pusiera eso y se la dieran por mala, creo que tendría derecho a impugnarlo.
Lo que haces en cada iteración es intercambiar el primer valor no ordenado por el menor de los no ordenados.
Primera iteración: 1,3,15,2,10,18
Segunda: 1,2,15,3,10,18
Tercera: 1,2,3,15,10,18
Cuarta: 1,2,3,10,15,18
Es decir en la cuarta ya está ordenado que es lo que dice la respuesta b. Técnicamente esto no es correcto, porque el algoritmo necesita de más iteraciones. Me explico. Usando la terminología [lista de ya ordenados][lista de no ordenados] para describir la lista, y (x,y) para describir el par de números a intercambiar:
[][10,3,15,2,1,18] -> (10,1) -> [1][3,15,2,10,18]
[1][3,15,2,10,18] -> (3, 2) -> [1,2][15,3,10,18]
[1,2][15,3,10,18] -> (15,3) -> [1,2,3][15,10,18]
[1,2,3][15,10,18] -> (15,10) -> [1,2,3,10][15,18]
Vale, aquí ya está ordenado, pero el algoritmo aún no lo "sabe". Para el algoritmo sólo los primeros cuatro elementos [1,2,3,10] están ordenados, y el resto, aún están por verificar. Por ejemplo, si el 18 viniera antes que el 15 sería necesaria una operación de intercambio más. Por lo tanto hace falta al menos una iteración más, en la que (en este caso) no se producirá intercambio:
[1,2,3,10][15,18] -> [1,2,3,10,15][18]
Ahora así, como solo queda un elemento, está ordenado por definición, por lo que [1,2,3,10,15][18] ~ [1,2,3,10,15,18][]
Es decir, el bucle exterior del algoritmo itera n-1 veces, aunque no todas ellas tienen por qué desembocar en un intercambio. La pregunta correcta debería haber sido: ¿cuántas operaciones de intercambio se producen para ordenar este array por el método de ordenación por selección?
Aceptemos pulpo como animal de compañía (sobre todo si se llama Paul)... pero si una de las respuestas fuera 5 y alguien pusiera eso y se la dieran por mala, creo que tendría derecho a impugnarlo.