Llistes i algorismes d'ordenació

Abans d’explicar i implementar l’algorisme de la bombolla, es farà una breu explicació sobre les funcions que prenen les llistes com a arguments, i com treballar i estructurar les dades que reben els programes (tant si entren per l’entrada estàndard com si ho fan per la línia d’ordres) abans d’enviar-les a aquestes funcions.

Per començar, codificareu un programa que calculi el màxim d’una llista de nombres enters i veurem com solucionar alguns problemes que apareixeran pel camí.

Enunciat: escriure un programa que trobi el màxim d’una llista de nombres enters entrada per la línia d’ordres.

Com sempre, cal començar amb un bon joc de proves que ens permeti validar el codi. Podeu veure’n un joc de proves a la taula.

Especificacions d’entrada: n nombres enters.

Aquest joc de proves proporciona diverses situacions per l’avaluació, incloent-hi una llista amb un únic element i una llista amb múltiples elements.

Abans de submergir-vos en el codi, cal pensar en el refinament. Es podria definir en els següents passos:

• Lectura d’una llista de nombres enters
• Cerca del màxim

En el pas del refinament cal també escollir quines seran les funcions necessàries.

Per a la tasca de trobar el màxim dels nombres enters l’ús d’una funció serà imprescindible. Quin seria el tipus d’entrada que rebrà? Com es pot estructurar aquesta funció perquè sigui reutilitzable i eficient? El docstring de la funció a definir serà el següent:

def maxim(l):
	'''
	Funció que troba el màxim d'una llista d'enters
	Entrada: Llista d'enters (de longitud > 0)
	Sortida: enter
	'''

Fixeu-vos que el docstring ha de definir les especificacions d’entrada que han d’acomplir les dades per poder accedir a la funció. Es considera que d’una llista buida no se’n pot trobar el màxim.

Respecte al pas de la lectura de la llista d’enters, és possible que sembli, d’entrada, que no serà necessari definir cap funció.

Amb aquests criteris en ment, es defineix la funció maxim(), en un fitxer que s’anomenarà modul_llistes en el que anireu codificant diverses funcions que us facilitaran la feina en els programes que utilitzin el tipus de dada list.

def maxim(l):
	'''
	Funció que troba el màxim d'una llista d'enters
	Entrada: Llista d'enters (de longitud > 0)
	Sortida: enter
	'''
	maxi = l[0]
	for n in l:
		if n > maxi:
			maxi = n
 
	return maxi
 
if __name__ == '__main__':
	if True:
		print(maxim([-1]))
		print(maxim([3, -4, -5, 78, 8, 19, 9]))    

Si executeu el fitxer, podreu verificar que el joc de proves s’acompleix.

D’entrada, el programa es pot pensar que és tan senzill com el següent:

import sys
import modul_llistes
 
# Lectura d'una llista de nombres enters
llista = sys.argv[1:]
# Búsqueda del màxim
print(modul_llistes.maxim(llista))

Si executeu el programa amb el joc de proves, el resultat és aquest:

$ python3 maxim_enters.py -1
-1
$ python3 maxim_enters.py -4 -5 78 8 19 9
9

Quin és l’error? La funció maxim() no està ben definida? La funció està ben definida i fa el que ha de fer si l’argument que entra és una llista d’enters. El problema del programa és que l’argument que se li envia a la funció maxim() no ho és, sinó que es tracta d’una llista de cadenes. Recordeu que sys.argv sempre és una llista de str.

L’error tampoc és que maxim() no accepti llistes de str, que sí que ho fa. El que ha passat en l’execució del programa és que a la funció li ha passat per alt una llista de str i ha utilitzat l’operador > per a comparar cadenes (que tenen sobreescrit el mètode dunder __gt__ per comparar segons l’ordre lexicogràfic).

El màxim que retorna la funció és el màxim entre les cadenes llegides. Si s’interpreten les entrades com a cadenes, el str '9' és major que el str ' 79' , de manera que la cadena llegida major és la '9'.

En treballar amb llistes caldrà que recordeu que els procediments que utilitzeu fins ara per entrar dades en un programa sempre entren dades de tipus str. Si les funcions necessiten enters o qualsevol altre tipus de dada caldrà que el programa en faci la conversió.

En l’exemple de trobar el màxim d’uns quants nombres enters llegits per la línia d’ordres, es poden prendre dues filosofies en el moment de codificar el programa:

• Si importa l’eficiència, es pot definir una funció que proporcioni el màxim d’una llista de cadenes enteres, considerant-les com a nombres. Aquesta funció transformaria cada str a un nombre enter, buscaria el màxim entre els enters i el retornaria. Aquest mètode és eficient perquè només recorre una vegada la llista d’entrada.
• Si el que importa és la modularitat, és millor definir una funció que busqui el màxim d’una llista d’elements del mateix tipus i que siguin comparables segons l’ordre definit per l’operador > (en altres paraules, que tinguin sobreescrit el dunder __gt__). Caldrà que prèviament el programa converteixi la llista de str llegida en una nova llista de int (directament o utilitzant una funció que converteixi la llista sencera).

Com que esteu en la lliçó de programació modular, s’optarà per la segona versió.

S’ha modificat el docstring() d’aquesta funció (i el test-driver) perquè s’acceptin llistes d’enters, de str i de qualsevol altre tipus de dada que es pugui comparar amb l’operador >. Per tant, el codi del mòdul llistes seria:

def maxim(l):
	'''
	Funció que troba el màxim dels elements d'una llista
	Entrada: Llista de dades del mateix tipus, comparables amb 
	l'operador >, i de longitud major que zero.
	Sortida: Dada del mateix tipus que les de la llista.
	'''
	maxi = l[0]
	for n in l:
		if n > maxi:
			maxi = n		
	return maxi
 
 
