Saltar a contenido

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.