Sortierverfahren

Sortierverfahren

Klaus Becker

2012

2 Sortierverfahren

3 Teil 1

Einen Datenbestand durchsuchen

4 Einen Datenbestand durchsuchen

Krause,Stefanie,Brandenburgische Str. 20,74343,Sachsenheim

Brandt,Mandy,Scharnweberstrasse 84,68199,Mannheim Almenhof

Möller,Jens,Schoenebergerstrasse 47,08313,Bernsbach

Herzog,Marco,Scharnweberstrasse 90,61130,Nidderau

Schmitz,Andreas,Meininger Strasse 84,66539,Neunkirchen Ludwigsthal

Ebersbacher,Michelle,Alt-Moabit 10,06691,Zeitz

Koertig,Christine,Hardenbergstraße 82,66887,Niederalben

Schmidt,Vanessa,Paderborner Strasse 44,86359,Gersthofen

Meister,Stephan,Fasanenstrasse 17,22605,Hamburg Othmarschen

...

Aachen,Anke,Reeperbahn 11,18201,Bad Doberan

Aachen,Dirk,Schmarjestrasse 80,33619,Bielefeld Innenstadt

Aachen,Anne,Gotzkowskystraße 77,75179,Pforzheim Nordweststadt

Abend,Kerstin,Lietzensee-Ufer 71,91217,Hersbruck

Abend,Kristin,Marseiller Strasse 44,21775,Steinau

Abend,Niklas,Knesebeckstraße 24,45770,Marl

Abend,Stephanie,Albrechtstrasse 42,55469,Oppertshausen

Abend,Annett,Ufnau Strasse 29,87640,Biessenhofen

Abend,Alexander,Budapester Straße 12,18273,Gleviner Burg

...

gesucht: Katja

Herrmann aus

Queidersbach

gesucht: Katja

Herrmann aus

Queidersbach

5

Algorithmische Suche - unsortierte Liste






Ebersbacher,Michelle,Alt-Moabit 10,06691,Zeitz

Koertig,Christine,Hardenbergstraße 82,66887,Niederalben

Schmidt,Vanessa,Paderborner Strasse 44,86359,Gersthofen

Meister,Stephan,Fasanenstrasse 17,22605,Hamburg Othmarschen

...

unsortierte Daten

Aufgabe:

(a) Entwickle einen Algorithmus, mit dem man in der gezeigten Datenliste nach einer Person mit einem vorgegebenen Nachnamen suchen kann.

Wenn der übergebene Name in der Datenliste vorkommt, dann soll der Index des zugehörigen Datensatzes zurückgegeben werden. Kommt der Name mehrfach vor, dann soll der Index des ersten passenden Datensatzes zurückgegeben werden. Kommt der Name in der Datenliste nicht vor, dann soll der Index -1 zurückgegeben werden.

(b) Implementiere den Algorithmus und teste ihn.

(siehe auch I:1.19.1.1.1)

6

Algorithmische Suche - sortierte Liste






Abend,Niklas,Knesebeckstraße 24,45770,Marl

Abend,Stephanie,Albrechtstrasse 42,55469,Oppertshausen

Abend,Annett,Ufnau Strasse 29,87640,Biessenhofen

Abend,Alexander,Budapester Straße 12,18273,Gleviner Burg

...

sortierte Daten

Aufgabe:

(a) Betrachte verschiedene Szenarien. Wann kann man jeweils die Suche abbrechen, wenn man die Daten des Datenbestandes der Reihe nach durchläuft?

(b) Passe den Suchalgorithmus entsprechend an. Implementiere und teste ihn anschließend.


7


def suchen(name, liste): indexErgebnis = -1 gefunden = False links = 0 rechts = len(liste)-1 while not gefunden and links <= rechts: mitte = (links + rechts) // 2 if name == liste[mitte][0]: gefunden = True indexErgebnis = mitte elif name < liste[mitte][0]: rechts = mitte-1 else: links = mitte+1 return indexErgebnisbinäre

Suche

Aufgabe:

Die folgende (in Python implementierte) Funktion benutzt ein Suchverfahren, das den Namen "binäre Suche" hat.

(a) Beschreibe den hier zu Grunde liegenden Algorithmus in eigenen Worten. Verdeutliche ihn auch anhand von Beispielen.

(b) Teste die Funktion mit dem gegebenen Datenbestand.


8


Aufgabe:

Das Suchverfahren "binäre Suche" kann man auch mit einem rekursiven Algorithmus beschreiben.

Entwickle diesen Algorithmus (oder recherchiere ihn im Internet). Implementiere den Algorithmus anschließend und teste ihn.

9 Lineare Suche - unsortierte Liste

Suche: Ga Ergebnis: -1

Suche: Ko Ergebnis: 5

Gr, Lo, Br, Mi, Sc, Ko, Fr, Be, Ke, Na, Eb, Kr, Wi, Sc, He,

Gr, Lo, Br, Mi, Sc, Ko, Fr, Be, Ke, Na, Eb, Kr, Wi, Sc, He,

def suchen(name, liste): gefunden = False indexErgebnis = -1 i = 0 while i < len(liste) and not gefunden: if name == liste[i][0]: gefunden = True indexErgebnis = i else: i = i+1 return indexErgebnis

10 Lineare Suche - sortierte Liste

Suche: Ga

Be, Br, Eb, Fr, Gr, He, Ke, Ko, Kr, Lo, Mi, Na, Sc, Sc, Wi,

def suchen(name, liste): indexErgebnis = -1 i = 0 while i < len(liste) and name > liste[i][0]: i = i+1 if name == liste[i][0]: indexErgebnis = i return indexErgebnis

Ergebnis: -1

Suche: Ta


Ergebnis: -1

Suche: Ko


Ergebnis: 7

11 Binäre Suche - sortierte Liste

Suche: Ga




Ga,

Ga,

Ga,


Ga,


def suchen(name, liste): indexErgebnis = -1 gefunden = False links = 0 rechts = len(liste)-1 while not gefunden and links <= rechts: mitte = (links + rechts) // 2 if name == liste[mitte][0]: gefunden = True indexErgebnis = mitte elif name < liste[mitte][0]: rechts = mitte-1 else: links = mitte+1 return indexErgebnis

12 Binäre Suche - sortierte Liste

Suche: Ta




Ta,

Ta,

Ta,



Ta,

def suchen(name, liste): indexErgebnis = -1 gefunden = False links = 0 rechts = len(liste)-1 while not gefunden and links <= rechts: mitte = (links + rechts) // 2 if name == liste[mitte][0]: gefunden = True indexErgebnis = mitte elif name < liste[mitte][0]: rechts = mitte-1 else: links = mitte+1 return indexErgebnis

13 Teil 2

Einen Datenbestand sortieren

14 Das Sortierproblem






...






...

Das Sortierproblem besteht darin, Verfahren zu entwickeln, die eine sortierte Anordnung von Datensätzen automatisiert erzeugen.