if __name__ == '__main__':
	if True:
		print(maxim([-1]))
		print(maxim([3, -4, -5, 78, 8, 19, 9])) 
		print(maxim(['3', '-4', '-5', '78', '8', '19', '9']))
		print(maxim(['hola', 'adeu']))
		print(maxim([(1, 2), (1, 2, 3), (1, 3)]))

El programa del càlcul del màxim de nombres enters seria el següent:

import sys
import modul_llistes
 
# Lectura d'una llista de nombres enters
llista = sys.argv[1:]
longitut = len(llista)
l_enters = [0] * longitut
for i in range(longitut):
	l_enters[i] = int(llista[i])
 
# Búsqueda del màxim
print(modul_llistes.maxim(l_enters))

I el resultat de l’execució seria el següent:

$ python3 maxim_enters.py -4 -5 78 8 19 9
78

L’algorisme de la bombolla és un dels algorismes d’ordenació més senzills de comprendre i implementar. Funciona comparant parells d’elements consecutius d’una llista i intercanviant-los si estan en l’ordre incorrecte. Aquest procés es repeteix fins que la llista està totalment ordenada:

1. Es comença amb una llista d’elements desordenats.
2. Es recorre la llista, comparant els elements consecutius.
3. Si l’element actual és més gran que el següent, s’intercanvia de posició.
4. En acabar la primera volta, es pot assegurar que l’element major està al final.
5. Es torna a començar el procés, des del que està en primera posició de la llista fins al penúltim (l’últim ja està ordenat).

El nom de l’algorisme prové del fet que en cada repetició s’aconsegueix que la “bombolla” (o l’element major) pugi fins a situar-se a dalt de tot (o al final de la llista). Vegem-ho:

1. En la primera passada s’aconsegueix que la bombolla ocupi l’última posició de la llista.
2. La segona passada comprèn des de la primera posició fins a la penúltima (l’última ja es troba ocupada per l’element més gran). S’aconseguirà “pujar” el segon element més gran a la penúltima posició.
3. La tercera passada només s’haurà de fer fins a arribar a l’antepenúltima posició (les dues últimes ja estaran ben ocupades). I s’aconseguirà que el tercer element més gran ocupi l’antepenúltima posició.

Si es fan totes les passades necessàries fins al final (quan la passada sigui només per als dos primers elements de la llista) es pot assegurar que la llista resultant estarà ordenada.

Considereu la següent llista: [5, 3, 8, 1, 2]. A continuació es mostren els passos que cal seguir, aplicant l’algorisme de la bombolla, fins a tenir-la completament ordenada:

1. Començar amb la llista [5, 3, 8, 1, 2].
2. Comparar els primers parells d’elements: (5, 3), (3, 8), (8, 1), (1, 2).
3. Intercanviar els elements que estan fora d’ordre: [3, 5, 1, 8, 2].
4. Tornar a comparar els parells d’elements: (3, 5), (5, 1), (1, 8), (8, 2).
5. Intercanviar els elements que estan fora d’ordre: [3, 1, 5, 2, 8].
6. Tornar a comparar els parells d’elements: (3, 1), (1, 5), (5, 2), (2, 8).
7. Intercanviar els elements que estan fora d’ordre: [1, 3, 2, 5, 8].
8. Tornar a comparar els parells d’elements: (1, 3), (3, 2), (2, 5), (5, 8).
9. Intercanviar els elements que estan fora d’ordre: [1, 2, 3, 5, 8].

La llista ara està totalment ordenada.

Si heu entès els passos de l’algorisme anterior, podeu comprovar que el codi de la funció per aplicar l’algorisme de la bombolla és el següent:

def bombolla(llista):
    '''
    Funció que ordena una llista de forma ascendent
    Entrada: llista d'enters
    Sortida: llista d'enters
    '''
    #Una passada per cada element (excepte el primer)
    for i in range(1, len(llista)): 
        # Cada vegada hi ha una nova 'bombolla' ben posada al final de la llista
        final = len(llista) - i 
        # cada element, s'intercanvia amb el posterior si no està ben posat
        for j in range(0, final): 
            if (llista[j] > llista[j + 1]): 
                t = llista[j] 
                llista[j] = llista[j + 1] 
                llista[j + 1] = t 
    return llista
 
if __name__ == '__main__':
    print(bombolla([5, 3, 8, 1, 2]))

Comproveu que l’algorisme funciona, executant diverses vegades el programa amb diferents llistes de nombres enters.

Com heu fet amb la funció del màxim, us podeu preguntar si l’algorisme de la bombolla serveix només per a ordenar nombres enters, o si també pot ordenar llistes dades d’altres tipus.

La resposta és la mateixa: aquesta funció pot ordenar llistes de qualsevol mena de dada que tingui sobreescrit el mètode dunder __gt__, i que, per tant, “entengui” la comparació quan s’utilitza l’operador >.

Caldrà afegir un joc de proves major i reescriure el docstring de la funció bombolla() tal com s’ha fet amb la funció maxim().

def bombolla(llista):
    '''
    Funció que ordena una llista de dades comparables amb l'operador >.
	Entrada: llista de dades del mateix tipus
	Sortida: Llista amb les mateixes dades ordenades
    '''
    #Una passada per cada element (excepte el primer)
    for i in range(1, len(llista)): 
		# Cada vegada hi ha una nova 'bombolla' ben posada al final de la llista
        final = len(llista) - i 
        # cada element, s'intercanvia amb el posterior si no està ben posat
        for j in range(0, final): 
            if (llista[j] > llista[j + 1]): 
                t = llista[j] 
                llista[j] = llista[j + 1] 
                llista[j + 1] = t 
    return llista
 
