EINFÜHRUNG

Computer sind weit mehr als Numbercrunchers, also reine Rechenmaschinen zur Zahlenverarbeitung. Vielmehr ist bekannt, dass ein beträchtlicher Teil der Laufzeit aller weltweit in Betrieb stehender Computer für das Sortieren und Suchen von Daten verwendet wird. Es ist darum wichtig, dass ein Programm nicht nur die richtigen Daten liefert, sondern auch optimiert wird. Dies betrifft:

• seine Länge
• seine Struktur und Übersichtlichkeit
• seine Laufzeit
• seinen Speicherbedarf

Grundsätzlich gilt, dass die Optimierung bereits zu Beginn der Problemlösung mit einbezogen werden sollte, denn es ist meist schwierig, ein salopp geschriebenes Programm im Nachhinein zu optimieren.

In diesem Kapitel untersuchst du die Laufzeitoptimierung beim Sortieren von Daten. Dabei wirst du auch Grenzen der Informatik und des Computereinsatzes kennen lernen, denn ein Problem, für das es wohl einen algorithmischen Lösungsweg gibt, der schnellste Computer aber hunderte von Jahren zur Lösung benötigt, gilt als unlösbares Problem.

SORTIEREN WIE KINDER: CHILDREN SORT

Das Sortieren bzw. Ordnen einer Menge von Objekten, für die es die Vergleichsoperationen grösser, kleiner und gleich gibt [mehr... In der Mathematik nennt man dies eine Ordnungsrelation] , ist und bleibt eine Standardaufgabe der Informatik. Obschon du in allen gängigen höheren Programmiersprachen Bibliotheksroutinen findest, mit denen du sortieren kannst, gehören die Konzepte des Sortierens zu deinem Standardwissen, denn es gibt immer wieder Situationen, wo du das Sortieren selbst implementieren oder optimieren musst.

Eine Ansammlung unsortierter Objekte wird als eine Menge bezeichnet. Im Computer werden die Objekte aber in einer eindimensionalen Datenstruktur gespeichert, wozu sich eine Liste besonders gut eignet [mehr... Früher wurden oft Arrays verwendet, die allerdings den Nachteil einer festen Länge haben].

Oft werden Algorithmen direkt aus Verfahren übernommen, die man auch im täglichen Leben anwendet. Fragt man Kinder, wie sie eine Menge von Objekten der Grösse nach ordnen, so beschreiben sie das Verfahren oft so: "Du nimmst dir das kleinste (oder grösste) Objekt und setzt es der Reihe nach hin". Dieses Lösungsverfahren klingt sehr plausibel, ist aber für den Computer ein Problem, denn er kann das kleineste oder grösste Objekte nicht wie wir Menschen auf einen Blick erfassen. Er muss es in der unsortierten Liste zuerst suchen, indem er der Reihe nach alle Objekte durchläuft und die Objekte miteinander vergleicht. Um das Sortierverfahren, hier Children Sort genannt  zu implementieren, benötigst du eine Funktion getSmallest(row), die von der übergebenen Liste den kleinsten Zwerg zurückliefert. Dabei gehst du wie folgt vor:

Du speicherst das erste Listenelement in der Variablen smallest und durchläufst in einer for-Schleife alle nachfolgenden Elemente. Ist das gerade betrachtete Element kleiner als smallest, so ersetzt du smallest durch dieses Element.

Beim Chidren Sort verwendest du zwei Listen, eine Liste startList mit den gegebenen Objekten und die Liste targetList, die vorerst leer ist. Du suchst in startList das kleinste Element, nimmst es dort heraus und fügst es hinten in die targetList an, bis startList leer ist.

from gamegrid import *
from random import shuffle

def bodyHeight(dwarf):
    return dwarf.getImage().getHeight()

def updateGrid():
   removeAllActors()
   for i in range(len(startList)):
       addActor(startList[i], Location(i, 0))
   for i in range(len(targetList)):
       addActor(targetList[i], Location(i, 1))

def getSmallest(li):
    global count
    smallest = li[0]
    for dwarf in li:
        count += 1
        if bodyHeight(dwarf) < bodyHeight(smallest):
            smallest = dwarf
    return smallest

n = 7

makeGameGrid(n, 2, 170, Color.red, False)
setBgColor(Color.white)
show()

startList = []
targetList = []

for i in range(0 , n):
    dwarf = Actor("sprites/dwarf" + str(i) + ".png")
    startList.append(dwarf)