Die einzige Voraussetzung, die die Daten erfüllen müssen, besteht darin, dass man sie nach einem Kriterium vergleichen kann. Es soll also möglich sein, bei zwei Daten D1 und D2 (der Ausgangsdatenliste) zu entscheiden, ob (nach dem vorgegebenen Vergleichskriterium) D1 kleiner als D2 oder D2 kleiner als D1 ist oder ob D1 und D2 bzgl. des Vergleichskriterium gleichwertig sind.

15

Das Sortierproblem - formal betrachtet

Gegeben ist eine Liste von Datensätzen [D0, D1, ..., Dn-2, Dn-1].

Die Datensätze sollen über eine Ordnungsrelation < verglichen werden können. Es soll also möglich sein, Vergleiche wie D0 < D1 eindeutig zu entscheiden.

Mit der Ordnungsrelation ≤ erfassen wir die Möglichkeit, dass zwei Datensätze in dem zu vergleichenden Merkmal übereinstimmen können. Es soll D1 ≤ D0 gelten, wenn D0 < D1 nicht gilt.

Gesucht ist eine neue Anordnung der Datensätze

[Dp(0), Dp(1), ..., Dp(n-2), Dp(n-1)]

mit der Eigenschaft, dass

Dp(0) ≤ Dp(1) ≤ ... ≤ Dp(n-2) ≤ Dp(n-1) gilt.

Die neue Anordnung der Datensätze wird hier durch eine bestimmte Anordnung (man sagt auch Permutation) p(0), p(1), ..., p(n-2), p(n-1) der Indexwerte 0, 1, ..., n-2, n-1 beschrieben.

16 Entwicklung von Sortierverfahren

Aufgabe ist es im Folgenden, ein (oder mehrere) Sortierverfahren zu entwickeln.

Für die Entwicklung von Sortierverfahren spielt die Komplexität der Daten keine zentrale Rolle. Wir gehen daher im Folgenden von einfachen Daten (hier Zahlen) aus.

25 17 32 56 25 19 8 66 29 6 20 29

6 8 17 19 20 25 25 29 29 32 56 66

17 Vorgehen wie ein Computer

Ein Computer hat (in der Regel) keinen Überblick über alle Daten. Er kann zudem (in der Regel) nicht so intelligent wie ein Mensch agieren.

Um die Arbeitsweise eines Computers zu simulieren, legen wir Regeln fest, die beim Sortieren beachtet werden müssen.

Zunächst einmal werden alle Karten umgedreht. Der "Sortierer" hat keine Gesamtsicht auf alle Daten.

25 17 32 56 25 19 8 66 29 6 20 29

18 Spielregeln

Regel 1: Karten umdrehen:

25 17 32 56 25 19 8 66 29 6 20 29

Regel 2: 2 Karten vergleichen und in Abhängigkeit des Ergebnisses weiteragieren:

25 17 32 56 25 19 8 66 29 6 20 29

<

?

Regel 3: Karten markieren (es dürfen auch mehrere unterscheidbare Marken benutzt werden):

25 17 32 56 25 19 8 66 29 6 20 29

19 Spielregeln

Regel 4: Eine Karte an eine andere Stelle verschieben:

Regel 5: Karten austauschen (d.h. zwei Karten geeignet verschieben):

Weitere (sinnvolle) Regeln können nach Bedarf eingeführt werden.

25 17 32 56

25

19 8 66 29 6 20 29

25 17 32 56 19 8 66 29 6 20 29

20 Teil 3

Sortieralgorithmen

21 Sortierverfahren

Es gibt zahlreiche Verfahren, um Datensätze zu sortieren. Wir werden uns im Folgenden auf 4 Standardverfahren konzentrieren.

22

Selectionsort (Sortieren d. Auswählen)

Wie sortieren Kartenspieler ihre Spielkarten? Auf YouTube wird ein Verfahren gezeigt, das Selectionsort genannt wird. Schaue dir das Video genau an. Kannst du die Grundidee des benutzten Sortierverfahrens beschreiben?

23


25 17 32 56 25 19 8 66 29 6 20 29

6

6 8

25 17 32 56 25 19 8 66 29 20 29

25 17 32 56 25 19 66 29 20 29

6 8 2517 32 56 25 19 66 29 20 29

Idee: Suche jeweils das kleinste Element im unsortierten Bereich und lege es am Ende des sortierten Bereichs ab.

24

25 17 32 56 25 19 8 66 29 6 20 29

6

6 8

25 17 32 56 25 19 8 66 29 20 29

25 17 32 56 25 19 66 29 20 29

6 8 2517 32 56 25 19 66 29 20 29


Realisierung mit 2 Listen

ALGORITHMUS selectionsort

Übergabe: Liste L

unsortierter Bereich ist die gesamte Liste L

der sortierte Bereich ist zunächst leer

SOLANGE der unsortierte Bereich noch Elemente hat:

suche das kleinste Element im unsortierten Bereich

entferne es im unsortierten Bereich

füge es im sortierten Bereich an letzter Stelle an

Rückgabe: sortierter Bereich

25

25 17 32 56 25 19 8 66 29 6 20 29

6

6 8

25 17 32 56 25 19 8 66 29 20 29

25 17 32 56 25 19 66 29 20 29

6 8 2517 32 56 25 19 66 29 20 29



ALGORITHMUS selectionsort

Übergabe: Liste L

unsortierter Bereich ist die gesamte Liste L

der sortierte Bereich ist zunächst leer

SOLANGE der unsortierte Bereich noch Elemente hat:

suche das kleinste Element im unsortierten Bereich

entferne es im unsortierten Bereich

füge es im sortierten Bereich an letzter Stelle an


26

Insertionsort (Sortieren d. Einfügen)

Auf YouTube gibt es eines interessantes Video zum Sortieren durch Einfügen. Schaue dir das Video genau an. Wie gehen die Tänzer beim Sortieren vor? Kannst du die Grundidee des benutzten Sortierverfahrens beschreiben?

27


Idee: Füge jeweils das erste Element des unsortierten Bereichts an der richtigen Stelle im sortierten Bereich ein.

25

17 25

17 25 32

17 32 56 25 19 8 66 29 6 20 29

32 56 25 19 8 66 29 6 20 29

56 25 19 8 66 29 6 20 29

17 25 32 56 25 19 8 66 29 6 20 29

17 25 32 5625 19 8 66 29 6 20 29

28

25

17 25

17 25 32

17 32 56 25 19 8 66 29 6 20 29

32 56 25 19 8 66 29 6 20 29

56 25 19 8 66 29 6 20 29

17 25 32 56 25 19 8 66 29 6 20 29

17 25 32 5625 19 8 66 29 6 20 29



ALGORITHMUS insertionsort

Übergabe: Liste

sortierter Bereich besteht aus dem ersten Element der Liste

unsortierter Bereich ist die Restliste (ohne das erste Element)

SOLANGE der unsortierte Bereich Elemente hat:

entferne das erste Element aus dem unsortierten Bereich

füge es an der richtigen Stelle im sortierten Bereich ein


29


Realisierung mit 1 Liste

25

17 25

17 25 32

17 32 56 25 19 8 66 29 6 20 29

32 56 25 19 8 66 29 6 20 29

