+ All Categories
Home > Documents > Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von...

Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von...

Date post: 25-Jul-2018
Category:
Upload: hamien
View: 224 times
Download: 0 times
Share this document with a friend
51
Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨ uller“, “Darmstadt“, 456) (“Meier“, “Wiesbaden“,123 ) (“Schmitt“, “Frankfurt“, 789) (“Adam“, “Hamburg“, 999) Aufsteigend nach Namen sortiert: (“Adam“, “Hamburg“, 999) (“Meier“, “Wiesbaden“, 456) (“M¨ uller“, “Darmstadt“, 123) (“Schmitt“, “Frankfurt“, 789) P raktische Informatik 1, WS 2004/05, F olien Sortieren-1, (14. Januar2005) Seite 1
Transcript
Page 1: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Sortieren

Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge

Beispiel

(“Muller“, “Darmstadt“, 456)(“Meier“, “Wiesbaden“,123 )(“Schmitt“, “Frankfurt“, 789)(“Adam“, “Hamburg“, 999)

Aufsteigend nach Namen sortiert:

(“Adam“, “Hamburg“, 999)(“Meier“, “Wiesbaden“, 456)(“Muller“, “Darmstadt“, 123)(“Schmitt“, “Frankfurt“, 789)

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 1

Page 2: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Sortieren, Beispiel (2)

Aufsteigend nach Kundennummer sortiert:

(“Muller“, “Darmstadt“, 123)(“Meier“, “Wiesbaden“, 456)(“Schmitt“, “Frankfurt“, 789)(“Adam“, “Hamburg“, 999)

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 2

Page 3: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Sortieren

Eingabe: Liste von ObjektenVergleichsoperator auf den Objekten

Ausgabe: Liste der Objekte mit i.a. anderer Reihenfolge [a1, . . . an]so dass i ≤ j ⇒ ai ≤ aj

Annahme: Ordnung ist transitiv, reflexiv, total,aber nicht notwendig antisymmetrisch

total :⇔ es gilt a ≤ b oder b ≤ a.

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 3

Page 4: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Sortiermethoden

Annahme im Folgenden: Liste von Zahlen.

Wir betrachten:

Insert-Sort Sortieren durch EinfugenBubble-Sort Sortieren durch binares VertauschenMerge-Sort Sortieren durch rekursives MischenQuick-Sort Sortieren durch rekursive Zerlegung und Vergleichen

Es gibt noch weitere Sortierverfahren

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 4

Page 5: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Sortieren

• Sortierprogramme in Haskell fur ListenDemonstration der PrinzipienAbschatzung der Komplexitat

• Sortierprogramme in Python fur ArrayPrinzipien der destruktiven AbanderungIn-place-Algorithmen

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 5

Page 6: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Sortieren durch Einfugen (Insert-Sort)

Idee: geordnetes Einfugen der Elemente in die bereits sortierte Liste

Sortiere: 5,3,99,1,2,7

sortierte Liste restliche Elemente5 3,99,1,2,73,5 99,1,2,73,5, 99 1,2,71,3,5, 99 2,71,2,3,5, 99 71,2,3,5, 7, 99

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 6

Page 7: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Insert-Sort: Haskell-Programm

Sortieren durch Einfugen:

sorteinfuegen xs = sorteinfuegenr xs []

sorteinfuegenr: unsortierter Rest, sortierter Anteil

sorteinfuegenr [] ys = ys

sorteinfuegenr (x:xs) [] = sorteinfuegenr xs [x]

sorteinfuegenr (x:xs) ys = sorteinfuegenr xs (sorteinfuegenr1 x ys)

sorteinfuegenr1 x [] = [x]

sorteinfuegenr1 x (y:ys) =

if x <= y then x:y:ys

else y : (sorteinfuegenr1 x ys)

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 7

Page 8: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Sortieren mit Blasensort

(Bubble-Sort)

Vertauschung von benachbarten Elementen;

falls notwendig: Mehrfaches Durcharbeiten der Liste

