Durante esta actividad, los alumnos serán capaces de:
Esta actividad promueve las siguientes habilidades, valores y actitudes: análisis y síntesis, capacidad de resolver problemas, creatividad, y uso eficiente de la informática y las telecomunicaciones.
Esta actividad puede ser elaborada de manera individual o en parejas.
Usando el lenguaje de programación Python versión 3.2, escribe las funciones que se describen a continuación. Coloca todas las funciones en un mismo archivo llamado tarea_ordenamientos.py. En la parte superior del archivo coloca en comentarios los datos personales de los autores de la tarea. Por ejemplo:
#-------------------------------------------------------------------- # Actividad de programación: Ordenamientos # Fecha: 21-Sep-2012 # Autores: # 1166611 Pepper Pots # 1160611 Anthony Stark #--------------------------------------------------------------------
selection_sort(lst): Devuelve una nueva lista con el resultado de efectuar el algoritmo de ordenamiento por selección directa sobre lst. La función no debe modificar a lst.
Descripción del algoritmo: Empieza con una lista resultante vacía y una copia de lst. En cada iteración encuentra y remueve el elemento más pequeño de la copia de lst, y coloca dicho elemento al final de la lista resultante. Las iteraciones terminan cuando la copia de lst queda totalmente vacía. No olvides regresar la lista resultante.
Ejemplos:
>>> selection_sort([7, 8, 2, 0, 7, 6, 4, 5, 1, 2, 0, 5, 9, 3, 2]) [0, 0, 1, 2, 2, 2, 3, 4, 5, 5, 6, 7, 7, 8, 9] >>> selection_sort([]) []
merge_sort(lst1, lst2): Devuelve una nueva lista con el resultado de efectuar el algoritmo de ordenamiento por mezcla sobre lst1 y lst2. Las listas lst1 y lst2 deben llegar ya ordenadas de forma ascendente. La función no debe modificar a lst1 ni a lst2.
Descripción del algoritmo: Empieza con una lista resultante vacía y copias de lst1 y lst2. En cada iteración determina quien tiene al inicio el elemento x más pequeño de entre las copias de lst1 y lst2 (recuerda que tanto lst1 y lst2 están ordenadas de forma ascendente, por lo que los elementos más pequeños siempre estarán al mero inicio de cada una de estas listas). Remueve a x de la lista que lo contiene y añádelo al final de la lista resultante. Las iteraciones terminan cuando alguna de las copias de lst1 o lst2 queda vacía. En ese momento hay que copiar a la lista resultante todos los elementos que quedaron en la lista que aún no está vacía. No olvides regresar la lista resultante.
Ejemplos:
>>> merge_sort([3, 4, 6, 6, 7, 8, 10], [1, 2, 3, 4, 5, 6, 6, 10, 15]) [1, 2, 3, 3, 4, 4, 5, 6, 6, 6, 6, 7, 8, 10, 10, 15] >>> merge_sort([], [1, 2, 3, 4, 5, 6, 6, 10, 15]) [1, 2, 3, 4, 5, 6, 6, 10, 15] >>> merge_sort([3, 4, 6, 6, 7, 8, 10], []) [3, 4, 6, 6, 7, 8, 10] >>> merge_sort([], []) []
bucket_sort(lst): Devuelve una nueva lista con el resultado de efectuar el algoritmo de ordenamiento por casilleros sobre lst. Los elementos contenidos en lst deben ser números del 0 al 99. La función no debe modificar a lst.
Descripción del algoritmo: Empieza con diez listas vacías numeradas de la 0 a la 9. Recorre todos los elementos de lst, colocando cada elemento en la lista que le corresponda: los elementos del 0 al 9 van en la lista 0, los elementos del 10 al 19 van en la lista 1, los elementos del 20 al 29 van en la lista 2, y asi sucesivamente. Posteriormente ordena individualmente cada una de las listas de la 0 a la 9 (utiliza la función sorted() o el método sort() ya provistos en Python). Finalmente regresa el resultado de concatenar en orden todas las listas numeradas.
Ejemplos:
>>> bucket_sort([84, 44, 30, 74, 57,
62, 28, 3, 8, 17,
29, 90, 42, 83, 24,
65, 6, 14, 48, 25])
[3, 6, 8, 14, 17, 24, 25, 28, 29, 30, 42, 44, 48, 57, 62, 65, 74, 83, 84, 90]
>>> bucket_sort([])
[]
bogo_sort(lst): Devuelve una nueva lista con el resultado de efectuar el algoritmo de ordenamiento bogo sobre lst. La función no debe modificar a lst.
Descripción del algoritmo: Empieza con una copia de lst. Si dicha copia ya está ordenada entonces ya terminaste. De lo contrario, en cada iteración revuelve al azar todos sus elementos de la copia. Repite esto hasta que en una de esas, por una feliz coincidencia, todos los elementos queden ordenados de manera incremental. No olvides regresar la lista resultante.
Ejemplos:
>>> bogo_sort([57, 62, 17, 3, 8, 17, 29, 90]) [3, 8, 17, 17, 29, 57, 62, 90] >>> bogo_sort([]) []
Nota 1: Como te has de imaginar, este algoritmo es extremadamente ineficiente, y en teoría podría nunca terminar, sobre todo con listas de más de unos cuantos elementos.
Nota 2: Para revolver una lista al azar utiliza la función shuffle del módulo random. Ejemplos de uso (Ojo: los resultados pueden variar, pues las listas se revuelven al azar, duh!):
>>> from random import shuffle >>> a = [1, 2, 3, 4, 5] >>> shuffle(a) >>> a [4, 5, 1, 3, 2] >>> shuffle(a) >>> a [3, 2, 4, 5, 1]
quick_sort(lst): Devuelve una nueva lista con el resultado de efectuar el algoritmo de ordenamiento rápido sobre lst. La función no debe modificar a lst.
Descripción del algoritmo: Este algoritmo es de naturaleza recursiva. El caso base considera que si lst es una lista vacía entonces por definición ya está ordenada, por lo que la función devuelve una lista vacía. En cualquier otro caso se toma el primer elemento de lst como "pivote" y se crean dos nuevas listas: una que contenga todos los elementos de lst (excluyendo al pivote) que sean menores que el pivote, y otra lista que contenga todos los elementos de lst (también excluyendo al pivote) que sean mayores o iguales al pivote. Se ordenan ambas listas usando esta misma función de manera recursiva. La función finalmente devuelve la concatenación de tres listas: 1) la del resultado del ordenamiento recursivo de la primera lista, 2) una nueva lista que solo contiene al pivote, y 3) la del resultado del ordenamiento recursivo de la segunda lista.
Ejemplos:
>>> quick_sort([7, 8, 2, 0, 7, 6, 4, 5, 1, 2, 0, 5, 9, 3, 2]) [0, 0, 1, 2, 2, 2, 3, 4, 5, 5, 6, 7, 7, 8, 9] >>> quick_sort([]) []
Sube el archivo tarea_ordenamientos.py usando el Sistema de Entrega de Tareas Automatizado. No se aceptan tareas por ningún otro medio.
Fecha límite: Viernes, 21 de septiembre.
Esta actividad será evaluada usando los siguientes criterios:
| 100 | La actividad cumple con todos los requerimientos. |
|---|---|
| -10 | No se incluyó en comentario los datos de los autores. |
| 10 | El programa fuente contiene errores sintácticos. |
| 50-90 | El programa produce algunos errores al momento de correrlo. |
| DA | La solución es un plagio. |