Ejercicio: Algoritmos de ordenación#
Los algoritmos de ordenación nos permiten reagrupar los elemementos de una estructura con un cierto orden (numérico, lexicográfico, etc). Hay varios algoritmos disponibles, cada uno con sus ventajas e inconvenientes en términos de complejidad temporal, espacial y estabilidad.
En este ejercicio vamos a definir dos algoritmos de ordenación comunes y estudiaremos su complejidad temporal respecto al tamaño del problema.
El algoritmo de ordenamiento de burbuja es un algoritmo de ordenación sencillo que propone ir comparando cada elemento de la lista con el siguiente e intercambiándolos de posición en caso de que esos elementos estén en el orden equivocado, aplicando dicha estrategia repetidamente hasta que la lista esté ordenada.
Por el contrario, el algoritmo de ordenamiento por mezcla se describe de la siguiente manera:
Si la longitud de la lista es 0 o 1, se considera que ya está en orden. De lo contrario:
La lista desordenada se divide en dos sublistas, cada una aproximadamente la mitad de la longitud total. Es decir, si la longitued de la lista es par, se divide en dos sublistas de igual longitud, en caso contrario, una sublista tendrá en elemento más que la otra.
Se aplica el ordenamiento por mezcla de manera recursiva a cada una de las sublistas.
Posteriormente, se combinan las dos sublistas resultantes para formar una única lista ordenada.
Exercise 78
Ejercicio 1
Crea una clase AlgoritmoOrdenacion que tenga un atributo lista, que será una lista de números (enteros o flotantes), y dos métodos ordena_burbuja y ordena_mezcla, que implementen, respectivamente, el algoritmo de ordenación de burbuja y por mezcla y ordenen, con respecto al orden natural de los números reales, el atributo lista.
from typing import List, Optional
class AlgoritmoOrdenacion:
def __init__(self, lista: Optional[List] = None):
if lista is None:
self.lista = []
else:
self.lista = lista
def ordena_burbuja(self):
n = len(self.lista)
for i in range(n):
for j in range(0, n-i-1):
if self.lista[j] > self.lista[j+1]:
self.lista[j], self.lista[j+1] = self.lista[j+1], self.lista[j]
def ordena_mezcla(self):
self._ordena_mezcla(self.lista)
def _ordena_mezcla(self, l: List):
if len(l) > 1:
media_longitud = len(l) // 2
mitad_izquierda = l[:media_longitud]
mitad_derecha = l[media_longitud:]
self._ordena_mezcla(mitad_izquierda)
self._ordena_mezcla(mitad_derecha)
i = j = k = 0
while i < len(mitad_izquierda) and j < len(mitad_derecha):
if mitad_izquierda[i] < mitad_derecha[j]:
l[k] = mitad_izquierda[i]
i += 1
else:
l[k] = mitad_derecha[j]
j += 1
k += 1
while i < len(mitad_izquierda):
l[k] = mitad_izquierda[i]
i += 1
k += 1
while j < len(mitad_derecha):
l[k] = mitad_derecha[j]
j += 1
k += 1
Exercise 79
Ejercicio 2
Implementa también los siguientes métodos
asigna_lista_ordenada: Toma como parámetro un enterony asigna el atributolistaa la lista[1, 2, ..., n].asigna_lista_ordenada_inversa: Toma como parámetro un enterony asigna el atributolistaa la lista[n, n-1, ..., 1].asigna_lista_orden_aleatorio: Asignalistaa una lista con losnprimeros enteros en orden aleatorio.
import random
class AlgoritmoOrdenacion2(AlgoritmoOrdenacion):
def asigna_lista_ordenada(self, n: int):
self.lista = list(range(n))
def asigna_lista_ordenada_inversa(self, n: int):
self.lista = list(range(n, 0, -1))
def asigna_lista_orden_aleatorio(self, n: int):
self.lista = list(random.randrange(n) for _ in range(n))
Exercise 80
Ejercicio 3
Crea otro método calcula_complejidad_temporal que tome como argumentos n_max e intentos, ambos enteros; y otro de tipo string tipo, que puede valer "burbuja" o "mezcla".
El método debe devolver un dataframe de pandas, cuyo índice se corresponda con la lista de enteros [0, 2, 4, ..., 2**n_max] y cuyas columnas sean tiempo_lista_ordenada, tiempo_lista_ordenada_inversa y tiempo_lista_orden_aleatorio cuyos valores sean el tiempo de ejecución de llamar el método de ordenación correspondiente un total de intentos veces y tomando la media.
from typing import Literal, Callable
import time
import pandas as pd
class AlgoritmoOrdenacion3(AlgoritmoOrdenacion2):
def calcula_complejidad_temporal(self, n_max: int, intentos: int, tipo: Literal["burbuja", "mezcla"]):
diccionario_algoritmo_ordenacion = {
'burbuja': self.ordena_burbuja,
'mezcla': self.ordena_mezcla
}
algoritmo_ordenacion = diccionario_algoritmo_ordenacion[tipo]
registro_tiempos = {}
for i in range(n_max):
self.asigna_lista_ordenada(2**i)
tiempo_lista_ordenada = self.calcula_tiempo_algoritmo(algoritmo_ordenacion, intentos)
self.asigna_lista_ordenada_inversa(2**i)
tiempo_lista_ordenada_inversa = self.calcula_tiempo_algoritmo(algoritmo_ordenacion, intentos)
self.asigna_lista_orden_aleatorio(2**i)
tiempo_lista_orden_aleatorio = self.calcula_tiempo_algoritmo(algoritmo_ordenacion, intentos)
registro_tiempos[2**i] = {
"tiempo_lista_ordenada": tiempo_lista_ordenada,
"tiempo_lista_ordenada_inversa": tiempo_lista_ordenada_inversa,
"tiempo_lista_orden_aleatorio": tiempo_lista_orden_aleatorio,
}
return pd.DataFrame.from_dict(registro_tiempos, orient='index')
def calcula_tiempo_algoritmo(self, algoritmo: Callable, intentos: int):
tiempos = []
for _ in range(intentos):
inicio = time.time()
algoritmo()
final = time.time()
tiempos.append(final - inicio)
return sum(tiempos) / intentos
Exercise 81
Ejercicio 4
Crea un método pinta_complejidad_temporal que tenga otro argumento tipo, similar al del ejercicio anterior, que llame al método calcula_complejidad_temporal (con valores de n_max e intentos a tu elección) y utilice matplotlib.pyplot para pintar un gráfico de línea representando la media de tiempo de ejecución frente al tamaño de las listas (utilizando escala logarítmica si fuera necesario), para el algoritmo correspondiente y para cada caso (lista ordenada, lista inversa, lista aleatoria).
Exercise 82
Ejercicio 5 (opcional)
En Python, una clase abstracta es una clase que no puede ser instanciada directamente y que generalmente sirve como una plantilla para otras clases. Su propósito principal es proporcionar una interfaz común para todas las clases derivadas, estableciendo un conjunto de métodos que deben ser implementados por las clases hijas. Una clase abstracta puede contener métodos abstractos, que son métodos sin una implementación definida en la clase abstracta.
Para crear una clase abstracta en Python, puedes utilizar el módulo abc (Abstract Base Classes). Aquí hay un ejemplo básico:
from abc import ABC, abstractmethod
class FiguraGeometrica(ABC):
@abstractmethod
def area(self):
pass
@abstractmethod
def perimetro(self):
pass
En este ejemplo, FiguraGeometrica es una clase abstracta que tiene dos métodos abstractos: area y perimetro. Las clases que heredan de FiguraGeometrica deben implementar estos métodos. Intentar instanciar directamente la clase abstracta o una clase derivada que no implemente todos los métodos abstractos resultará en un error.
Ejemplo de una clase que hereda de la clase abstracta:
class Cuadrado(FiguraGeometrica):
def __init__(self, lado):
self.lado = lado
def area(self):
return self.lado ** 2
def perimetro(self):
return 4 * self.lado
En este caso, la clase Cuadrado hereda de FiguraGeometrica y proporciona implementaciones concretas para los métodos abstractos area y perimetro.
El uso de clases abstractas ayuda a establecer contratos en la programación orientada a objetos, asegurando que las clases derivadas implementen ciertos métodos necesarios para su funcionamiento, lo que mejora la consistencia y la estructura del código.
Modifica la clase AlgoritmoOrdenacion para que sea una clase abstracta, con un método abstracto ordena y eliminando los argumentos tipo de calcula_complejidad_temporal y pinta_complejidad_temporal.
Crea clases hijas AlgoritmoBurbuja y AlgoritmoMezcla que implementen solamente el método ordena correspondiente.