cc 1002: introducción a la programación clase 20nbaloian/cc1002/cc... · mergesort: algoritmo...

CC 1002: Introducción a la Programación

Clase 20

Nelson Baloian, José A. Pino

MergeSort: algoritmo O(nlog2n)

1ª mitad 2ª mitad

situación inicial desordenada desordenada

ordenar mitades

situación intermedia

mezclar (“merge”)

situación final

Mergesort

def mergesort(x,ip,iu):

if ip>=iu: return #caso base

im=(ip+iu)/2 #índice de mitad

mergesort(x,ip,im) #ordenar 1ª mitad

mergesort(x,im+1,iu) #ordenar 2ª mitad

merge(x,ip,im,iu) #mezclar mitades

invocación

mergesort(lista,0,len(lista)-1)

Merge

def merge(x,ip,im,iu):

#lista auxiliar e indices

a=[] #lista auxiliar

i1=ip; i2=im+1 #indices para 1ª y 2ª mitad

#repetir hasta terminar una de las mitades

while i1<=im and i2<=iu:

#seleccionar y copiar el más pequeño

if x[i1]<x[i2]:

a.append(x[i1]); i1+=1

else:


#traspasar restantes de 1ª mitad (si quedan)

while i1<=im: a.append(x[i1]); i1+=1

#traspasar restantes de 2ª mitad (si quedan)

while i2<=iu: a.append(x[i2]); i2+=1

#copiar lista auxiliar en original

x[ip:iu+1]=a

Merge: 2ª. versión

def merge(x,ip,im,iu):

#recorrer mitades y lista auxiliar

a=[]

i1=ip; i2=im+1 #indices para 1a y 2a mitad

for i in range(ip,iu+1):

#si izq<der (o se terminó 2ª mitad)

if i1<=im \

and (i2>iu or x[i1]<x[i2]):


else:


#copiar lista auxiliar

x[ip:iu+1]=a

Analizando Mergesort

• Segunda versión de Merge: una sola pasada

• Fácil de programar

• Como habíamos mencionado, complejidad tiempo: O(nlogn)

• Si lista ya está ordenada o casi ordenada: no hay castigo

• ¿Desventaja?

La desventaja

• Necesitamos memoria extra (tanto como la lista original)

• En cambio, Quicksort no requiere memoria extra

QuickSort (Hoare, 1962): O(nlog2n) sin lista auxiliar

sit.inicial lista desordenada

ip iu

particionar

invariante desordenados < P P| desordenados P

i

ordenar partes

sit.final P|

P: pivote

elemento de la lista que se utiliza para separar (distribuir) los

otros elementos en menores y mayores o iguales

puede elegirse cualquiera (por ejemplo el primero)

las particiones resultan de distintos largos

¿log2n? en promedio particiones de largos iguales (≈mergesort)

def quicksort(x,ip,iu):

#caso base(1 elemento)

if ip>=iu: return

#particionar (y obtener indice de pivote)

i=particionar(x,ip,iu)

#ordenar 1ª parte

quicksort(x,ip,i-1)

#ordenar 2ª parte

quicksort(x,i+1,iu)

Particionamiento original de Hoare: algoritmo O(n)

sit.inicial P | ?

ip i j

invariante P| <P | ? | P

i j

final P| < P P

j i

intercambio < P | P P

j

def particionar(x,ip,iu):

#elegir pivote (por ejemplo: el primero)

pivote=x[ip]

#repetir hasta que indices se superen

i=ip+1; j=iu

while i<=j:

#avanzar índice de menores

while i<=j and x[i]<pivote:

i=i+1

#retroceder índice de mayores o iguales

while i<=j and x[j]>=pivote:

j=j-1

#intercambiar menor con mayor (si corr)

if i<=j:

x[i],x[j]=x[j],x[i]

i=i+1; j=j-1

#pivote a su posición final

x[ip]=x[j]; x[j]=pivote

return j


#elegir pivote (ej. Primero)

pivote=x[ip]

#inicializar índices

i=ip #ultimo de los menores que pivote

j=ip+1 #primero de los desconocidos

#recorrer todos los desconocidos

while j<=iu:

#si < pivote,intercambiar con 1ºde mayores

if x[j]<pivote:

i=i+1

x[i],x[j]=x[j],x[i]

j=j+1 #avanzar indice desconocidos


x[ip]=x[i]; x[i]=pivote