56 25 19 8 66 29 6 20 29

17 25 32 56 25 19 8 66 29 6 20 29

17 25 25 32 56 19 8 66 29 6 20 29

ALGORITHMUS insertionsort

Übergabe: Liste

sortierter Bereich besteht aus dem ersten Element der Liste

unsortierter Bereich ist die Restliste (ohne das erste Element)

SOLANGE der unsortierte Bereich Elemente hat:

füge das erste Element des unsortierten Bereichs an der richtigen Stelle im sortierten Bereich ein

verkleinere den unsortierten Bereich


30

Bubblesort (Sortieren d. Aufsteigen)

Auf YouTube gibt es eines interessantes Video zum Sortieren. Schaue dir das Video genau an. Wie gehen die Lego-Arbeiter beim Sortieren vor? Kannst du die Grundidee des benutzten Sortierverfahrens beschreiben?

31


Idee: Durchlaufe (mehrfach) den gesamten Bereich. Vergleiche jeweils zwei benachbarte Element und vertausche sie, wenn die Reihenfolge nicht stimmt.

25 17 32 56 25 19 8 66 29 6 20 29

17 25 32 56 25 19 8 66 29 6 20 29

17 25 32 56 25 19 8 66 29 6 20 29

17 25 32 56 25 19 8 66 29 6 20 29

17 25 32 25 56 19 8 66 29 6 20 29

17 25 32 25 19 8 56 29 6 20 29 66

...

32



25 17 32 56 25 19 8 66 29 6 20 29

17 25 32 56 25 19 8 66 29 6 20 29

17 25 32 56 25 19 8 66 29 6 20 29

17 25 32 56 25 19 8 66 29 6 20 29

17 25 32 25 56 19 8 66 29 6 20 29

17 25 32 25 19 8 56 29 6 20 29 66

...

ALGORITHMUS bubblesort

Übergabe: Liste

unsortierter Bereich ist zunächst die gesamte Liste

SOLANGE der unsortierte Bereich mehr als ein Element hat:

duchlaufe den unsortierten Bereich von links nach rechts

wenn dabei zwei benachbarte Elemente in der falschen Reihenfolge vorliegen:

vertausche die beiden Elemente

verkürze den unsortierten Bereich durch Weglassen des letzten Elements

Rückgabe: überarbeitete Liste

33 Quicksort (Sortieren d. Zerlegen)

Eine Person (z.B. die erste in der Reihe) wird als Vergleichsperson ausgewählt. Im vorliegenden Beispiel ist das Anton.

Anton

1.74 Britta

1.64

Carlo

1.85

Durs

1.89

Georg

1.78

Fiona

1.67

Greta

1.61

Fabian

1.92

Jana

1.78

Hannah

1.58

Igor

1.70

Eli

1.74

Britta

1.64

Fiona

1.67

Greta

1.61

Hannah

1.58

Igor

1.70

Anton

1.74 Carlo

1.85

Durs

1.89

Georg

1.78

Fabian

1.92

Jana

1.78

Eli

1.74

Alle anderen ordnen sich links bzw. rechts von der Vergleichsperson ein, je nachdem, ob sie kleiner oder größergleich als die Vergleichsperson sind.


Anton bleibt jetzt auf seiner Position. Er nimmt nicht mehr an weiteren Spielrunden teil. Dasselbe Spiel wird jetzt im linken und im rechten Bereich durchgeführt: Eine Person (z.B. die erste in der Reihe) wird wiederum als Vergleichsperson ausgewählt.

Wie geht das Spiel weiter? Wann ist das Spiel beendet? Welche Extremfälle können während des Spiels auftreten? Funktioniert das Sortierspiel dann auch noch?

Britta

1.64 Fiona

1.67

Greta

1.61

Hannah

1.58

Igor

1.70

Anton

1.74

Carlo

1.85 Durs

1.89

Georg

1.78

Fabian

1.92

Jana

1.78

Eli

1.74


Idee: Ein Element der Liste (z.B. das erste Element) wird ausgewählt. Die Restliste wird dann gemäß dieses Elements in zwei Teillisten aufgeteilt: die Liste der Elemente der Restliste, die kleiner als das ausgewählte Element sind sowie die Liste der Elemente der Restliste, die nicht kleiner (d.h. größer oder gleich) als das ausgewählte Element sind. Dieser Vorgang wird mit den Teillisten völlig analog fortgesetzt.

25 17 32 56 25 19 8 66 29

2517 32 56 2519 8 66 29

6 20 29

6 20 29

Zerlegen

Zusammensetzen

256 25 29 298 17 32 5619 20 66

6 8 17 19 20 25 25 29 29 32 56 66

Zerlegen

Zusammens.

Zerlegen

Zusammens.

... ...


ALGORITHMUS quicksort

Übergabe: Liste L

wenn die Liste L mehr als ein Element hat:

# zerlegen

wähle als Pivotelement p das erste Element der Liste aus

erzeuge Teillisten K und G aus der Restliste (L ohne p) mit:

- alle Elemente aus K sind kleiner als das Pivotelement p

- alle Elemente aus G sind größergleich als das Pivotelement p

# Quicksort auf die verkleinerten Listen anwenden

KSortiert = quicksort(K)

GSortiert = quicksort(G)

# zusammensetzen

LSortiert = KSortiert + [p] + GSortiert

Rückgabe: LSortiert

Realisierung mit mehreren

Listen

37

Quicksort (Sortieren d. Zerlegen) - alt.

Eine Person (z.B. die erste in der Reihe) wird als Vergleichsperson ausgewählt.Suche von links eine Person, die größergleich als die ausgewählte Person ist. Suche von rechts eine Person, die kleinergleich als die ausgewählte Person ist.

Anton

1.74

Britta

1.64

Carlo

1.85

Durs

1.89

Georg

1.78

Fiona

1.67

Greta

1.61

Fabian

1.92

Jana

1.78

Hannah

1.58

Igor

1.70

Eli

1.75

Wenn "links < rechts": Personen tauschen ihre Position in der Reihe.

Igor

1.70

Britta

1.64

Carlo

1.85

Durs

1.89

Georg

1.78

Fiona

1.67

Greta

1.61

Fabian

1.92

Jana

1.78

Hannah

1.58

Anton

1.74

Eli

1.75

usw.

38


ALGORITHMUS quicksort

Übergabe: Liste L

wenn die Liste L nicht leer ist:

# zerlegen

wähle als Pivotelement p (z.B.) das erste Element der Liste aus

tausche Elemente innerhalb L so, dass eine Zerlegung entsteht mit:

- L = K + G alle Elemente aus K sind kleinergleich als das Pivotelement p alle Elemente aus G sind größergleich als das Pivotelement p K und G enthalten mindestens ein Element


quicksort(K)

quicksort(G)

Rückgabe: L


39

>>> Quicksort: [21, 9, 20, 45, 5, 58, 40, 17]

Quicksort: [17, 9, 20, 5]

Quicksort: [5, 9]

Quicksort: [20, 17]

Quicksort: [45, 58, 40, 21]

Quicksort: [21, 40]