if __name__ == '__main__':
    print(bombolla([5, 3, 8, 1, 2]))
    print(bombolla(['3', '-4', '-5', '78', '8', '19', '9']))
    print(bombolla(['hola', 'adeu']))
    print(bombolla([(1, 2), (1, 2, 3), (1, 3)]))
    print(bombolla(''))

Ara que ja heu utilitzat i definit funcions amb tota mena d’arguments (enters, cadenes, llistes…) i tipus de retorn, és el moment de parlar de com Python maneja els valors de les variables quan es passen a les funcions.

En Python, quan es passen valors a les funcions, us podeu trobar amb dos escenaris principals: el pas per valor i el pas per referència. Per començar, s’estudiarà el concepte de pas per valor, on els valors dels paràmetres es copien en la memòria abans de passar-los a la funció. Veureu com això afecta diferents tipus de dades, inclosos de tipus immutables com int, float i str.

A continuació, s’abordarà el concepte de pas per referència, on es passa una referència a l’objecte en memòria, en lloc de fer una còpia del valor. Aquest comportament s’aplica a les llistes i els diccionaris (tipus de dada que encara no heu estudiat), que són tipus de dades mutables.

A continuació es veurà com s’aplica aquest concepte en les funcions i mètodes d’ordenació predefinits del sistema, i per acabar s’aplicarà a les funcions d’ordenació definides per vosaltres.

És important comprendre que el pas per valor no implica una còpia de l’objecte original, sinó una còpia del valor que fa referència a l’objecte en memòria. Això vol dir que si es modifica l’objecte referenciat pel paràmetre dins de la funció, aquest canvi no afectarà l’objecte original fora de la funció. Fixeu-vos en el codi següent:

def suma3(num):
	'''
	Funció que suma 3 a un enter
	input: int
	output: int
	'''
	num = num + 3
	return num
 
a = 5
b = suma3(a)
print(a, b)

El resultat de l’execució és el següent:

$ python3 exemple_pas_valor.py 
a 5
b 8

La variable a, que conté l’enter 5, ha arribat a la funció suma3() com a argument. Dins de la funció s’ha modificat el seu valor, passant a ser 8, valor que ha estat retornat al programa, i emmagatzemat en la variable b.

El valor inicial de la variable a no ha estat modificat, ja que Python ha passat aquest argument per valor: n’ha fet una còpia, que és la que ha enviat a la funció que l’ha modificat. Però el valor original s’ha mantingut intacte.

La naturalesa del pas per valor fa que sigui més segur manipular les variables dins de les funcions, ja que els canvis fets dins de la funció no afecten les variables originals fora de la funció. Això permet un millor control i previsibilitat del comportament del codi.

Segurament el pas per valor d’un argument a una funció no us sorprendrà, ja que és el que es fa amb tipus de dades immutables com són els int, els float o els str, i són els casos que més heu treballat fins ara.

A diferència del pas per valor, quan es passen tipus de dades mutables com llistes i diccionaris com a arguments a una funció, en realitat s’envia una referència a l’objecte en memòria. Això vol dir que quan es modifica l’objecte referenciat pel paràmetre dins de la funció, aquest canvi es reflecteix directament a les variables originals fora de la funció.

Fixeu-vos què passa quan s’executa el següent codi:

def suma3_a_tots(llista):
	'''
	Funció que suma 3 enters a tots els elements d'una llista
	input: llista d'enters
	output: None
	'''
	for i in range(0, len(llista)):
		llista[i] = llista[i] + 3
	return
 
l1 = [1, 2, 3]
suma3_a_tots(l1)
print(l1)

I l’execució:

$ python3 exemple_pas_ref.py 
[4, 5, 6]

Heu d’observar el següent:

• La funció suma3_a_tots() no retorna res (o retorna None).
• La llista l1 inicial s’ha modificat dins la funció. I els canvis són reals (el programa només té accés a la llista modificada, l’original s’ha perdut).
• Com que la funció no retorna res, tan sols es crida i no cal desar cap dada retornada.

El pas per referència permet la manipulació directa d’objectes en memòria, el que pot ser molt útil per a la manipulació eficient de dades i la creació de funcions que operen directament sobre estructures de dades complexes. Tanmateix, cal tenir en compte que aquest comportament pot comportar canvis inesperats en les variables originals fora de la funció si no s’administra correctament.

A continuació es mostraran un parell d’exemples que il·lustren les diferències entre el pas per valor i per referència. Tot i que les llistes sempre entren a la funció per referència, es pot crear una còpia dins de la funció i actuar com si haguessin estat passades per valor.

def modificar_llista(llista):
	'''
	Funció que afegeix el nombre quatre al final d'una llista d'enters
	Entrada: Llista d'enters
	Sortida: None
	'''
	llista.append(4)
 
llista_original = [1, 2, 3]
modificar_llista(llista_original)
print("Després de modificar la llista:", llista_original)

def crear_copia_llista(llista):
	'''
	Funció que crea una nova llista igual que l'entrada, i afegeix el nombre
	5 al final de l'original.
	Entrada: Llista d'enters
	Sortida: Llista d'enters
	'''
	nova_llista = []
	for el in llista:
		nova_llista.append(el)
	nova_llista.append(5)
	return nova_llista
 
llista_original = [1, 2, 3]
nova = crear_copia_llista(llista_original)
print("Després de crear una còpia de la llista:", llista_original)
print("Nova llista creada:", nova)