5 3 99 1 2 75 3 99 1 2 75 3 99 1 2 75 3 1 99 2 75 1 3 99 2 71 5 3 99 2 71 5 3 99 2 71 5 3 99 2 71 5 3 2 99 71 5 2 3 99 71 2 5 3 99 7. . .

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 8

Page 9: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Bubble-Sort: Haskell-Programm

Sortieren durch Vertauschen von benachbarten Feldern

bubblesort [] = []

bubblesort [x] = [x]

bubblesort xs =

let y:resty = bubblesort1 xs

in y: (bubblesort resty)

bubblesort1 [x] = [x]

bubblesort1 (x:rest) =

let (y:resty) = bubblesort1 rest

in if x > y then y:x: resty

else (x: y:resty)

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 9

Page 10: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Bubble-Sort mit Optimierung:

Haskell-Programm

bubblesorto [] = []

bubblesorto [x] = [x]

bubblesorto xs =

let (aenderung,y:resty) = bubblesorto1 xs

in if aenderung then y: (bubblesorto resty)

else xs

bubblesorto1 [x] = (False,[x])

bubblesorto1 (x:rest) =

let (aenderung, y:resty) = bubblesorto1 rest

in if x > y then (True,y:x: resty)

else (aenderung,x: y:resty)

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 10

Page 11: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Quicksort: Rekursives Zerlegen

Idee

Pivot = erstes Element der Liste:

• Zerlege Liste in Teillisten von Elemente, die bzgl Pivot:

kleinere, grossere und gleiche Elemente enthalten

• Sortiere diese rekursiv (Quicksort)

• Fuge sie zusammen.

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 11

Page 12: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Quicksort: Beispiel

Sortiere: 5,3,99,1,2,7

Pivot 5kleinere/großere Elte 3,1,2 99,7Pivots 1 | 99kleinere/großere Elte 2,3 | 7 -Pivots 2 |kleinere/großere Elte 3 |Zusammensetzen: 1,2,3,5,7,99

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 12

Page 13: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Sortieren mit Quicksort: Haskell-Programm

quicks [] = []

quicks [x] = [x]

quicks [x,y] = if x <= y then [x,y] else [y,x]

quicks (x:xs) = let (llt,lge) = splitlist x xs

in (quicks llt) ++ (x: (quicks lge))

splitlist x y = splitlistr x y [] []

splitlistr x [] llt lge = (llt,lge)

splitlistr x (y:ys) llt lge =

if y < x

then splitlistr x ys (y: llt) lge

else splitlistr x ys llt (y:lge)

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 13

Page 14: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Mergesort: Sortieren durch Mischen

Rekursives Verfahren: Zerlege Liste in erste und zweite Halftesortiere beide rekursivzusammenmischen

Sortiere: 5,3,99,1,2,7

Zerlegen 5,3,99 | 1,2,7Zerlegen 5 3,99 | 1 2,7

. . . | . . .. . . 5 3,99 | 1 2,7Merge 3,5,99 | 1,2,7Merge 1,2,3,5,7,99

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 14

Page 15: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Sortieren mittels Mischen: Haskell-Programm

mischsort xs = mergesort (length xs) xs

mergesort _ [] = []

mergesort _ [x] = [x]

mergesort _ [x,y] = if x <= y then [x,y] else [y,x]

mergesort len xs =

let lenh = len ‘div‘ 2

in mische (mergesort lenh (take lenh xs))

(mergesort (len -lenh) (drop lenh xs))

mische [] ys = ys

mische xs [] = xs

mische (x:xs) (y:ys) =

if x <= y then x: (mische xs (y:ys))

else y: (mische (x:xs) ys)

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 15

Page 16: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Sortieren: Mindestanzahl der Vergleiche

Satz Sortieren einer Liste von n Zahlen durch Vergleichsoperationen

benotigt im schlechtesten Fall mindestens n ∗ log2(n) Vergleiche.

Argumentation:

Ein Entscheidungsbaum-Programm zur Lange n sortiert eine Eingabe-

liste [a1, . . . , an] der Lange n folgendermaßen:

An den Verzweigungen wird die Frage gestellt: ist ai > aj? fur be-

stimmte (feste) Indizes i, j,

die Ausgabe am Ende ist die sortierte Permutation der Eingabeliste.

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 16

Page 17: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Sortieren: Mindestanzahl der Vergleiche

Es gibt immer eine Eingabeliste, so dass n ∗ log2(n) Vergleiche zum

Sortieren notig sind

Begrundung:

Der Entscheidungsbaum hat n! Blatter, da jede Eingabereihenfolge

moglich ist.

Die Tiefe d des Baumes > log2(n!).

Offenbar: n! ≥ 1 ∗ . . . ∗ 1︸ ︷︷ ︸n/2

∗n/2 ∗ . . . ∗ n/2︸ ︷︷ ︸n/2

= (n/2)(n/2).

log2(n!) > log((n/2)(n/2)) = 0.5 ∗ n ∗ llog(n/2) = 0.5 ∗ n ∗ (log2(n)− 1).

D.h. Ω(n ∗ llog2(n)).

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 17

Page 18: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Sortieren: Mindestanzahl der Vergleiche(3)

Abschatzung kann leicht verbessert werden

mittels der Stirlingformel fur n!.

Aber: Man konnte noch nicht allgemein nachweisen,

dass dies auch eine untere Schranke ist,

wenn man alle Algorithmen zulasst.

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 18

Page 19: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Eigenschaften der Sortierverfahren

• Zeitbedarf im schlechtesten Fall / besten Fall / im Mittel• Stabilitat

Ein Sortierverfahren ist stabil,

wenn die Reihenfolge von Elementen mit gleichem Sortierschlussel

erhalten bleibt.

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 19

Page 20: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Eigenschaften des Insert-Sort

Gut fur kleinere Listen, oder fast sortierte Listen

im schlechtesten Fall: O(n2):

Fur Listen der Lange n hochstens: 1 + 2 + . . . + (n− 1) Vergleiche

im besten Fall: O(n) fur vorsortierte Listen.

Die Haskell-Implementierung ist stabil.

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 20

Page 21: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Insert-Sort: Variante

Folgende Variante des Insert-sort ist stabil und hat Komplexitat O(n)

fur vorsortierte Listen:

sorteinfuegeno xs = reverse (sorteinfuegenor xs [])

sorteinfuegenor [] ys = ys

sorteinfuegenor (x:xs) [] = sorteinfuegenor xs [x]

sorteinfuegenor (x:xs) ys = sorteinfuegenor xs (sorteinfuegenor1 x ys)

sorteinfuegenor1 x [] = [x]

sorteinfuegenor1 x (y:ys) =

if x >= y then x:y:ys

else y : (sorteinfuegenor1 x ys)

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 21

Page 22: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Eigenschaften des Bubble-Sort

Gut: wenn Elemente schon in der Nahe ihres endgultigen Platzes sind.

im schlechtesten Fall: (n− 1) + (n− 2) + . . . + 1 = O(n2)

im besten Fall: O(n), wenn Liste schon sortiert

Stabil, wenn gleiche Elemente nicht vertauscht werden.

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 22

Page 23: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Eigenschaften des Quicksort

im schlechtesten Fall: O(n2), wenn Liste bereits sortiert

im besten Fall: O(n ∗ log(n))

Im Mittel: O(n ∗ log(n))

Gut: wenn Listen groß und Werte zufallig verteilt.

Beim Experimentieren in Haskell mit zufallig erzeugten Listen ist es

das beste Verfahren

Haskell-Implementierung ist stabil,

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 23

Page 24: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Eigenschaften des Mischsort

im schlechtesten Fall: O(n ∗ log(n)).

Im besten Fall: auch O(n ∗ log(n)).

Gut: Wenn keine Komplexitats-Ausrutscher vorkommen sollen