shuffle(startList)
updateGrid()
setTitle("Children Sort. Press <SPACE> to sort...")
count = 0
while not isDisposed() and len(startList) > 0:
    c = getKeyCodeWait()
    if c == 32:
        smallest = getSmallest(startList)
        targetList.append(smallest)
        startList.remove(smallest)
        count += 1
        setTitle("Count: " + str(count) + " <SPACE> for next step...")
        updateGrid()
setTitle("Count: " + str(count) + " All done")

MEMO

SORTIEREN BEIM KARTENSPIEL: INSERTION SORT

Nimmst du beim Ausspielen von Spielkarten Karte um Karte fächerartig in die Hand, so verwendest du meist intuitiv ein anderes Sortierverfahren: Du fügst jede neu aufgenommene Karte dort in die Hand ein, wo sie gemäss ihrer Wertigkeit hineinpasst. Im deinem Programm, dass die ungeordneten Karten von der Startliste (dem Kartenstapel) in die Zielliste (deine Hand) einfügt, gehst du genau so vor:

Du nimmst Karte um Karte von links nach rechts aus der Startliste und durchläuft die bereits geordnete Zielliste ebenfalls von links nach rechts. Sobald die aufgenommene Karte höhere Wertigkeit als die zuletzt in der Hand betrachtete ist, fügst du sie in die Zielliste ein.

from gamegrid import *
from random import shuffle

def cardValue(card):
    return card.getImage().getHeight()

def updateGrid():
   removeAllActors()
   for i in range(len(startList)):
       addActor(startList[i], Location(i, 0))
   for i in range(len(targetList)):
       addActor(targetList[i], Location(i, 1))

n = 9

makeGameGrid(n, 2, 130, Color.blue, False)
setBgColor(Color.white)
show()

startList = []
targetList = []

for i in range(0 , 9):
    card = Actor("sprites/" + "hearts" + str(i) + ".png")
    startList.append(card)

shuffle(startList)
updateGrid()
setTitle("Insertion Sort. Press <SPACE> to sort...")
count = 0

while not isDisposed() and len(startList) > 0:
    getBg().clear()
    c = getKeyCodeWait()
    if c == 32:
        pick = startList[0] # take first
        startList.remove(pick)
        i = 0
        while  i < len(targetList) and cardValue(pick) > cardValue(targetList[i]):
            i += 1
            count += 1
        targetList.insert(i, pick)
        count += 1
        setTitle("Count: " + str(count) + " <SPACE> for next step...")
        updateGrid()
setTitle("Count: " + str(count) + " All done")  

MEMO

SORTIEREN MIT LUFTBLASEN: BUBBLE SORT

Eine bekannte Art, Objekt in einer Liste zu sortieren, besteht darin, die Liste von links nach rechts mehrmals zu durchlaufen und immer zwei nebeneinander liegende Elemente zu vertauschen, falls sie in falscher Reihenfolge liegen. 

from gamegrid import *
from random import shuffle

def bubbleSize(bubble):
    return bubble.getImage().getHeight()

def updateGrid():
   removeAllActors()
   for i in range(len(li)):
       addActor(li[i], Location(i, 0))

def exchange(i, j):
    temp = li[i]
    li[i] = li[j]
    li[j] = temp

n = 7
li = []

makeGameGrid(n, 1, 150, Color.red, False)
setBgColor(Color.white)
show()
for i in range(0 , n):
    bubble = Actor("sprites/bubble" + str(i) + ".png")
    li.append(bubble)
shuffle(li)
updateGrid()
setTitle("Bubble Sort. Press <SPACE> for next step...")
k = n - 1
i = 0
count = 0
while not isDisposed() and k > 0:
    getBg().fillCell(Location(i, 0), makeColor("beige"))
    getBg().fillCell(Location(i + 1, 0), makeColor("beige"))
    refresh()
    c = getKeyCodeWait()
    if c == 32:
        count += 1
        bubble1 = li[i]
        bubble2 = li[i + 1]
        refresh()
        if bubbleSize(bubble1) > bubbleSize(bubble2):
             exchange(i, i + 1)
             setTitle("Last Action: Exchange. Count: " + str(count))
        else:
             setTitle("Last Action: No Exchange. Count: " + str(count))
        getBg().clear()        
        updateGrid()
        if i == k - 1:
            k = k - 1
            i = 0
        else:
            i += 1
getBg().clear()
refresh()
setTitle("All done. Count: " + str(count))

MEMO

MIT BIBLIOTHEKSROUTINEN SORTIEREN: TIMSORT