$ python3 llistes_referencia.py 
Després de crear una còpia de la llista: [1, 2, 3]
Nova llista creada: [1, 2, 3, 5]

def crear_copia_llista(llista):
	'''
	Funció que crea una nova llista igual que l'entrada, i afegeix el nombre
	5 al final de l'original.
	Entrada: Llista d'enters
	Sortida: None
	'''
	nova_llista = []
	for el in llista:
		nova_llista.append(el)
	nova_llista.append(5)
	return
 
llista_original = [1, 2, 3]
nova = crear_copia_llista(llista_original)
print("Després de crear una còpia de la llista:", llista_original)
print("Nova llista creada:", nova)

$ python3 llistes_referencia2.py 
Després de crear una còpia de la llista: [1, 2, 3]
Nova llista creada: None

llista = [1, 2, 3]
a = llista
b = llista
 
a[0] = 0
print(b)

$ python3 referencies.py 
[0, 2, 3]

def bombolla(llista):
    '''
    Funció que ordena una llista de dades comparables amb l'operador > (in situ)
	Entrada: llista de dades del mateix tipus
	Sortida: None
    '''
    #Una passada per cada element (excepte el primer)
    for i in range(1, len(llista)): 
		# Cada vegada hi ha una nova 'bombolla' ben posada al final de la llista
        final = len(llista) - i 
        # cada element, s'intercanvia amb el posterior si no està ben posat
        for j in range(0, final): 
            if (llista[j] > llista[j + 1]): 
                t = llista[j] 
                llista[j] = llista[j + 1] 
                llista[j + 1] = t 
    return 
 
if __name__ == '__main__':
    l1 = [5, 3, 8, 1, 2]
    bombolla(l1)
    print(l1)
    l2 = ['3', '-4', '-5', '78', '8', '19', '9']
    bombolla(l2)
    print(l2)
    l3 = ['hola', 'adeu']
    bombolla(l3)
    print(l3)
    l4 = [(1, 2), (1, 2, 3), (1, 3)]
    bombolla(l4)
    print(l4)

En resum podem dir que:

• Pas per valor (tipus de dades immutables): els tipus de dades immutables com int, float, str i tuple, en Python, es passen a les funcions per valor. En aquest cas, els canvis a les variables dins de la funció no afectaran les variables originals fora de la funció.
• Pas per referència (tipus de dades mutables): Python utilitza el pas per referència per a tipus de dades mutables com les llistes (i altres tipus de dades complexes). Aquestes canvien dins del programa tot i que la modificació s’hagi produït únicament dins l’àmbit de la funció.

En Python, les llistes disposen de funcions i mètodes d’ordenació predefinits que permeten ordenar els seus elements de manera ascendent o descendent. Dos dels més comuns són la funció sorted() i el mètode sort().

El docstring del mètode sort(), obtingut amb help(list.sort) és el següent:

sort(self, /, *, key=None, reverse=False)
    Sort the list in ascending order and return None.
 
    The sort is in-place (i.e. the list itself is modified) and stable (i.e. the
    order of two equal elements is maintained).
 
    If a key function is given, apply it once to each list item and sort them,
    ascending or descending, according to their function values.
 
    The reverse flag can be set to sort in descending order.
    Sort the list in ascending order and return None.
 
    The sort is in-place (i.e. the list itself is modified) and stable (i.e. the
    order of two equal elements is maintained).

Fixeu-vos en el seu ús: sort() no retorna res (o None), i si es vol mostrar el resultat de la seva acció, cal mostrar la llista. En aquest cas, el seu funcionament és com el de la funció modifica_llista(). La diferència és que modifica_llista() rep la llista com a argument i, en canvi, sort() és un mètode que s’engega sobre la mateixa llista.

Hi ha un paràmetre opcional (reverse), que permet modificar l’ordre de l’ordenació: és ascendent en cas que aquest paràmetre no hi sigui o valgui False, o descendent si crideu al mètode sorted() amb el paràmetre reverse = False. En ser un mètode de la classe list, només pot actuar sobre llistes. Altres tipus de seqüències immutables com les cadenes o les tuples no el poden utilitzar. El seu algorisme és semblant al mètode de la bombolla, però una mica més eficient i evita de fer tantes passades.

>>> c = [5, 2, 9]
>>> c.sort()
>>> c
[2, 5, 9]
>>> c.sort(reverse = False)
>>> c
[2, 5, 9]

El docstring de la funció sorted(), obtingut amb help(sorted()) és el següent:

sorted(iterable, /, *, key=None, reverse=False)
    Return a new list containing all items from the iterable in ascending order.

La funció sorted() retorna una nova llista ordenada amb els elements de la llista original. Aquesta funció no modifica la llista original, sinó que crea una nova llista amb els elements ordenats.

llista_original = [3, 1, 4, 2]
llista_ordenada = sorted(llista_original, reverse = True)
print("Llista original:", llista_original)
print("Llista ordenada descendent:", llista_ordenada)

$ python3 exemple_sorted.py 
Llista original: [3, 1, 4, 2]
Llista ordenada: [4, 3, 2, 1]

Aquesta funció té una altra particularitat: és capaç d’ordenar altres tipus de dades, a més a més de les llistes (com per exemple, les cadenes, tuples i els diccionaris). El seu tipus de retorn, però, sempre serà una llista. És capaç d’ordenar dades de tipus immutable perquè crea una llista on va desant els elements de la dada original de manera ordenada.

>>> a = 'cadena'
>>> sorted(a)
['a', 'a', 'c', 'd', 'e', 'n']
>>> b = (2, 5, 1, 3)
>>> sorted(b, reverse = True)
[5, 3, 2, 1]