Quicksort: [58, 45]


def quicksort(L, anfang, ende): if L != []: pivot = L[anfang] links = anfang rechts = ende while links <= rechts: while L[links] < pivot: links = links+1 while L[rechts] > pivot: rechts = rechts-1 if links <= rechts: if links < rechts: h = L[links] L[links] = L[rechts] L[rechts] = h links = links+1 rechts = rechts-1 if anfang < rechts: L = quicksort(L, anfang, rechts) if links < ende: L = quicksort(L, links, ende) return L Implementieru

ng mit 1 Liste

40


Quicksort [29, 17, 56, 6, 60, 41, 8, 25, 30, 20, 32, 19]Pivot: 29 [19, 17, 20, 6, 25, 8] [41, 60, 30, 56, 32, 29]Quicksort [19, 17, 20, 6, 25, 8]Pivot: 19 [8, 17, 6] [20, 25, 19]Quicksort [8, 17, 6]Pivot: 8 [6] [17, 8]Quicksort [17, 8]Pivot: 17 [8] [17]Quicksort [20, 25, 19]Pivot: 20 [19] [25, 20]Quicksort [25, 20]Pivot: 25 [20] [25]Quicksort [41, 60, 30, 56, 32, 29]Pivot: 41 [29, 32, 30] [56, 60, 41]Quicksort [29, 32, 30]Pivot: 29 [29] [29, 32, 30]Quicksort [32, 30]Pivot: 32 [30] [32]Quicksort [56, 60, 41]Pivot: 56 [41] [60, 56]Quicksort [60, 56]Pivot: 60 [56] [60]

41 Teil 4

Laufzeitverhalten

42 Zielsetzung

Algorithmen stellen oft nur einen Zwischenschritt beim Problemlösen dar. In der Praxis ist man meist an Programmen - also Implementierungen von Algorithmen in einer Programmiersprache - interessiert, die von Rechnern real ausgeführt werden können. Dabei spielt der Ressourcenverbrauch (Laufzeitverhalten und Speicherplatzbelegung) der Programme eine zentrale Rolle. Erwünscht sind solche Programme, die mit möglichst wenig Ressourcen auskommen. Wir werden uns im Folgenden auf die Ressource "Rechenzeit" konzentrieren, da Speicherplatz heute für viele Problemlösungen genügend zur Verfügung steht.

Laufzeitmessungen liefern wichtige Informationen über die Einsetzbarkeit von Programmen. Programme, bei denen man sehr lange auf Ergebnisse warten muss, sind - je nach Anwendungsgebiet - oft nicht praxistauglich.

Ziel der folgenden Untersuchungen ist es, das Laufzeitverhalten von Sortieralgorithmen zu ermitteln und die Ergebnisse genauer zu analysieren.

43

from time import *print("Start")t1 = clock()# Ausführung des Programms ...t2 = clock()t = t2 - t1print("Stopp")print("Rechenzeit: ", t)

Laufzeitmessungen

from time import *from random import randint

# Sortieralgorithmusdef selectionsort(L): ... # Initialisierung der Listeprint("Aufbau der Testliste")anzahl = 100L = []for i in range(anzahl): L = L + [randint(1, 10*anzahl)]print(L)print("Start des Sortiervorgangs")# Sortierung der Listet1 = clock()L_sortiert = selectionsort(L)t2 = clock()t = t2 - t1print("Ende des Sortiervorgangs")# Ausgabeprint(L_sortiert)print("Rechenzeit: ", t)

Muster

Beispiel

44

from time import *from random import randint# Sortieralgorithmus...# Initialisierung der Anzahl der Listenelementeanzahl = 1000while anzahl < 10000: # Erzeugung der Liste L = [] for i in range(anzahl): L = L + [randint(1, 10*anzahl)] # Bestimmung der Rechenzeit t1 = clock() L_sortiert = selectionsort(L) t2 = clock() t = t2 - t1 # Ausgabe des Messergebnisses print("Anz...: ", anzahl, "Rechenzeit: ", t) # Erhoehung der Anzahl anzahl = anzahl + 1000

Systematische Laufzeitmessungen

>>> Anzahl der Listenelemente: 1000 Rechenzeit: 0.208472864568Anzahl der Listenelemente: 2000 Rechenzeit: 0.82472800314Anzahl der Listenelemente: 3000 Rechenzeit: 1.83589394742Anzahl der Listenelemente: 4000 Rechenzeit: 3.3119754047Anzahl der Listenelemente: 5000 Rechenzeit: 5.27956234661Anzahl der Listenelemente: 6000 Rechenzeit: 7.45063213341Anzahl der Listenelemente: 7000 Rechenzeit: 9.99217191012Anzahl der Listenelemente: 8000 Rechenzeit: 13.1027999369Anzahl der Listenelemente: 9000 Rechenzeit: 16.5563961341

Beispiel

Wir bestimmen die Laufzeit t(n) systematisch in Abhängigkeit der Listenlänge n für wachs-ende Listenlängen (z.B. n = 1000, 2000, ...).

45 Laufzeitmessungen - Selectionsort

Aufgabe:

Führe selbst systematische Laufzeitmessungen durch (u.a. für Selectionsort und Quicksort). Versuche, anhand der Messwerte Gesetzmäßigkeiten aufzudecken (z.B.: Wie ändert sich t(n), wenn man n verdoppelt?) Benutze die Gesetzmäßigkeiten, um Vorhersagen zu treffen (z.B.: Wie lange dauert es, um ... Listenelemente zu sortieren?). Überprüfe deine Vorhersagen.

46

Anzahl der Listenelemente: 1000

Rechenzeit: 0.204296356101


Rechenzeit: 0.809496178984


Rechenzeit: 1.83842583345













...

Laufzeitmessungen - Selectionsort

*2

*2

*2

47


Rechenzeit: 0.0178980848125


Rechenzeit: 0.0625291761942


Rechenzeit: 0.133521718542


Rechenzeit: 0.176368784301


Rechenzeit: 0.351487409713


Rechenzeit: 0.330103965727




Rechenzeit: 0.854964248249


Rechenzeit: 0.942683218119

...

Laufzeitmessungen - Quicksort

*2

*2

*2

# ALGORITHMUS quicksort(L)


# zerlegen

wähle als Pivotelement p das erste Element d. Liste aus

erzeuge Teillisten K und G aus "L ohne p" mit


- alle Elemente aus G sind nicht kleiner als p




# zusammensetzen


# Rückgabe: LSortiert

48


Rechenzeit: 0.00662849607981


Rechenzeit: 0.0137794049244


Rechenzeit: 0.0227299838387


Rechenzeit: 0.031230226188


Rechenzeit: 0.0419377323096


Rechenzeit: 0.0518194351517


Rechenzeit: 0.0589655947893


Rechenzeit: 0.069147894495


Rechenzeit: 0.0784993623491

...

Laufzeitmessungen - Quicksort

*2

*2

*2



# zerlegen


tausche Elemente innerhalb L so, dass eine Zerlegung L = K + [p] + G entsteht mit