Experiment: in Haskell ist es nur dann besser als Quicksort,

wenn Teile der Listen bereits sortiert sind.

Stabil, wenn der Merge Stabilitat beachtet:

D.h. wenn gleiche Elemente aus der linken Liste vor denen aus der

rechten Liste einsortiert werden.

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 24

Page 25: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Komplexitat des Mischsort

Genauere Begrundung

Behauptung: Mischsort hat einen Zeitbedarf von O(n ∗ log(n))

Abschatzung von redms:

redms(n) = c + redmische(n) + 2 ∗ redms(n/2)= c + n + 2 ∗ redms(n/2)≤ c + n + 2 ∗ (c + n/2) + 4 ∗ redms(n/4)= (c + n) + (2c + n) + (4c + n) + (8c + n) + . . .

Tiefe der Rekursionen: ≈ log2(n)

c ∗ n + n ∗ log2(n) + 2 ∗ log2(n).

d.h. der Mischsort ist O(n ∗ log(n)).

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 25

Page 26: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Sortierprogramme in imperativen

Programmiersprachen, Speicherverwaltung

Zusatzlicher Aspekt: effiziente Speicherverwaltung

Falls Sortierung innerhalb des Eingabe-Arrays: In-Place- Verfahren.

Insertion-Sort, Bubble-Sort, Quick-Sort: In-Place-Verfahren

Merge-Sort: Es gibt ein effizientes In-Place-Merge-Verfahren,

der Algorithmus ist nicht so offensichtlich zu finden.

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 26

Page 27: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Bubblesort in Python, in-place

def Bubblesort(soArray):

laenge = len(soArray)

for i in range(0,laenge-1):

aenderung = 0

for j in range(0,laenge-1-i):

if soArray[j] > soArray[j+1]:

vertausche(soArray,j, j+1)

aenderung = 1

if aenderung == 0:

break

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 27

Page 28: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Insertsort in Python, in-place

def Insertsort(soArray):

laenge = len(soArray)

for i in range(1,laenge):

for j in range(i,0,-1):

if soArray[j] < soArray[j-1]:

vertausche(soArray,j, j-1)

else: break

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 28

Page 29: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Quicksort in Python, in-place

def Quicksort(soArray):

return Quicksortr(soArray,0,len(soArray)-1)

def Quicksortr(soArray,iLo,iHi):

if (iHi-iLo == 1): ##Optimierung

if_groesser_then_tausch(soArray,iLo,iHi);

return soArray;

Lo = iLo;

Hi = iHi;

Mid = (Lo + Hi) / 2;

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 29

Page 30: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Quicksort in Python, in-place, (2)

while (Lo <= Hi):

while (isKleiner(soArray,Lo,Mid)):

Lo = Lo+1

while (isGroesser(soArray,Hi,Mid)):

Hi = Hi -1;

if (Lo <= Hi):

if (Mid == Hi): Mid = Lo;

elif (Mid == Lo): Mid = Hi;

if (Lo != Hi):

vertausche(soArray,Lo, Hi);

Lo = Lo +1;

Hi = Hi-1;

if (Hi > iLo): Quicksortr(soArray,iLo, Hi);

if (Lo < iHi): Quicksortr(soArray,Lo, iHi);

return soArray

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 30

Page 31: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Quicksort in Python, in-place, (3)

def isGroesser(soArray,x,y): return (soArray[x] > soArray[y])

def isKleiner(soArray,x,y): return (soArray[x] < soArray[y])

def vertausche(soArray,ind1, ind2):

x = soArray[ind1];

soArray[ind1] = soArray[ind2];

soArray[ind2] = x;

def if_groesser_then_tausch(soArray,ind1,ind2):

if isGroesser(soArray,ind1,ind2):

vertausche(soArray,ind1, ind2);

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 31

Page 32: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Eigenschaften der in-place Sortierverfahren

