Python 3 - Lernen und professionell anwenden

213

7.4

Listen

Durch die print()-Anweisung in Zeile #1 dokumentiert die Funktion ihre Arbeitsweise,

indem sie die Liste

s (also den aktuellen Suchbereich) ausgibt. Natürlich könnte man diese

Zeile auch weglassen. Wenn der Suchbereich nur noch aus einem einzigen Element be-

steht (

#2), vergleicht die Funktion dieses mit dem gesuchten Objekt x. Falls x und Listen-

element gleich sind, wird

1 zurückgegeben (x ist in der Liste enthalten), ansonsten 0 (x ist

nicht in der Liste enthalten).

Wenn der Suchbereich mehr als ein Element enthält, wählt die Funktion in Zeile

#3 das mitt-

lere Element

m aus. Falls das gesuchte Objekt größer oder gleich m ist, wird in der rechten

Hälfte der Liste

s weitergesucht (einschließlich des mittleren Elements m), ansonsten wird

die Suche in der linken Hälfte der Liste fortgesetzt. Das heißt, bei jedem rekursiven Aufruf

von

enthalten() ist die (Teil-)Liste, in der gesucht wird, nur noch halb so lang wie vorher.

Um die Funktion zu testen, erzeugen wir zunächst eine sortierte Liste von Zufallszahlen:

Nun prüfen wir, ob die (willkürlich gewählte) Zahl 17 in der Liste enthalten ist.

7.4.6 Zwei Sortierverfahren im Vergleich

Gewiss – Python-Listen besitzen eine Methode zum Sortieren. Insofern braucht man sich als

Python-Programmierer nicht mehr um die Entwicklung von Funktionen zum Listensortie-

ren zu kümmern. Andererseits gehören Sortierverfahren zu den klassischen Themen der

praktischen Informatik. An dem Problem des Sortierens lässt sich nämlich gut verdeut-

lichen, dass Algorithmen sich in ihrer Effizienz unterscheiden. Wenn große Datenmengen

verarbeitet werden, kommt es entscheidend darauf an, besonders effiziente Algorithmen zu

finden, die mit kleinen Laufzeiten und geringem Speicherplatzbedarf auskommen. Wir kon-

zentrieren uns hier auf den Aspekt der Laufzeit. Den Zeitbedarf eines Algorithmus in Abhän-

gigkeit von der Größe der Eingabedaten, die verarbeitet werden, bezeichnet man auch als

Zeitkomplexität.

Wie kann also eine beliebige Liste sortiert werden? Ein einfaches Verfahren nennt sich

Bubblesort. Die Idee ist folgende: Man vergleicht immer zwei benachbarte Elemente der

Liste. Ist das erste Element größer als das zweite, werden die beiden Elemente der Liste in

ihrer Reihenfolge vertauscht. Das macht man an allen Stellen der Liste, und zwar so lange,

bis man sicher ist, dass die Liste sortiert ist. Bubblesort wird durch folgende Funktion imple-

mentiert. Sie übernimmt eine beliebige Liste als Eingabe und gibt eine sortierte Liste zurück.

>>> import random

>>> s = [random.randint(0, 100) for i in range(16)]

>>> s.sort()

>>> enthalten(s, 17)

[1, 2, 4, 11, 16, 17, 18, 24, 41, 51, 59, 62, 65, 65, 83, 90]

[1, 2, 4, 11, 16, 17, 18, 24]

[16, 17, 18, 24]

[16, 17]

[17]

1