- alle Elemente aus K sind kleiner als Pivotelement p



quicksort(K)

quicksort(G)

# Rückgabe: L

49

StartStoppRechenzeit: 3.27038296767StartStoppRechenzeit: 3.23336066455StartStoppRechenzeit: 3.25390210208StartStoppRechenzeit: 3.2653359575StartStoppRechenzeit: 3.24174441165StartStoppRechenzeit: 3.25976206473StartStoppRechenzeit: 3.2584529598StartStoppRechenzeit: 3.26073537279StartStoppRechenzeit: 3.23565201723StartStoppRechenzeit: 3.23315561056

Schwierigkeiten bei Laufzeitmessungen

StartStoppRechenzeit: 3.2807468547StartStoppRechenzeit: 3.41092736647StartStoppRechenzeit: 3.4124093984StartStoppRechenzeit: 5.37245627587StartStoppRechenzeit: 6.69305316737StartStoppRechenzeit: 6.70120168904StartStoppRechenzeit: 6.67988976253StartStoppRechenzeit: 6.67656727321StartStoppRechenzeit: 6.70371150523StartStoppRechenzeit: 4.73779544607

Selectionsort - wiederholte

Durchführung einer

Laufzeitmessung

Selectionsort - wiederholte

Durchführung einer

Laufzeitmessung

50

Problematik von Laufzeitmessungen

Laufzeitmessungen werden in der Praxis durchgeführt, um das Laufzeitverhalten eines Programms unter Realbedingungen zu ermitteln.

Aus systematisch durchgeführten Laufzeitmessungen kann man oft Gesetzmäßigkeiten erschließen, wie die Laufzeit von den zu verarbeitenden Daten abhängt.

Bei Laufzeitmessungen muss man aber sehr genau darauf achten, dass sie unter gleichen Bedingungen erfolgen. Ein Wechsel des Rechners führt in der Regel zu anderen Ergebnissen. Auch Änderungen in der Implementierung wirken sich in der Regel auf die Messergebnisse aus. Selbst bei ein und demselben Rechner und derselben Implementierung können sich die Bedingungen ändern, da oft mehrere Prozesse gleichzeitig ablaufen.

Ergebnisse von Laufzeitmessungen sind also kaum auf andere Systeme (andere Rechner, andere Programmiersprachen) übertragbar. Um diese Schwierigkeit zu überwinden, soll im Folgenden ein anderer Weg zur Beschreibung der Berechnungskomplexität beschritten werden.

51 Teil 5

Aufwandsanalyse

52 Zielsetzung

Experimentell bestimmte Laufzeiten haben den Nachteil, dass sie vom benutzen Rechner und den Bedingungen auf dem Rechner (Prozesse, die dort laufen) abhängen. Solche Rechenzeiten sind also nur bedingt aussagekräftig. Erschwerend kommt manchmal hinzu, dass Rechenzeiten bei manchen Problemstellungen so groß werden, dass man sie bis heute noch nicht ermitteln konnte.

Neben experimentellen Methoden benutzt man in der Informatik daher auch mathematische Methoden zur Einschätzung des Laufzeitverhaltens. Man versucht dabei, das Laufzeitverhalten abzuschätzen und abstrahierend zu beschreiben.

53 Kostenabschätzung

def selectionsort(L): n = len(L) i = 0 while i < n-2: minpos = i m = i while m < n: if L[m] < L[minpos]: minpos = m m = m+1 h = L[i] L[i] = L[minpos] L[minpos] = h i = i+1 return L

Bei der Ausführung des Algorithmus (bei vorgegebenen Problemgröße) spielt es eine Rolle, wie viele Operationen ausgeführt werden müssen. Operationen sind im vorliegenden Algorithmus u.a. das Ausführen eines Vergleichs und das Ausführen einer Zuweisung. Als Kostenmaß zur Beschreibung des zeitlichen Aufwands könnte man also die Gesamtanzahl der auszuführenden Vergleiche und Zuweisungen wählen. Bei der Festlegung eines Kostenmaßes müssen Annahmen über den Aufwand der

verschiedenen auszuführenden Operationen gemacht werden. Zwei ganz unterschiedliche Wege kann man dabei bestreiten. Ein Weg besteht darin, unterschiedliche Aufwände von Operationen möglichst genau zu erfassen und im Kostenmaß zu berücksichtigen. Ein anderer Weg beschränkt sich darauf, dominante Operationen auszuwählen und die Kosten nur grob zuzuschätzen. Wir werden hier nur den zweiten Weg beschreiten.

54 Kostenabschätzung

def selectionsort(L): n = len(L) i = 0 while i < n-2: minpos = i m = i while m < n: if L[m] < L[minpos]: minpos = m m = m+1 h = L[i] L[i] = L[minpos] L[minpos] = h i = i+1 return L

Aufgabe:

Wie viele Vergleiche von Listenelementen werden bei der Ausführung des Algorithmus / Programms durchgeführt? Ergänze die Funktionsdefinition um einen geeigneten Zähler.

55 Kostenanalyse - Selectionsort| 25 17 32 56 25 19 8 66 29 6 20 29 Vergleiche: 11 ^

6 | 17 32 56 25 19 8 66 29 25 20 29 ^

6 8 | 32 56 25 19 17 66 29 25 20 29 ^

6 8 17 | 56 25 19 32 66 29 25 20 29 ^

6 8 17 19 | 25 56 32 66 29 25 20 29 ^

6 8 17 19 20 | 56 32 66 29 25 25 29 ^

6 8 17 19 20 25 | 32 66 29 56 25 29 ^

6 8 17 19 20 25 25 | 66 29 56 32 29 ^

6 8 17 19 20 25 25 29 | 66 56 32 29 ^

6 8 17 19 20 25 25 29 29 | 56 32 66 ^

...

Problemgröße: n Datensätze

Kostenmaß:Anzahl der Vergleiche

Kostenfunktion:n -> (n-1)+(n-2)+...+1

Selectionsort

56 Kostenanalyse - Insertionsort 25 | 17 32 56 25 19 8 66 29 6 20 29 Vergleiche: 1

17 25 | 32 56 25 19 8 66 29 6 20 29

17 25 32 | 56 25 19 8 66 29 6 20 29

17 25 32 56 | 25 19 8 66 29 6 20 29

17 25 25 32 56 | 19 8 66 29 6 20 29

17 19 25 25 32 56 | 8 66 29 6 20 29 ...



Kostenfunktion:n -> ?

Insertionsort

Aufgabe:

Bestimme jeweils die Anzahl der benötigten Vergleiche.

Bei welcher Ausgangssituation sind die Kosten besonders ungünstig / günstig?

Wie lautet in diesen beiden Fällen die Kostenfunktion?

57 Kostenanalyse

best case (bester Fall): der Fall, in dem bei der Ausführung des Algorithmus die wenigsten Kosten anfallen

worst case (schlechtester Fall): der Fall, in dem bei der Ausführung des Algorithmus die meisten Kosten anfallen

average case (durchschnittlicher Fall): eine Mittelung der Kosten über alle Fälle