Imperative in-place Sortierverfahren:Isert-Sort ist stabilBubble-Sort ist stabilimperativer Quicksort ist nicht stabileffizienter Merge-Sort ist stabil

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 32

Page 33: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Datenabstraktion, Abstrakte Daten-Typen

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 33

Page 34: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Datenabstraktion

Strukturierungsmethode fur Programme und Implementierungen

unabhangig von einer Programmiersprache verwendbar

Prinzip: Trennung von

• interner Implementierung der Daten, interner Zugriffsfunktionen• externem Zugriff

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 34

Page 35: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Was man vermeiden sollte

Gilt auch fur Module

• Durchgriff auf die Implementerung

Schein-Argumente: Effizienz, Bequemlichkeit

kann langfristig zu Wartungs-Problemen fuhren,

z.B. bei Anderung der internen Implementierung des Moduls

• Verwenden des durch die Implementierung bedingten, aber nicht

garantierten, Verhaltens

Z.B. bei Implementierung von Mengen: Reihenfolge der Elemente

nicht ausnutzen

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 35

Page 36: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Datenabstraktion

Funktionen auf einem abstrakten Datentyp:

• Konstruktoren bzw. Eingabe der Objekte• Fallunterscheidung nach den Konstruktoren und Selektoren;

bzw. Frage nach der logischen Struktur der Datenobjekte,

bzw. Ausgabe der Objekte,• interne Service-Funktionen. Z.B. Operatoren auf Objekten,

Gleichheitstests, usw.• externe Service-Funktionen. Z.B. die Funktion map auf Listen.• Datenkonversionen

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 36

Page 37: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Datenabstraktion

Wesentliche Aspekte, analog zu Modulen, sind:

• Die Daten sind uber klar definierte Zugriffsfunktionen verfugbar

• Die Algorithmen verwenden nur diese Zugriffsfunktionen

• Die Daten haben eine Semantik, die von der Implementierung re-spektiert wird.

• Die Implementierung der Daten und Zugriffe ist nicht sichtbar(Kapselung, Information hiding).

• Schnittstellen

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 37

Page 38: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Beispiel: Listen

Konstruktoren: cons, nilSelektoren: head, tail

Beispiel fur Gleichheitsaxiome:

head(cons s t) = stail(cons s t) = tnil 6= (cons s t)

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 38

Page 39: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Haskell-Listen

Haskell-Listen erfullen diese Axiome:

Definitionen:

head (x:y) = x

tail (x:y) = y

cons x y = x:y

nil = []

Nachrechnen ergibt:

[] 6= s : t.

head (cons s t ) reduziert zu s.

tail (cons s t) reduziert zu t.

head nil fuhrt zu einem Fehler (d.h. undefiniert).

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 39

Page 40: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Datentyp”naturliche Zahl“

Konstruktoren Null, S

S(S(S(Null))) der Zahl: 3.

alle arithmetischen Operatoren sind implementierbar

Zahlen in Programmiersprachen: binare Strings

Gleiche Funktionalitat, aber effizienter

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 40

Page 41: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Datentyp”ganze Zahlen“

Benutzt Datentyp der naturlichen Zahlen

Darstellung als Paar (s, n) Vorzeichen positive Zahl

Diese Darstellung hat eine Doppeldeutigkeit

(+,0) oder (−,0) sind zwei Darstellungen der 0.

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 41

Page 42: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Der Datentyp Rationale Zahlen

• Funktionen zum Erzeugen und Anzeigen• arithmetische Operationen: ∗, /,+,−• Vergleiche: <,≤• Konversionen Int→ Rational

Axiom: beim Drucken erscheint stets die gekurzte Darstellung

Verschiedene interne Darstellungen sind moglich:

man hat freie Wahl, ob und wann (intern) gekurzt wird.

Datekonversionen:

Integer → Rational

Rational → Integer

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 42

Page 43: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Gleitkommazahlen

• Funktionen: Erzeugen, Anzeigen,• mathematische Operationen: ∗, /,+,−• Vergleiche . . .