El mètode sort() és preferible en termes d’eficiència i recursos de memòria, ja que ordena directament la llista original sense la necessitat de crear una nova llista. Aquest enfocament pot conduir a un millor rendiment del programa, especialment en aplicacions amb grans quantitats de dades.

• Utilitzeu el mètode sort() quan vulgueu ordenar la llista original i no us preocupi modificar-la in situ.
• Utilitzeu la funció sorted() només si necessiteu la llista ordenada i l’original.

sort() és un mètode que només poden utilitzar les llistes d’elements. Els elements d’aquestes llistes poden ser de qualsevol tipus que accepti l’ordre natural, que és el que està definit per l’operador <. En canvi, la funció sorted() és capaç d’ordenar altres estructures (com tuples i diccionaris) que compleixin determinades condicions.

En aquest apartat aprendreu a ordenar segons un criteri d’ordre personalitzat les llistes de dades. Per a fer-ho, recuperareu el mòdul de nombres_racionals i aprendreu primer a definir funcions pròpies que ordenin segons el criteri desitjat, i després a utilitzar les del sistema amb el mateix objectiu.

L’última versió del mòdul i la que s’utilitzarà en aquest apartat és la següent:

'''
Mòdul de funcions per a operar amb nombres racionals.
Una dada de tipus racional és un str amb el format 'num/den' que 
acompleix les següents condicions:
- num és un nombre enter
- den és un nombre enter diferent de zero.
- si den val 1, el str es pot escriure com 'num'
'''
 
# Funcions incorporades en aquest mòdul per comoditat. Haurien d'estar 
# en un mòdul matematiques. Per això es declaren com a privades.
def _es_enter(s):
	'''
	Funció que ens diu si una cadena és o no un enter
	Entrada: str 
	Sortida: bool
	'''
	if len(s) == 0:
		return False
	#traiem el signe, si cal
	if s[0] in '+-':
		s = s[1:]
	return s.isdigit()
 
def _maxim_comu_divisor(a, b):
	'''Funció que calcula el màxim comú divisor de dos nombres
	Entrada: n, m enters positius
	Sortida: int'''
	# algorisme per a calcular el màxim comú divisor
	t = 0
	while b != 0:
		t = b
		b = a % b
		a = t
	return a
 
# Funcions bàsiques 
def es_racional_valid(s):
	'''
	Funció per validar si una cadena és un racional vàlid. Accepta com a 
	racionals 3/1 i també 3
	Entrada: str
	Sortida: bool
	'''
	#comprovem si es tracta d'un enter
	if _es_enter(s):
		return True
	#separem la cadena per /
	l = s.split('/')
 
	#si no té 2 camps, malament
	if len(l) != 2:
		return False
	#treiem el signe si hi és
	#si cada camp no és enter, malament
	if not (_es_enter(l[0]) and _es_enter(l[1])):
		return False
	if int(l[1]) == 0:
		return False
 
	return True
 
def crea_racional(num, den):
	'''
	Funció que construeix una dada de tipus nombre racional
	Atenció, s'ha de comprovar que el resultat sigui un racional vàlid
	Entrada: dos enters. El segon diferent de zero.
	Sortida: String en format de racional (n/d o n)
	'''
	if den == 1:
		return str(num)		#ATENCIÓ, ha de ser str!!!
	return '%d/%d' % (num, den) 
 
def get_numerador(racional):
	'''
	Funció que retorna el numerador d'una cadena de tipus nombre 
	racional.
	Entrada: str tipus racional
	Sortida: int
	'''
	llista_r = racional.split('/')	
	return int(llista_r[0])
 
def get_denominador(racional):	
	'''
	Funció que retorna el denominador d'una cadena de tipus nombre 
	racional.
	Entrada: str tipus racional
	Sortida: Int (serà 1 en el cas que el racional sigui un enter
	'''
	llista_r = racional.split('/')	
	denominador = 1
	#si es tracta d'un enter, no pot petar
	if len(llista_r) == 2:
		denominador = int(llista_r[1])
	return denominador
 
# Operacions amb racionals
def suma(rac1, rac2):
	'''Funció que suma dos racionals. Atenció, també pot acceptar 'num' com
	a racional
	Entrada: 2 str en format racional
	Sortida: str en format racional correcte
	'''
	#extraiem numeradors i denominadors
	num1 = get_numerador(rac1)
	num2 = get_numerador(rac2)
	den1 = get_denominador(rac1)
	den2 = get_denominador(rac2)
 
	#busquem el denominador final (la multipl dels dos denominadors)
	den = den1 * den2
	num = num1 * den2 + num2 * den1
	return fraccio_canonica(crea_racional(num, den))
 
def multiplicacio(rac1, rac2):
	'''
	Funció que multiplica dos racionals. Atenció, també pot acceptar 'num' com
	a racional
	Entrada: 2 str en format racional
	Sortida: str en format racional 
	'''
	#extraiem numeradors i denominadors
	num1 = get_numerador(rac1)
	num2 = get_numerador(rac2)
	den1 = get_denominador(rac1)
	den2 = get_denominador(rac2)
 
	#busquem el denominador final (la multipl dels dos denominadors)
	num = num1 * num2
	den = den1 * den2
 
	return fraccio_canonica(crea_racional(num, den))
 
def resta(rac1, rac2):
	'''
	Funció que resta el segon racional del primer.
	Entrada: str (nombre racional)
	sortida: str (nombre racional)
	'''
	return suma(rac1, oposat(rac2))
 