Die Anzahl der Datensatzvergleiche bei der Ausführung eines Sortieralgorithmus hängt manchmal nicht nur von der Problemgröße n (d.h. der Anzahl der Listenelemente) ab, entscheidend ist auch, wie stark die Liste bereits vorsortiert ist.

12 | 17 32 35 35 40 51 66 70 82 88 91 Vergleiche: 1 12 17 | 32 35 35 40 51 66 70 82 88 91 Vergleiche: 1 12 17 32 | 35 35 40 51 66 70 82 88 91 Vergleiche: 1

...Kostenfunktion: n -> n-1

91 | 88 82 70 66 51 40 35 35 32 17 12 Vergleiche: 1 88 91 | 82 70 66 51 40 35 35 32 17 12 Vergleiche: 2 82 88 91 | 70 66 51 40 35 35 32 17 12 Vergleiche: 3

... Kostenfunktion: n -> 1+ 2 + ... + (n-1)

Insertionsort

Insertionsort

58 Kostenmodellierung als Problem

Genauere Analysen zeigen, dass bei längeren Listen die Verwaltung und die Verarbeitung dieser Listen sehr aufwendig ist und bei der Kostenmodellierung nicht vernachlässigt werden können.



# zerlegen


tausche Elemente innerhalb L so, dass eine Zerlegung L = K + [p] + G entsteht mit

- alle Elemente aus K sind kleiner als Pivotelement p



quicksort(K)

quicksort(G)

# Rückgabe: L



# zerlegen


erzeuge Teillisten K und G aus "L ohne p" mit






# zusammensetzen


# Rückgabe: LSortiertProblemgröße: n Datensätze



Kostenmaß:???

59 Kostenanalyse - Quicksort 21 9 20 45 5 58 40 17 Vergleiche: 8 ^

17 9 20 5 | 45 58 40 21 Vergleiche: 4(+2) + 4 ^ ^

5 9 | 20 17 | 21 40 | 58 46 Vergleiche: 2(+1) + 2 + 2(+1) + 2 ^ ^ ^ ^

5 | 9 | 17 | 20 | 21 | 40 | 46 | 58 Vergleiche:

Quicksort - günstiger Fall

58 5 9 17 20 21 40 45 Vergleiche: 10 ^

45 5 9 17 20 21 40 | 58 Vergleiche: 9 ^

40 5 9 17 20 21 | 45 58 Vergleiche: 8 ^

21 5 9 17 20 | 40 21 45 Vergleiche: 7 ^

...

Quicksort - ungünstiger Fall

Tbest(n) ≈ log2(n)*n

Tworst(n) = n(+2) + (n-1)(+2) + ... + 3(+2) + 2

60 Fachkonzept Kostenfunktion

Die Problemgröße ist eine präzise Beschreibung des Umfangs der zu verarbeitenden Daten, von dem das Zeit- bzw. Speicherverhalten von Lösungalgorithmen maßgeblich beeinflusst wird.

Bei der Beschreibung der Zeitkomplexität mit Hilfe einer Kostenfunktion werden in der Regel eine Reihe von Vereinfachungen vorgenommen sowie Annahmen gemacht. Die Festlegung einer Kostenfunktion kann somit als eine Form der Modellierung angesehen werden, weil hier ein Berechnungsmodell entwickelt werden muss, das den Berechnungsaufwand vereinfachend beschreibt.

Wie bei jeder Modellierung kann das entwickelte Modell mehr oder auch weniger geeignet sein, um die zu beschreibende Wirklichkeit darzustellen. Bei der Modellierung der Zeitkomplexität kommt es darauf an, "richtige" Annahmen über den Aufwand bestimmter, im Algorithmus vorkommender Operationen zu machen. Dass das manchmal schwierig ist, zeigen die Implementierungen des Quicksort-Algorithmus.

Ein Kostenmaß legt fest, in welchem Maße welche Operationen bei der Aufwandsbestimmung berücksichtigt werden. Eine Kostenfunktion ordnet der Problemgröße n die vom Algorithmus benötigten Gesamtkosten T(n) bzgl. des vorgegebenen Kostenmaßes zu.

61 Kostenanalyse - Ergebnisse

Selectionsort:

Tbest(n) = (n-1) + (n-2) + ... + 1 = n*(n-1)/2 = n2/2 - n/2

Tworst(n) = (n-1) + (n-2) + ... + 1 = n2/2 - n/2

Taverage(n) = n2/2 - n/2

Insertionsort:

Tbest(n) = n-1

Tworst(n) = 1 + 2 + ... + (n-1) = n2/2 - n/2

Taverage(n) ≈ c*n2

Quicksort:


Tworst(n) = n(+2) + (n-1)(+2) + ... + 3(+2) + 2 = a*n2 + b*n + c

Taverage(n) ≈ c*n*log2(n)

62 Kostenanalyse

Aufgabe:

Führe eine Kostenanalyse für den Sortieralgorithmus Bubblesort durch.

63 Teil 6

Asymptotisches Wachstumsverhalten

64 Vergleich von Kostenfunktionen

Oft gibt es zu einem Problem mehrere Lösungsalgorithmen mit unterschiedlichen Kostenfunktionen. Diese will man natürlich vergleichen. Bevorzugt werden die Algorithmen, die die geringsten Kosten verursachen. Nur, wie vergleicht man Kostenfunktionen?

Selectionsort:

Tbest(n) = (n-1) + (n-2) + ... + 1

Tworst(n) = (n-1) + (n-2) + ... + 1

Taverage(n) = (n-1) + (n-2) + ... + 1

Quicksort:


Tworst(n) = a*n2 + b*n + c

Taverage(n) ≈ c*n*log2(n)


Algorithmen sind in der Regel so konzipiert, dass sie eine Lösung für beliebige Problemgrößen liefern. Beim Vergleich zugehöriger Kostenfunktionen tritt die Schwierigkeit auf, dass globale Aussagen oft nicht möglich sind. Es kann vorkommen, dass in einem Bereich die eine Kostenfunktion günstiger ist, in einem anderen Bereich die andere Kostenfunktion.

T1(n) = 0.01*n2

T2(n) = 100*n*log10(n)


Oft ist der Problembereich, für den Algorithmen benötigt werden, nicht klar vorgegeben. Man benötigt dann ein Vergleichsverfahren für Kostenfunktionen, das auch mit Situationen wie in der Abbildung klarkommt.

Eine Grundidee des in der Informatik gängigen Vergleichsverfahrens besteht darin, dass kleine Problemgrößen meist von geringerem Interesse sind als große Problemgrößen. Bei kleinen Problemgrößen unterscheiden sich Laufzeiten von Algorithmen z.B. nur im Millisekunden-bereich, während die Unterschiede bei großen Problemgrößen im Sekunden-, Minuten-, Stunden-, Tage- oder gar Jahrebereich liegen können. Verbesserungen von Algorithmen zeigen sich in der Regel insbesondere bei großen Problemgrößen.

Mathematisch präzisiert man diese Idee, indem man das Wachstumsverhalten von Kosten-funktionen vergleicht. Dabei idealisiert man, indem man das Grenzwertverhalten für gegen unendlich strebende Problemgrößen betrachtet.