Erfullen nicht die mathematischen Axiome fur reelle Zahlen

sinnvoll ware: Axiome, die Naherung an reelle Zahlen beschreiben.

Standardisierungen und Normierungen:

auf der Basis der internen Darstellung

fur Rundungen und Fehlermeldungen bei Ausnahmen

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 43

Page 44: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Der abstrakte Datentyp “Menge“

Endliche Mengen mit Elementen von gleichem Typ

folgende Funktionalitat ist sinnvoll:

• Erzeugen von Mengen, gegeben endliche Aufzahlung der Elemente• Test auf Enthaltensein eines Elementes in einer Menge• Drucken einer Menge• Kardinalitat einer Menge• Bildung von Schnitt, Vereinigung, Differenz, Potenzmenge• Test auf Gleichheit von Mengen

Notwendig: Gleichheitstest fur Elemente.

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 44

Page 45: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Datentyp “Menge“: Beispiel

Eingabe: (1,2), (2,4)

= (1,2) falls rationale Zahlen gemeint sind.

Aber:

= (1,2), (2,4), falls Paare komplexe Zahlen darstellen.

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 45

Page 46: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Der abstrakte Datentyp “Multimenge“

Endliche Multimengen mit Elementen von gleichem Typ,

wobei Elemente mehrfach vorkommen durfen.

Multimengen sind wie Listen, bei denen man von der Reihenfolge der

Elemente absieht.

Notwendige Funktionalitaten analog wie bei Mengen.

Beispielsweise gilt fur Multimengen

1,1,1,2,2 ∩ 1,1,2,2,2 = 1,1,2,2 und

1,1,1,2,2 ∪ 1,1,2,2,2 = 1,1,1,1,1,2,2,2,2,2.Implementierung von Multimengen: auf der Basis von Listen.

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 46

Page 47: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Datentyp “Multi-Menge“: Beispiel

Notwendig auch fur Multimengen: Gleichheitstest fur Elemente.

Beispiel-Eingabe: (1,2), (2,4)

= (1,2), (1,2) falls Paare rationale Zahlen darstellen.

Aber:

= (1,2), (2,4), mit (1,2) 6= (2,4) falls Paare komplexe Zahlen dar-

stellen.

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 47

Page 48: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Axiome fur “Multimenge“

Konstruktoren und Funktionen:

cons, null, anzahl, einfuegen, ....

Typ ware (Multimenge a)

Zwei exemplarische Axiome:

anzahl null = 0

∀s :: a, t :: Multimenge a : anzahl(einfuegen s t) = (anzahl t) + 1

Implementierung mit anzahl = length, einfuegen = cons

Diese ist korrekt, denn:

anzahl null → length [] → 0

anzahl (einfuegen s t) → length (cons s t) → (length t) + 1.

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 48

Page 49: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Mengen: Implementierung

endliche Mengen:

Implementierungsmoglichkeiten: Listen von Elementensortierte Listen von ElementenSuch-BaumeMultimengen von Elementen

Aber: Datentyp “unendliche Liste“ oder “unendliche Menge“nur eingeschrankt implementierbar

problematisch: nicht alle unendlichen Mengen sind endlich darstellbar.Gleichheitstest von unendlichen Mengen

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 49

Page 50: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Abstraktionsbarrieren

Abstraktionsbarrieren fur die Beispiele Mengen / Multimengen / Listensind:

Mengen: Schnitt, ...

Multimengen: Schnitt, Vereinigung, Gleichheit, ...

Schnittstellenfunktionen

Listen. append, element, ...

Schnittstellenfunktionen

Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 50

Page 51: Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge · Sortieren Ziel: Bringe Folge von Objekten in eine bestimmte Reihenfolge Beispiel (“M¨uller“, “Darmstadt“,

Die Barrieren (Schnittstellen) erlauben sauberes zverlassiges Program-

mieren Die Effizienz kann durch Schnittstellen etwas verschlechtert

werden.


Recommended