Da das Sortieren zu den wichtigsten Algorithmen gehört, stellen alle höheren Programmiersprachen eingebaute Bibliotheksfunktionen zum Sortieren zur Verfügung. In Python handelt es sich um die Funktion sorted(liste, cmp), die sogar zu den eingebauten Funktionen gehört, also ohne  import verwendet werden kann. Du kannst dir also deinen selbstgeschriebenen Sortieralgorithmus ersparen, dafür musst du aber lernen, wie die Bibliotheksfunktion verwendet wird. Offensichtlich benötigt sie als Parameter die zu sortierende Liste. Du musst ihr aber auch noch mit einem zweiten Parameter die Information mitgeben, nach welchem Ordnungskriterium sie die Objekte sortieren soll.

Das Sortierkriterium legst du in einer Funktion fest, die du hier mit compare() bezeichnest. Diese muss als Parameter die zwei Objekte erhalten und  drei Werte 1, 0 und -1 zurückgeben, je nachdem ob das erste Objekt grösser, gleich oder kleiner dem zweiten Objekt ist. Der Bibliotheksfunktion sorted() übergibst du den frei gewählten Funktionsnamen als zweiten Parameter oder mit dem benannten Parameter cmp.

from gamegrid import *
from random import shuffle

def bodyHeight(dwarf):
    return dwarf.getImage().getHeight()

def compare(dwarf1, dwarf2):
    if bodyHeight(dwarf1) < bodyHeight(dwarf2):
        return -1
    elif bodyHeight(dwarf1) > bodyHeight(dwarf2):
        return 1
    else:
        return 0

def updateGrid():
   removeAllActors()
   for i in range(len(li)):
       addActor(li[i], Location(i, 0))

n = 7
li = []

makeGameGrid(n, 1, 170, Color.red, False)
setBgColor(Color.white)
show()
for i in range(0 , n):
    dwarf = Actor("sprites/dwarf" + str(i) + ".png")
    li.append(dwarf)
shuffle(li)
updateGrid()
setTitle("Timsort. Press any key to get result...")
getKeyCodeWait()
li = sorted(li, cmp = compare)
updateGrid()
setTitle("All done.")  

MEMO

AUFGABEN

ZUSATZSTOFF

ÜBERLADEN DER VERGLEICHSOPERATOREN

Das Vergleichen von zwei Objekten ist eine wichtige Operation. Für Zahlen kannst du dazu die 5 Vergleichsoperationen <, <=, ==, >, = > verwenden. In Python ist es möglich, diese Operatoren auch für irgend einen anderen Datentyp einzusetzen, also beispielsweise für Zwerge. Dadurch gewinnt der Programmcode an Eleganz und Übersichtlichkeit.

Du gehst wie folgt vor:

Definiere in der Klassendefinition deines Datentyps die Methoden _lt_(), __le__(), __eq__(), __ge__(), __gt__(), die den booleschen Werte der Vergleichsoperation less, less-and-equal, equal, greater-and-equal, greater zurückgeben. Zusätzlich kannst du noch die Methode __str()__ definieren, die beim Aufruf der str() Funktion verwendet wird. Dies hat allerdings mit dem Sortieren nichts zu tun.

In der Klasse Dwarf, die von Actor abgeleitet ist, speicherst du als Instanzvariable zusätzlich noch den Namen des Zwergs, den du bei updateGrid() als TextActor ausschreibst.

from gamegrid import *
from random import shuffle

class Dwarf(Actor):
    def __init__(self, name, size):
        Actor.__init__(self, "sprites/dwarf" + str(size) + ".png")
        self.name = name
        self.size = size
    def __eq__(self, a):  # ==
        return self.size == a.size
    def __ne__(self, a): # !=
        return self.size != a.size
    def __gt__(self, a): # >
        return self.size > a.size
    def __lt__(self, a): # <
        return self.size < a.size
    def __ge__(self, a): # >=
        return self.size >= a.size
    def __le__(self, a): # <=
        return self.size <= a.size
    def __str__(self):  # str() function
        return self.name

def compare(dwarf1, dwarf2):
    if dwarf1 < dwarf2:
        return -1
    elif dwarf1 > dwarf2:
        return 1
    else:
        return 0

def updateGrid():
   removeAllActors()
   for i in range(len(row)):
       addActor(row[i], Location(i, 0))
       addActor(TextActor(str(row[i])), Location(i, 0))

n = 7
row = []
names = ["Monday", "Tuesday", "Wednesday", "Thursday", 
         "Friday", "Saturday", "Sunday"]

makeGameGrid(n, 1, 170, Color.red, False)
setBgColor(Color.white)
show()
for i in range(0 , n):
    dwarf = Dwarf(names[i], i)
    row.append(dwarf)
shuffle(row)
updateGrid()
setTitle("Press any key to get result...")
getKeyCodeWait()
row = sorted(row, cmp = compare)
updateGrid()
setTitle("All done.")

MEMO