T1(n) = 0.01*n2

T2(n) = 100*n*log10(n)

T2(n) / T1(n) -> 0


Eine (Kosten-) Funktion f wächst schneller als eine (Kosten-) Funktion g, wenn der Quotient f(n)/g(n) mit wachsendem n gegen unendlich strebt.

Eine (Kosten-) Funktion f wächst langsamer als eine (Kosten-) Funktion g, wenn der Quotient f(n)/g(n) mit wachsendem n gegen 0 strebt.

Eine (Kosten-) Funktion f wächst genauso schnell wie eine (Kosten-) Funktion g, wenn der Quotient f(n)/g(n) mit wachsendem n gegen eine Konstante c strebt.

Selectionsort:

Tselectionsort(n)

= (n-1) + (n-2) + ... + 1

= n*(n-1)/2

= n2/2 - n/2

Quicksort - average:

Tquicksort(n) ≈ c*n*log2(n)

Beispiel:

Tselectionsort(n) wächst genauso schnell wie T(n) = n2.

Tselectionsort(n) / n2 = 1/2 - 1/(2n) -> 1/2

Beispiel:

Tquicksort(n) wächst langsamer als Tselectionsort(n).

Tquicksort(n) / Tselectionsort(n) = c*n*log2(n) / (n*(n-1)/2) = 2*c*log2(n) / (n-1) -> 0

68 Wachstumsprototypen

Prototyp Grundeigenschaft

logarithmisches Wachstum:f(n) = log(n) Wenn n sich verdoppelt, dann wächst f(n) um einen konstanten Betrag.

lineares Wachstum:f(n) = n Wenn n sich verdoppelt, dann verdoppelt sich f(n) ebenfalls.

logarithmisch-lineares Wachstumf(n) = n*log(n)

quadratisches Wachstum:f(n) = n2 Wenn n sich verdoppelt, dann vervierfacht sich f(n).

kubisches Wachstum:f(n) = n3 Wenn n sich verdoppelt, dann verachtfacht sich f(n).

polynomiales Wachstumf(n) = nk Wenn n sich verdoppelt, dann vervielfacht sich f(n) mit 2k.

exponentielles Wachstum:f(n) = bn Wenn n sich um 1 erhöht, dann vervielfacht sich f(n) mit b.

69 Wachstumsprototypen

aus: P. Breuer: Praktische Grenzen der Berechenbarkeit. siehe: http://informatik.bildungrp.de/fileadmin/user_upload/informatik.bildung-rp.de/Weiterbildung/pdf/WB-X-6-PraktischeGrenzen.pdf

70 Wachstumsklassen

Eine (Kosten-) Funktion f wächst nicht schneller als eine (Kosten-) Funktion g, wenn f genauso schnell oder langsamer als g wächst.

Die Klasse aller Funktionen, die nicht schneller wachsen als eine vorgegebene (Kosten-) Funktion f, wird mit O(f) bezeichnet. Man liest das so: "Groß O von f".

Beispiel:

Tselectionsort(n) gehört zur Klasse O(n2).

Tselectionsort(n) gehört zur Klasse der Funktionen, die nicht schneller als quadratisch wachsen.

Beispiel:

Tquicksort(n) gehört zur Klasse O(n*log2(n)).

Tquicksort(n) gehört zur Klasse der Funktionen, die nicht schneller als logarithmisch-linear wachsen.

71 Teil 7

Die Komplexität des Sortierproblems

72 Komplexität von Problemen

Der Algorithmus selectionsort hat - im günstigsten wie auch ungünstigsten Fall - eine quadratische Zeitkomplexität. Die zur Beschreibung des Laufzeitverhalten gewählte Kostenfunktion gehört zur Klasse O(n2) der asymptotisch quadratisch wachsenden Funktionen.

Der Algorithmus quicksort hat - im günstigsten (und auch durchschnittlichen) Fall - eine logischmisch-lineare Zeitkomplexität. Die zur Beschreibung des Laufzeitverhalten gewählte Kostenfunktion gehört hier zur Klasse O(n*log2(n)).

Es gibt eine Vielzahl an weiteren Sortieralgorithmen. Die "schnelleren" dieser Algorithmen haben alle eine logischmisch-lineare Zeitkomplexität. Es stellt sich die Frage, ob es nicht noch schnelleren Sortieralgorithmen gibt - z.B. solche mit einer linearen Zeitkomplexität - und, ob es auch eine Art untere Schranke für die Zeitkomplexität gibt, die von keinem Sortieralgorithmus unterschritten werden kann. Diese Fragen betreffen die Komplexität des Sortierproblems.

Zur Beschreibung der Komplexität eines Problems muss man folglich Aussagen über alle möglichen Algorithmen zur Lösung des Problems machen, indem man zeigt, dass ein bestimmter Ressourcenverbrauch bei all diesen Algorithmen erforderlich ist und von keinem Algorithmus unterschritten werden kann. Die Schwierigkeit beim Nachweis solcher Aussagen besteht darin, dass man den Nachweis über alle denkbaren - d.h. bis jetzt gefundenen und auch noch nicht bekannten - Algorithmen führen muss.

Die (Zeit-)Komplexität eines Problems beschreibt man durch Komplexitätsklassen, die untere Schranken für die Komplexität der Algorithmen, die das Problem lösen, bilden.

73 Problem - Sortieren

{abcd,abdc,acbd,acdb,adbc,adcb,bacd,badc,bcad,bcda,bdac,bdca, cabd,cadb,cbad,cbda,cdab,cdba,dabc,dacb,dbac,dbca,dcab,dcba}[a, b, c, d]a < b?T: {abcd,abdc,acbd,acdb,adbc,adcb,cabd,cadb,cdab,dabc,dacb,dcab} [a, b, c, d] a < c? T: {abcd,abdc,acbd,acdb,adbc,adcb,dabc,dacb} [a, b, c, d] a < d? T: {abcd,abdc,acbd,acdb,adbc,adcb} [a, b, c, d] b < c? ...F: ...

| 25 32 56 27 ^

25 | 32 56 27 ^

25 27 | 56 32 ^

25 27 32 | 56Selectionsort

Gegeben ist eine Liste L = [a, b, c, d] mit 4 Elementen (z.B. Zahlen) und eine Vergleichsoperation, über die die Listenelemente sortiert werden sollen.

Bei einer Liste mit 4 Elementen gibt es 24 verschiedene Möglichkeiten, wie die Listenelemente nach der Sortierung angeordnet sein können:

{abcd,abdc,acbd,acdb,adbc,adcb,bacd,badc,bcad,bcda,bdac,bdca,cabd,cadb,cbad,cbda,cdab,cdba,dabc,dacb,dbac,dbca,dcab,dcba}

mögliche Ausführungen von Selectionsort als Baumdiagramm

