Ejercicios · Estructuras de Datos · Implementaciones y quicksort¶
Ejercicios sobre las implementaciones y quicksort. Cada enlace abre una actividad que se trabaja directo en el navegador, en el mismo orden de los temas de la sesión. Los programas y los arreglos no son los de la sesión: mismo tema, ronda nueva.
Las tres implementaciones enlazadas¶
caminar¶
Sumar los doce elementos de una lista, una cola y una pila sobre nodos usando solo el contrato: cuántos nodos recorre cada una, cuántos reserva y cuál de las tres termina en Θ(n²).
Ejercicios sobre las implementaciones¶
rotar¶
Pasar el frente de la cola al final cambiando punteros: qué lista hace falta debajo, cuál de tres órdenes de asignación pierde la cadena, qué pasa con un solo elemento y cuánto cuesta.
concatenar¶
Colgar una cola detrás de otra en Θ(1) desde dentro de la clase, contra la versión con el contrato que cuesta Θ(m), con el caso de la cola vacía y la razón para dejar vacía la segunda.
Pagar al partir: quicksort¶
particionar¶
particionar sobre siete elementos, vuelta por vuelta, con i, j y la zona
de cada casilla: dónde queda el pivote antes de correrlo, cómo queda el arreglo
y cuántas veces se llama a intercambiar.
zonas¶
Seis estados anotados durante una partición, con el color de la zona de cada
casilla; en cada uno, qué quedó mal: un valor en la zona que no le toca, i
delante de j, el pivote movido antes de tiempo o un valor perdido, si algo.
libre¶
Un arreglo propio, de hasta doce enteros: la partición paso a paso y la tabla
de todas las llamadas de quicksort que lo ordenan, con las comparaciones y la
profundidad de la pila.
Lo que cuesta quicksort¶
comparaciones¶
Predecir las comparaciones de quicksort sobre una entrada ordenada, la misma al revés y una balanceada, y cuántas llamadas llegan a estar abiertas a la vez. Después, las llamadas una por una.
peorcaso¶
Cuatro órdenes de los mismos siete valores: cuál es el peor caso aunque no lo parezca, qué lo hace caro, cuánto ahorra el pivote del medio y qué pivote impide que una entrada fija lo provoque siempre.