def divisio(rac1, rac2):
	'''
	Funció que resta el segon racional del primer.
	ATENCIÓ: Utilitza la funció invers, de manera que cal comprovar que
	el resultat sigui un racional vàlid.
	Entrada: str (nombre racional)
	sortida: str (nombre racional)
	'''
	return multiplicacio(rac1, invers(rac2))
 
def oposat(racional):
	'''
	Funció que retorna l'oposat de un racional. l'oposat de a/b és -a/b.
	Entrada: str (nombre racional)
	Sortida:str (nombre racional)
	'''
	a = get_numerador(racional)
	b = get_denominador(racional)
	return crea_racional(-a, b)
 
def invers(racional):
	'''
	Funció que retorna l'invers de un racional. l'invers de a/b és b/a.
	ATENCIÓ: s'ha de comprovar que el numerador resultat sigui un racional vàlid
	Entrada: str (nombre racional)
	Sortida:str (nombre racional)
	'''
	a = get_numerador(racional)
	b = get_denominador(racional)
	return crea_racional(b, a)	
 
 
def fraccio_canonica(racional):
	'''
	Funció que simplifica, i retorna la fracció canònica d'un racional
	Entrada: str (nombre racional)
	Sortida: str (nombre racional)
	'''
 
	a = get_numerador(racional)
	b = get_denominador(racional)
 
	# guardar el signe
	positiu = True
	if a * b < 0:
		positiu = False
 
	# càlcul del mcm
	a = abs(a)
	b = abs(b)
	mcd = _maxim_comu_divisor(a, b)
 
	# valors del numerador i divisor (han de ser enters)
	a = a // mcd
	b = b // mcd
 
	#correcció del signe
	if not positiu:
		a = -a
 
	return crea_racional(a, b)
 
def representacio_decimal(racional):
	'''
	Funció que proporciona la representació decimal d'un nombre racional.
	Entrada: str (nombre racional)
	Sortida: float
	'''
	a = get_numerador(racional)
	b = get_denominador(racional)
	return a / b
 
# Mètodes semblants als dunders
def son_equivalents(rac1, rac2):
	'''
	Funció que implementa l'equivalència entre dos nombres racionals
	Entrada: str (nombre racional)
	Sortida: bool
	'''
	return (get_numerador(rac1) * get_denominador(rac2) == 
	 get_numerador(rac2) * get_denominador(rac1))
 
def es_major(rac1, rac2):
	'''
	Funció que diu si el primer nombre és major que el segon
	Entrada: str (nombre racional)
	Sortida: bool
	'''
	return representacio_decimal(rac1) > representacio_decimal(rac2)
 
def compara_racionals(rac1, rac2):
	'''
	Funció comparator de nombres racionals
	Entrada: 2 str (nombres racionals)
	Sortida: int 
				1 si rac1 > rac2
				0 si rac1 == rac2
				-1 si rac1 < rac2
	'''
	resultat = -1
	if es_major(rac1, rac2):
		resultat = 1
	elif son_equivalents(rac1, rac2):
		resultat = 0
	return resultat
 
#Test driver
if __name__ == '__main__':
 
	if False:
		print(_es_enter('-22'))
		print(_es_enter('-22.2'))
		print(_es_enter('+2'))
		print(_es_enter('2'))
		print(_es_enter(''))
		print()
 
	if False:
		print(('es un racional vàlid?'))
		print('45/4', es_racional_valid('45/4'))
		print('2.3/7', es_racional_valid('2.3/7'))
		print('-45/9', es_racional_valid('-45/9'))
		print('234/0', es_racional_valid('234/0'))
		print('23', es_racional_valid('23'))
		print('3/-33', es_racional_valid('3/-33'))
		print('2/1/-2', es_racional_valid('2/1/-2'))
		print('34m/23', es_racional_valid('34/23m'))
		print('34m/23.', es_racional_valid('34m/23.'))
		print('/', es_racional_valid('/'))
		print('6/', es_racional_valid('6/'))
		print('0/2', es_racional_valid('0/2'))		
		print('3/1', es_racional_valid('3/1'))
		print()
 
 
	if False:
		print('constructor de racionals')
		print(crea_racional(-4, -234))
		print(crea_racional(-2, 3))
		print(crea_racional(-23, 1))
		print(crea_racional(23, -1))
		print()
 
	if False:
		print('getters')
		print('23/-1')
		print('numerador: ', get_numerador('23/-1'))
		print('denominador: ', get_denominador('23/-1'))
		print('23')
		print('numerador: ', get_numerador('23'))
		print('denominador: ', get_denominador('23'))
		print()
 
	if False:
		print('suma')
		print('1/2  +  1/2 =', suma('1/2', '1/2'))
		print('2/4  +  1/6 =', suma('2/4', '1/6'))
		print('1/2  +  1/-2 =', suma('1/2', '1/-2'))
		print('3 + 5/2 = ', suma('3', '5/2'))
		print('3 + 5/1 = ', suma('3', '5/1'))
		print('3 + 5 = ', suma('3', '5'))
		print()
 
	if False:
		print('multiplicació')
		print('1/2  *  1/2	=', multiplicacio('1/2', '1/2'))
		print('-6/5  *  5/-2 =', multiplicacio('-6/5', '5/-2'))
		print('-6/-1  *  1/-6  =', multiplicacio('-6/-1', '1/-6'))
		print()
 
	if False:
		print('màxim comú divisor')
		print(_maxim_comu_divisor(4, 10))
		print(_maxim_comu_divisor(7, 60))
		print(_maxim_comu_divisor(7, 7))
		print()
 
	if False:
		print('la fracció canònica')
		print('2/4',fraccio_canonica('2/4'))
		print('14/24', fraccio_canonica('14/24'))
		print('1/4', fraccio_canonica('1/4'))
		print('-30/-10', fraccio_canonica('-30/-10'))
		print('6/-6', fraccio_canonica('6/-6'))
		print()
 
	if False:
		print('representacio_decimal')
		print('1/2', representacio_decimal('1/2'))
		print('4/2', representacio_decimal('4/2'))
		print('-6/-3', representacio_decimal('-6/-3'))
		print()
 
	if False:
		print(f'oposat i invers')
		print(f"1/2  oposat: {oposat('1/2')} invers: {invers('1/2')}")
		print(f"0/2  oposat: {oposat('0/2')} invers: {invers('0/2')}")
		print('ATENCIÓ: després de invers cal utilitzar es_racional_valid')
		print(f"4/-10  oposat: {oposat('4/-10 ')} invers: {invers('4/-10 ')}")
		print()
 
	if False:
		print(f'resta i divisió')
		print(f"1/2, 2/3 resta: {resta('1/2', '2/3')} divisió: {divisio('1/2', '2/3')}")
		print(f"0/2 , -2/-3 resta: {resta('0/2', '-2/-3')} divisio: {divisio('0/2', '-2/-3')}")
		print(f"-2/-3, 0 resta: {resta('-2/-3', '0')} divisio: {divisio('-2/-3', '0')}")
		print('ATENCIÓ: després de invers cal utilitzar es_racional_valid')
		print()
 
	if False:
		print('equivalència')
		print(f"2 i 4/2, {son_equivalents('2', '4/2')}")
		print(f"4/2 i 6/3, {son_equivalents('4/2', '6/3')}")
		print(f"2 i 6/3, {son_equivalents('2', '6/3')}")
		print(f"1/1000 i 1/1001, {son_equivalents('1/1000', '1/1001')}")
		print()
 
	if False:
		print("Comparació amb l'operador > ")
		print(f"1 > 1/2 {'1' > '1/2'}")
		print(f"3/5 > 4/5 {'3/5' > '4/5'}")
		print('es_major()')
		print(f"1 > 1/2 {es_major('1', '1/2')}")
		print(f"3/5 > 4/5 {es_major('3/5', '4/5')}")
		print()
 
	if True:
		print('compara_racionals')
		print(f"1 i 1/2 {compara_racionals('1', '1/2')}")
		print(f"3/5 i 4/5 {compara_racionals('3/5', '4/5')}")
		print(f"1/2 i 1/2 {compara_racionals('1/2', '1/2')}")