74 Problem - Sortieren{abcd,abdc,acbd,acdb,adbc,adcb,bacd,badc,bcad,bcda,bdac,bdca, cabd,cadb,cbad,cbda,cdab,cdba,dabc,dacb,dbac,dbca,dcab,dcba}[a, b, c, d]a < b?T: {abcd,abdc,acbd,acdb,adbc,adcb,cabd,cadb,cdab,dabc,dacb,dcab} [a, b, c, d] a < c? T: {abcd,abdc,acbd,acdb,adbc,adcb,dabc,dacb} [a, b, c, d] a < d? T: {abcd,abdc,acbd,acdb,adbc,adcb} [a, b, c, d] b < c? T: {abcd,abdc,adbc} [a, b, c, d] b < d? T: {abcd,abdc} [a, b, c, d] c < d? T: {abcd} [a, b, c, d] F: {abdc} [a, b, d, c] F: {adbc} [a, d, c, b] c < b? T: {} [a, d, c, b] F: {adbc} [a, d, b, c] F: {acbd,acdb,adcb}

| 25 32 56 27 ^

25 | 32 56 27 ^

25 27 | 56 32 ^

25 27 32 | 56Selectionsort

75 Problem - Sortieren ... F: {dabc,dacb} [d, b, c, a] b < c? T: {dabc} [d, b, c, a] b < a? T: {} c < a? T: {} F: {} F: {dabc} [d, a, c, b] c < b? T: {} F: {dabc} [d, a, b, c] F: {dacb} [d, b, c, a] c < a? T: {} b < a? T: {} F: {} F: {dacb} [d, a, c, b] c < b? T: {dacb} [d, a, c, b] F: {} ...

| 25 32 56 27 ^

25 | 32 56 27 ^

25 27 | 56 32 ^

25 27 32 | 56

Selectionsort

Wenn ein Sortieralgorithmus die Sortierung nur über Vergleiche von Listenelementen erzeugt, dann lässt sich die Ausführung des Algorithmus bei beliebigen Ausgangslisten über einen Entscheidungsbaum darstellen. Die "Tiefe des Baumes" (erkennbar an den Einrückungen) zeigt dabei, wie viele Entscheidungen im ungünstigsten Fall auszuführen sind. Im Fall des Algorithmus selectionsort beträgt die Tiefe des Baumes 6.

Am Entscheidungsbaum zeigt sich also, wie gut oder schlecht ein Algorithmus ist. Wenn die Tiefe des Entscheidungsbaums groß bzw. klein ist, dann ist das worst-case-Verhalten des Algorithmus schlecht bzw. gut.

76

{abcd,abdc,acbd,acdb,adbc,adcb,bacd,badc,bcad,bcda,bdac,bdca, cabd,cadb,cbad,cbda,cdab,cdba,dabc,dacb,dbac,dbca,dcab,dcba}a < b?T: {abcd,abdc,acbd,acdb,adbc,adcb,cabd,cadb,cdab,dabc,dacb,dcab} c < d? T: {abcd,acbd,acdb,cabd,cadb,cdab} a < c? T: {abcd,acbd,acdb} b < c? T: {abcd} F: {acbd,acdb} b < d? T: {acbd} F: {acdb} F: {cabd,cadb,cdab} b < d? T: {cabd} F: {cadb,cdab} a < d? T: {cadb} F: {cdab} F: {abdc,adbc,adcb,dabc,dacb,dcab} a < d? T: {abdc,adbc,adcb} b < d? T: {abdc} F: {adbc,adcb} b < c? T: {abdc} F: {adcb} F: ...

Problem - Sortieren

Am Entscheidungsbaum kann auch aufgezeigt werden, wie gut das worst-case-Verhalten eines Sortieralgorithmus überhaupt sein kann: Bei 24 möglichen Anordnungen benötigt man mindestens einen Entscheidungsbaum der Tiefe 5, um alle Anordnungen durch Entscheidungen erzeugen zu können. Das sieht man so ein: Durch 1 Entscheidung erhält man eine Aufteilung der Anordnungen in 2 Teilmengen, durch 2, 3, 4, 5, ... Entscheidungen in 4, 8, 16, 32, ... Teilmengen. Um alle 24 Anordnungen mittels Entscheidungen auseinander zu bekommen, sind daher mindestens 5 Entscheidungen im Entscheidungsbaum erforderlich. Das Baumdiagramm zeigt, wie man mit 5 geschachtelten Entscheidungen tatsächlich alle Anordnungen erhält.

77 Komplexität des Sortierproblems

Die Betrachtungen oben verdeutlichen, dass es zu jedem vergleichsbasierten Sortieralgorithmus (für jede Listenlänge) einen zugehörigen Entscheidungsbaum gibt. Die Tiefe des Entscheidungsbaum (in Abhängigkeit der Listenlänge) legt das worst-case-Verhalten des Algorithmus fest.

Um eine untere Schranke für das worst-case-Verhalten von Sortieralgorithmen zu gewinnen, schauen wir uns die Tiefe von "optimalen Entscheidungsbäumen" (in Abhängigkeit der Listenlänge) an.

Um k verschiedene Anordnungen nur mit Entscheidungen zu erzeugen, benötigt man einem Entscheidungsbaum mit einer Tiefe der Größenordnung log2(k). Wenn k = 2m eine Zweierpotenz ist, dann reicht die Tiefe m. Ansonsten benötigt man als Tiefe den Exponenten von der von k aus nächst größeren Zweierpotenz.

Wenn beispielsweise k = 24, dann benötigt man eine Tiefe log2(32), also die Tiefe 5.

Um eine Aussage über Listen beliebiger Länge treffen zu können, muss man wissen, wie viele Anordnungen jeweils möglich sind: Bei n Listenelementen gibt es n! = 1*2*...*n verschiedene mögliche Anordnungen der Listenelemente.

Fasst man beide Ergebnisse zusammen, so erhält man folgende Aussage: Um eine Liste mit n Elementen zu sortieren, benötigt man einen Entscheidungsbaum, der eine Tiefe der Größenordnung log2(n!) hat.

78 Komplexität des Sortierproblems

Jeder vergleichsbasierte Sortieralgorithmus hat demnach ein worst-case-Verhalten, das durch die Funktion K(n) = log2(n!) abgeschätzt werden kann.

Mathematiker haben gezeigt, dass n! ≥ (n/2)(n/2) gilt.

Mit dieser Abschätzung erhält man log2(n!) ≥ (n/2)*log2(n/2).

Hieraus ergibt sich, dass jeder vergleichsbasierte Sortieralgorithmus ein worst-case-Verhalten hat, das nach unten durch die Funktion K(n) = (n/2)*log2(n/2) abgeschätzt werden kann. Betrachtet man - wie üblich - nur das asymptotische Verhalten, so zeigt dies, dass das worst-case-Verhalten eines beliebigen Sortieralgorithmus von der Ordnung n*log2(n) sein muss.Ergebnis - Komplexität des Sortierproblems:

Die Komplexität des Sortierproblems ist von der Ordnung n*log2(n) - sofern ein vergleichsbasiertes Berechnungsmodell zu Grunde liegt.

Date post:	25-Jan-2016
Category:	Documents
Upload:	mada
View:	20 times
Download:	1 times

Sortierverfahren

Documents