#devolver indice de pivote

return i


#elegir pivote

pivote = x[ip]

#inicializar índice de último de menores

i=ip

#recorrer elementos

for j in range(ip+1,iu+1):

#si menor que pivote juntarlo con menores

if x[j]<pivote:

i=i+1

x[i],x[j]=x[j],x[i]


x[ip]=x[i]

x[i]=pivote

return i

Introduciendo la Unidad 4

Hasta ahora hemos visto:

• Programación Funcional: problemas se modelan como funciones que toman

datos de entrada y retornan un valor simple o compuesto que sólo depende de la

entrada

• Programación Imperativa: estructuras actúan como memoria. Resultados

retornados por las funciones no sólo dependen de los valores de los parámetros de

la función, sino que también dependen del estado actual de estas estructuras

• Programación Orientada a Objetos (OOP): los conceptos básicos son objetos y

clases

¿Por qué introducimos este tercer tipo de programación? La solución de ciertos

problemas es más natural con este tipo de programación. Resolver problemas re-

usando soluciones anteriores…

Objeto

• Un objeto es un modelo computacional de un ente o concepto que posee ciertos atributos y con el cual podemos realizar ciertas operaciones

• Los objetos contienen tanto los datos asociados a estos como las operaciones que se pueden realizar con ellos

• Una clase permite describir en forma abstracta los atributos y operaciones del concepto modelado, que luego se instancia en un objeto

• La clase es esencialmente una fábrica para generar uno o más objetos. Cada objeto generado desde una clase tiene acceso a los atributos de la clase

Ejemplo

• Simulación de tránsito de automóviles

• Para cada automóvil: color, velocidad actual, velocidad máxima,

cantidad de gasolina en el estanque, etc.

• Operaciones: acelerar, frenar, apagar, consultar cuánta

gasolina queda en el estanque, cambiar color, etc.

• Crear clase Automovil:

class Automovil:

# …

# instrucciones para generar objetos

# interacciones entre objetos

Creando instancias de clases

>>> unAutomovil = Automovil ()

unAutomovil es entonces una instancia de la clase Automovil

A una instancia de la clase (objeto) se le pueden aplicar Métodos:

>>> unAutomovil.encender()

>>> unAutomovil.acelerar()

>>> unAutomovil.frenar()

>>> unAutomovil.apagar()

Métodos pueden recibir parámetros:

unAutomovil.acelerar(30) # presiona acelerador 30 seg.

Más sobre métodos

• Llamadas a métodos: contexto está unido al estado de cada objeto.

gasolina = unAutomovil.obtenerNivelGasolina ()

if gasolina > 0:

unAutomovil.acelerar()

else:

unAutomovil.frenar()

Más sobre objetos

Los objetos también pueden considerarse valores.

Por tanto, pueden pasarse como parámetros a métodos, o éstos

pueden retornar un objeto.

Por ejemplo, acelerar y frenar pueden retornar el objeto mismo.

Así podemos hacer este tipo de llamada:

>>>unAutomovil.acelerar().acelerar().frenar().acelerar()

Múltiples instancias

>>> unAutomovil = Automovil()

>>> otroAutomovil = Automovil()

¿En qué se diferencian?

Valores de los atributos constituyen el estado del objeto.

Tal como en las estructuras mutables, el estado de un objeto puede

cambiar.

Al instanciar el objeto, podemos poner valores a los atributos:

miAutomovil = Automovil(color="azul", velMaxima=220)

Y luego cambiarlos (al “enchularlo”):

miAutomovil.setColor("rojo")

miAutomovil.setVelocidadMaxima(250)

Otro ejemplo

Libreta de direcciones.

Supongamos que tenemos dos clases: Libreta y Registro

libretaPersonal = Libreta("personal")

libretaTrabajo = Libreta("trabajo")

registro1 = Registro(nombre ="Juan Gonzalez", \

telefono="777-7777", direccion="Calle ABC 123")

libretaTrabajo.agregarRegistro(registro1)

Métodos para buscar en

Libreta >>> john = libretaTrabajo.buscar("John")

>>> john.setTelefono("133")

>>> john.getTelefono()

"133"

(jueves)

Leer capítulo 15 del apunte

Para la próxima clase

cc 1002: introducción a la programación clase 20nbaloian/cc1002/cc... · mergesort: algoritmo...

Documents