D’entrada, efectueu algunes operacions amb l’intèrpret interactiu, per recordar com operar amb nombres racionals:

>>> import nombres_racionals
>>> llista_racionals = ['2/3', '2', '9/10']
>>> nombres_racionals.suma(llista_racionals[0], llista_racionals[1])
'8/3'
>>> nombres_racionals.representacio_decimal(llista_racionals[0])
0.6666666666666666
>>> nombres_racionals.es_major(llista_racionals[0], llista_racionals[1])
False

Entre altres operacions, podeu:

• Sumar racionals (la suma de 2/3 i 1 dona 8/3)
• Calcular la representació decimal d’un racional (és a dir, efectuar la divisió). El racional 2/3 correspon al nombre float 0.666…
• Comparar dos nombres racionals i saber quin és major (2/3 no és major que 1).

Però quan s’utilitza el mètode sort() o la funció sorted(), s’ordena segons l’ordre natural del tipus de dada, i com que en el fons els racionals són str, el resultat obtingut no és el desitjat:

>>> nova_llista = sorted(llista_racionals)
>>> nova_llista
['2', '2/3', '9/10']
>>> llista_racionals
['2/3', '2', '9/10']
>>> llista_racionals.sort()
>>> llista_racionals
['2', '2/3', '9/10']

Les llistes s’ordenen, però segons l’ordre natural del tipus de dades. Els nombres racionals són str i l’ordre natural de les cadenes és l’ordre lexicogràfic. De manera que qualsevol cadena que comença amb el caràcter '2' és anterior a una cadena que comença amb el caràcter '9'.

En aquest apartat veureu com utilitzar l’algorisme d’ordenació de la bombolla per personalitzar l’ordre segons el qual necessiteu. Primer s’utilitzarà el mateix algorisme, modificant la manera de comparar els elements de la llista i utilitzant un comparator, i, en segon lloc, s’utilitzaran les funcions key, que posteriorment us permetran personalitzar els criteris d’ordre també amb els mecanismes d’ordenació que ofereix el sistema.

Recordeu la funció que heu definit de la bombolla, que ordena segons l’ordre natural (i rep la llista per referència):

def bombolla(llista):
    '''
    Funció que ordena una llista de dades comparables amb l'operador >
    (in situ)
	Entrada: llista de dades del mateix tipus
	Sortida: None
    '''
    for i in range(1, len(llista)): 
        final = len(llista) - i 
        for j in range(0, final): 
            # Línia de la comparació
            if (llista[j] > llista[j + 1]): 
                t = llista[j] 
                llista[j] = llista[j + 1] 
                llista[j + 1] = t 
    return 

Ordenar amb un comparator

Si us fixeu en l’algorisme, observareu que per a ordenar nombres racionals l’algorisme és el mateix. L’únic que caldria modificar és la manera com es comparen un parell de nombres racionals, ja que l’operador > no dona el resultat desitjat.

            if (llista[j] > llista[j + 1]): 
 

            if nombres_racionals.compara_racionals(llista[j], llista[j + 1]) == 1: 

import nombres_racionals
 
