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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Datenabstraktion, Abstrakte Daten-Typen
Praktische Informatik 1, WS 2004/05, Folien Sortieren−1, (14. Januar2005) Seite 33
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Die Barrieren (Schnittstellen) erlauben sauberes zverlassiges Program-
mieren Die Effizienz kann durch Schnittstellen etwas verschlechtert
werden.