Test sobre Ordenamiento rápido (quicksort)
Ordenamiento Rápido (Quicksort): Guía Completa para Estudiantes
Test: Algoritmo Quicksort
20 preguntas
Pregunta 1: Elegir el elemento central como pivote en Quicksort elimina completamente la posibilidad de que el pivote sea muy pequeño o muy grande.
A. Sí
B. No
Explicación: Según los materiales de estudio, la estrategia de elegir el elemento central como pivote reduce la probabilidad de seleccionar un pivote muy pequeño o muy grande, pero no elimina esta posibilidad por completo.
Pregunta 2: Un Quicksort ingenuo en su peor caso puede agotar la pila de llamadas, especialmente con listas muy grandes, en lenguajes con límites de recursión.
A. Sí
B. No
Explicación: Los materiales de estudio establecen que "En lenguajes con límites de recursión, un Quicksort ingenuo en el peor caso puede agotar la pila de llamadas, especialmente con listas muy grandes".
Pregunta 3: En el pseudo-código de la función de partición proporcionado, el pivote se selecciona inicialmente como el último elemento de la sublista y finalmente se coloca en la posición `i + 1` después de la reorganización de los elementos.
A. Sí
B. No
Explicación: El pseudo-código de la función `particion` muestra explícitamente: `pivote = arr[alto]` lo que indica que el último elemento (`arr[alto]`) es inicialmente elegido como pivote. Luego, después de recorrer la sublista, el código finaliza con `intercambiar(arr, i + 1, alto)` y `retornar i + 1`, confirmando que el pivote (`arr[alto]`) es intercambiado y colocado en la posición `i + 1`.
Pregunta 4: La complejidad espacial del algoritmo Quicksort es O(1) en el peor caso, lo que significa que no utiliza memoria adicional significativa independientemente del tamaño de la entrada.
A. Sí
B. No
Explicación: La complejidad espacial de Quicksort en el peor caso es O(n), no O(1). Esto ocurre cuando la recursión es muy profunda, requiriendo un espacio de pila proporcional al número de elementos (n) en el array.
Pregunta 5: Durante el proceso de partición de Lomuto, si se está evaluando un elemento `arr[j]` y este es mayor que el pivote, se procede a intercambiar `arr[i]` y `arr[j]` sin modificar el índice `i`.
A. Sí
B. No
Explicación: Según el esquema de partición de Lomuto, si `arr[j]` es mayor que el pivote, no se realiza ningún intercambio entre `arr[i]` y `arr[j]`. En ese caso, solo se continúa con la siguiente iteración del bucle, y el índice `i` tampoco se incrementa. El intercambio y el incremento de `i` solo ocurren cuando `arr[j]` es menor o igual que el pivote.