def bombolla_racionals_comparator(llista):
    '''
    Funció que ordena una llista de nombres racionals, utilitzant un comparator
    de racionals
	  Entrada: llista de racionals.
	  Sortida: None
    '''
    for i in range(1, len(llista)): 
        final = len(llista) - i 
        for j in range(0, final): 
            # Línia de la comparació
            if nombres_racionals.compara_racionals(llista[j], llista[j + 1]) == 1: 
                t = llista[j] 
                llista[j] = llista[j + 1] 
                llista[j + 1] = t 
    return 
 
if __name__ == '__main__':
    l1 = ['2/3', '2', '9/10']
    bombolla_racionals_comparator(l1)
    print(l1)

['2/3', '9/10', '2']

Ordenar amb una funció key

Les funcions key operen aplicant una transformació als elements de la llista abans de comparar-los durant l’ordenació. Això permet ordenar els elements basant-se en atributs específics o criteris personalitzats.

Es tracta de definir una funció que rebi per argument una dada del tipus que es vol ordenar (un racional, per exemple), i retorni una transformació de la mateixa aplicant el criteri que es vol utilitzar per a definir la relació d’ordre. Per exemple, en el cas d’un nombre racional, s’utilitza la seva representació decimal per determinar la seva posició d’ordre respecte a un altre element. Això ja ho sabeu perquè les funcions compara_racionals(), o es_major() utilitzen la funció representacio_decimal() per saber si un racional és major o no que un altre.

En aquest cas, la funció representacio_decimal() actua com a funció key per ordenar els nombres racionals. Com abans, per aplicar l’algorisme de la bombolla amb nombres racionals, només caldrà modificar la línia de la funció bombolla original, modificant la línia de codi en què s’efectua la comparació com a cadenes:

            if (llista[j] > llista[j + 1]): 
 

Per aquesta línia, on els elements de la llista, abans de ser comparats, són transformats per una funció key i comparats utilitzant l’operador >:

            if (nombres_racionals.representacio_decimal(llista[j]) > 
             nombres_racionals.representacio_decimal(llista[j + 1])) : 

En el cas dels racionals, per saber si un nombre és major que un altre, només cal buscar la seva representació decimal. La representació decimal proporciona un nombre de tipus float, que pot ser comparat amb l’operador > perquè té definit l’ordre natural.

El codi sencer seria:

import nombres_racionals
 
def bombolla_racionals_key(llista):
    '''
    Funció que ordena una llista de nombres racionals, utilitzant la funció
    representacio_decimal com a funció key.
	Entrada: llista de racionals.
	Sortida: None
    '''
    for i in range(1, len(llista)): 
        final = len(llista) - i 
        for j in range(0, final): 
            # Línia de la comparació
            if (nombres_racionals.representacio_decimal(llista[j]) > 
             nombres_racionals.representacio_decimal(llista[j + 1])) : 
                t = llista[j] 
                llista[j] = llista[j + 1] 
                llista[j + 1] = t 
    return 
 
if __name__ == '__main__':
    l1 = ['2/3', '2', '9/10']
    bombolla_racionals_comparator(l1)
    print(l1)

Si executeu el programa amb el mateix test-driver comprovareu que també ordena segons el nou criteri els nombres racionals.

def bombolla_longitud(llista):
    '''
    Funció que ordena una llista de nombres racionals, utilitzant la funció
    representacio_decimal com a funció key.
	Entrada: llista de racionals.
	Sortida: None
    '''
    for i in range(1, len(llista)): 
        final = len(llista) - i 
        for j in range(0, final): 
			# Línia de la comparació
            if len(llista[j]) > len(llista[j + 1]) : 
                t = llista[j] 
                llista[j] = llista[j + 1] 
                llista[j + 1] = t 
    return 
 
if __name__ == '__main__':
    l1 = ['abc', 'abecedari', 'z', 'bon dia', 'a']
    bombolla_longitud(l1)
    print(l1)

['z', 'a', 'abc', 'bon dia', 'abecedari']

Per acabar, es mostrarà com ordenar, amb relacions d’ordre definides per l’usuari, però utilitzant la funció sorted() i el mètode sort() que ofereix el Python. Fixeu-vos en els docstrings complets que proporciona l’ajuda:

Funció sorted():

sorted(iterable, /, *, key=None, reverse=False)
    Return a new list containing all items from the iterable in ascending order.
 
    A custom key function can be supplied to customize the sort order, and the
    reverse flag can be set to request the result in descending order.

Mètode de list sort():

sort(self, /, *, key=None, reverse=False)
    Sort the list in ascending order and return None.
 
    The sort is in-place (i.e. the list itself is modified) and stable (i.e. the
    order of two equal elements is maintained).
 
    If a key function is given, apply it once to each list item and sort them,
    ascending or descending, according to their function values.
 
    The reverse flag can be set to sort in descending order.

El paràmetre opcional key, en ambdós casos, es refereix a una funció del tipus key esmentada en l’apartat anterior. Només cal que definiu una funció que realitzi una transformació de la dada a comparar abans d’aplicar-li l’operador >, perquè es pugui ordenar amb l’ordre demanat.

Tant sort() com sorted() internament fan el mateix que vosaltres heu fet en l’apartat anterior: substituir la línia on s’efectua la comparació pel mateix, però aplicant la transformació de la funció key abans de la comparació.

>>> import nombres_racionals
>>> llista1 = ['2/3', '1', '-4', '3/2', '30/20']
>>> llista1.sort()
>>> llista1
['-4', '1', '2/3', '3/2', '30/20']
>>> llista1.sort(key = nombres_racionals.representacio_decimal)
>>> llista1
['-4', '2/3', '1', '3/2', '30/20']
>>> llista1.sort(key = len)
>>> llista1
['1', '-4', '2/3', '3/2', '30/20']