2.21. Sortering

2.21.1. Sortering af basale typer

I mange computersprog bruges nogenlunde følgende rutine, når værdierne i to variabler skal bytte plads f.eks. i en sorteringsrutine:

>>> a = 50; b = 25
>>> temp = a
>>> a = b
>>> b = temp
>>> print a,b
25 50
>>>

I Python er samme proces kortere og mere logisk:
>>> a = 50; b = 25
>>> a, b = b, a
>>> print a,b
25 50
>>>

Sortering af elementerne i en liste foretages let med sort() funktionen:

>>> l = [2,34,5,4,78,6,12]
>>> l.sort()
>>> print l
[2, 4, 5, 6, 12, 34, 78]
>>>

Ud fra det, jeg har været inde på et eller flere andre steder i bogen, kan du passende forsøge at forklare, hvorfor også den følgende sortering er korrekt, for det er den.

>>> l = ["A","d","B","g","s","a","w","I","k","a","p","P"]
>>> l.sort()
>>> print l
['A', 'B', 'I', 'P', 'a', 'a', 'd', 'g', 'k', 'p', 's', 'w']
>>>

Sort funktionen kan anvendes uden parameter eller med en funktion som parameter. Anvendelsen uden parameter, som vist ovenfor, svarer helt til sort(cmp), hvor cmp() er en fordefineret funktion der sammenligner to værdier, x og y, og returnerer -1,0 og 1 afhængig af om\ x < y, x == y eller \ x > y.

>>> l = [2,34,5,4,78,6,12]
>>> l.sort()
>>> print l
[2, 4, 5, 6, 12, 34, 78]

Eller:
>>> l.sort(cmp)
>>> print l
[2, 4, 5, 6, 12, 34, 78]
>>>

Hvis du ønsker det, kan du let lave din egen sammenligningsfunktion:

>>> def Sam(a,b):
...     return a - b
...
>>> l = [2,34,5,4,78,6,1]
>>> l.sort(Sam)
>>> print l
[1, 2, 4, 5, 6, 34, 78]
>>>

Lambda kan være svær at forstå virkningen af. Som jeg er inde på andetsteds, så opererer lambda i baggrunden. Lad os se på Sam() ovenfor igen. Sam er en funktion med sit eget navn. Sam() trækker b fra a. Ved brug af lambda kan denne operation flyttes op i sort's parameterliste:

>>> l = [2,34,5,4,78,6,1]
>>> l.sort(lambda a, b : a- b)
>>> print l
[1, 2, 4, 5, 6, 34, 78]
>>>

Nu kunne jeg imidlertid godt tænke mig at anvende samme lambda på en sortering i faldende orden. Det eneste, jeg da skal gøre er at bytte om, så

>>> l = [2,34,5,4,78,6,1]
>>> l.sort(lambda a, b : b - a)
>>> print l
[78, 34, 6, 5, 4, 2, 1]
>>>

Tilsvarende kunne Sam() ganske let ændres til at fortage sortering med
faldende orden:
>>> def Sam(a,b):
...     return b - a
...
>>> l = [2,34,5,4,78,6,1]
>>> l.sort(Sam)
>>> print l
[78, 34, 6, 5, 4, 2, 1]
>>>

I sorteringrutiner er hastighed ofte et vigtigt parameter, så i sorteringer i stigende orden er det bedst at bruge sort uden parametre. Ønsker du sortering i faldende orden bliver ekspeditionstiden kortest ved at udføre operationen i to omgange. Først foretages en sortering i stigende orden med sort() og derefter anvendes funktionen reverse():

>>> l = [2,34,5,4,78,6,1]
>>> l.sort()
>>> l.reverse()
>>> print l
[78, 34, 6, 5, 4, 2, 1]
>>>

Med strengfunktionen split(), er det enkelt at konvertere en tekststreng til en liste. Når det er gjort, kan strengen sorteres helt tilsvarende den numeriske sortering, vi har set på ovenfor:

>>> import string
>>> streng = "Lad os dele opgaven op i enkeltelementer."
>>> s = streng.split()
>>> s
['Lad', 'os', 'dele', 'opgaven', 'op', 'i', 'enkeltelementer.']
>>> s.sort()
>>> s
['Lad', 'dele', 'enkeltelementer.', 'i', 'op', 'opgaven', 'os']
>>> s.reverse()
>>> s
['os', 'opgaven', 'op', 'i', 'enkeltelementer.', 'dele', 'Lad']
>>>

Her de samme rutiner med brug af Lambda funktionen:
>>> import string
>>> l = "Lad os dele opgaven op i enkeltelementer.".split()
>>> l.sort(lambda a,b:cmp(a,b))
>>> print l
['Lad', 'dele', 'enkeltelementer.', 'i', 'op', 'opgaven', 'os']
>>>

>>> import string
>>> l = "Lad os dele opgaven op i enkeltelementer.".split()
>>> l.sort(lambda a,b: - cmp(a,b))
>>>
>>> print l
['os', 'opgaven', 'op', 'i', 'enkeltelementer.', 'dele', 'Lad']
>>>

Her er en kasusafhængig strengsortering med stigende orden,
der anvender Lambda funktionen:
>>> import string
>>> l = "Lad os dele opgaven op i enkeltelementer.".split()
>>> l.sort(lambda a,b: cmp(string.lower(a), string.lower(b)))
>>> print l
['dele', 'enkeltelementer.', 'i', 'Lad', 'op', 'opgaven', 'os']

Og her den samme sortering i faldende orden:
>>> l.sort(lambda a,b: cmp(string.lower(b), string.lower(a)))
>>> print l
['os', 'opgaven', 'op', 'Lad', 'i', 'enkeltelementer.', 'dele']
>>>

Sorter strengen, indsæt elementerne i en tuple og sæt den
ind i en liste for senerer sortering:

>>> import string
>>> l = "Lad os dele opgaven op i enkeltelementer.".split()
>>> listen = []
>>> for i in range(len(l)):
...     listen.append((string.lower(l[i]),i))
...
>>> listen.sort()
>>> print listen
[('dele', 2), ('enkeltelementer.', 6), ('i', 5), ('lad', 0), ('op', 4),
('opgaven', 3), ('os', 1)]
>>>

Nu kan listen renses for tuplens indvirkning ved
(vi har ingen brug for indeksværdierne (tallene)) :

>>> nyListe = []
>>> for springOver, i in listen:
...     nyListe.append(l[i])
...
>>> print nyListe
['dele', 'enkeltelementer.', 'i', 'Lad', 'op', 'opgaven', 'os']
>>>

En anden vej til målet er at lagre de oprindelige data (elementer) som
listens andet led:

>>> import string
>>> l = string.split("Lad os dele opgaven op i enkeltelementer.")
>>> listen = []
>>> for element in l:
...     listen.append((string.lower(element), element))
...
>>>
>>> print listen
[('lad', 'Lad'), ('os', 'os'), ('dele', 'dele'), ('opgaven', 'opgaven'), ('op', 'op'),
 ('i', 'i'), ('enkeltelementer.', 'enkeltelementer.')]