Jonietz
Sort
iere
n u
nd
S
uch
en
1
Sortieren und Suchen
IFB 2002
Daniel Jonietz
Jonietz
Sort
iere
n u
nd
S
uch
en
2Überblick
Teil 1: Elementare Sortieralgorithmen
Teil 2: Quicksort
Teil 2: Effizienz von Sortierverfahren
Teil 3: Suchalgorithmen
Jonietz
Sort
iere
n u
nd
S
uch
en
3Teil 1
Elementare Sortieralgorithmen
Jonietz
Sort
iere
n u
nd
S
uch
en
4Motivation
Eine Reihe von Werten liegt unsortiert vor. Ziel: Die Werte sollen (aufsteigend) sortiert werden.
Jonietz
Sort
iere
n u
nd
S
uch
en
5Datenmodell
Die Werte liegen in einer Reihung vor:
...
0 1 2 user_max
tIndex
tWert
tZahlen
...
prog_max
Jonietz
Sort
iere
n u
nd
S
uch
en
6Daten und Typen
const prog_max = 1000;
type tWert = integer; tIndex = integer; tZahlen = array [0..prog_max] of tWert;
var zahlen: tZahlen; user_max: tWert = 14;
Insgesamt höchstens 1000 Werte
Verwenden davon nur 15
Jonietz
Sort
iere
n u
nd
S
uch
en
7Sortieren durch Auswahl
Idee:Suche das kleinste Element und lege es beiseite. Dann wähle aus den übrigen wiederum das kleinste Element und lege es daneben.
Sortieren von Münzen
Jonietz
Sort
iere
n u
nd
S
uch
en
8Auswahl-Sortieren V1
5 7 2 8 3 1 4
1
1 2
1 2 3
1 42 3
1 52 3 4
2 731 4 5
2 831 4 5 7
5 7 2 8 3 4
5 7 8 3 4
5 7 8 4
5 7 8
7 8
8
Jonietz
Sort
iere
n u
nd
S
uch
en
9Auswahl-Sortieren V2
5 7 2 8 3 1 4
1
2
3
4
5
7
8
57 2 8 3 4
57 8 3 4
578 4
57 8
7 8
8
1
1
1
1
1
1
2
2
2
2
2
3
3
3
3
4
4
4 7
5
5 „in situ“
Jonietz
Sort
iere
n u
nd
S
uch
en
10Algorithmus
minsort
Für i von 0 bis Anzahl-1
Suche das Minimum aus den restlichen Elementen
Tausche das Minimum mit dem Wert an der Position i
Brauchen Möglichkeit zur Bestimmung des Minimums aus einem Bereich der Zahlen
Jonietz
Sort
iere
n u
nd
S
uch
en
11Minimum und Maximum
Aufruf findet statt in procedure TForm1.suche_minimum(Sender: TObject); procedure TForm1.suche_maximum(Sender: TObject);
Jonietz
Sort
iere
n u
nd
S
uch
en
12Aufgabe
Implementieren Sie die Funktionen
function min(anfang, ende: tIndex): tIndex;function max(anfang, ende: tIndex): tIndex;
die den Index eines minimalen bzw. maximalen Elementes aus dem Bereich anfang ... ende liefert.
Implementieren Sie damit die Prozedur
procedure minsort;
Wer möchte, auch procedure maxsort; Idee?
Jonietz
Sort
iere
n u
nd
S
uch
en
13Lösungsvorschlag
function min(anfang, ende: tIndex): tIndex;
var i, min_pos: tIndex;
min_wert: tWert;
begin
min_pos:= anfang;
min_wert:= zahlen[min_pos];
for i:= anfang+1 to ende do
if (zahlen[i] < min_wert) then
begin
min_pos:= i;
min_wert:= zahlen[min_pos];
end;
min:= min_pos;
end;
Kandidat
besserer Kandidat
Jonietz
Sort
iere
n u
nd
S
uch
en
14Lösungsvorschlag
function max(anfang, ende: tIndex): tIndex;
var i, max_pos: tIndex;
max_wert: tWert;
begin
max_pos:= anfang;
max_wert:= zahlen[max_pos];
for i:= anfang+1 to ende do
if (zahlen[i] > max_wert) then
begin
max_pos:= i;
max_wert:= zahlen[max_pos];
end;
max:= max_pos;
end;
Kandidat
besserer Kandidat
Jonietz
Sort
iere
n u
nd
S
uch
en
15Lösungsvorschlag
procedure minsort;
var
i, merke: tIndex;
begin
for i:= 0 to user_max-1 do
begin
merke:= min(i, user_max);
tausche(zahlen[merke], zahlen[i]);
end;
end;
Jonietz
Sort
iere
n u
nd
S
uch
en
16Lösungsvorschlag
procedure maxsort;
var
i, merke: tIndex;
begin
for i:= user_max downto 1 do
begin
merke:= max(0, i);
tausche(zahlen[merke], zahlen[i]);
end;
end;
Idee: Suche immer das Maximum und sammle von rechts
Jonietz
Sort
iere
n u
nd
S
uch
en
17Sortieren durch Einfügen
Idee:Nimm das nächste Element und füge es sortiert ein.
Sortieren eines Kartenspiels
Jonietz
Sort
iere
n u
nd
S
uch
en
18Sortieren durch Einfügen
5 7 2 8 3 1 4
5 7 2 8 3 1 4
2 8 3 1 45 7
2 8 3 1 45 7
2 8 3 1 45 7
2 83 1 45 7
2 831 45 7
2 831 4 5 7
Jonietz
Sort
iere
n u
nd
S
uch
en
19Sortieren durch Einfügen
5 7 2 8 3 1 4
7 2 8 3 1 4
2 8 3 1 4
8 3 1 4
3 1 4
1 4
4
5
75
752
8752
8752 3
8752 31
4 8752 31 „in situ“
Jonietz
Sort
iere
n u
nd
S
uch
en
20Sortieren durch Einfügen
Verschiebeoperationen sind auf Reihungen schwierig zu realisieren
Günstig auf anderen Datenstrukturen ( Listen)
Jonietz
Sort
iere
n u
nd
S
uch
en
21Bubblesort
Idee:Vergleiche paarweise und schiebe große Elemente nach hinten
Sortieren wie Blasen in einem Wasserglas aufsteigen: Große Blasen steigen schnell auf
Jonietz
Sort
iere
n u
nd
S
uch
en
22Bubblesort - Beispiel
5 7 2 8 3 1 4
5 72 83 1 4
5 72 83 1 4
5 72 83 1 4
5 72 831 4
5 72 831 4
5 72 831 4
Jonietz
Sort
iere
n u
nd
S
uch
en
23Algorithmus
Ende des Sortiervorgangs:– Wenn keine Vertauschung mehr stattfand– spätestens nach „Anzahl“ Schleifendurchläufen
bubblesort
Wiederhole bis keine Vertauschung stattfand
Für i von 0 bis Anzahl-1
Element i > Element i+1 ?ja nein
Vertausche beide
Jonietz
Sort
iere
n u
nd
S
uch
en
24Aufgaben
Implementieren Sie die
procedure bubblesort;
Der vorgestellte Bubblesort-Algorithmus kann noch verbessert werden: Die innere Schleife muss nicht immer bis zum Ende durchlaufen werden. Durchdenken Sie dies und verbessern Sie Ihre Implementierung.
Jonietz
Sort
iere
n u
nd
S
uch
en
25Lösungsvorschlag
procedure bubblesort;
var i: tIndex;
getauscht: boolean;
begin
repeat
getauscht:= FALSE;
for i:= 0 to user_max-1 do
if (zahlen[i] > zahlen[i+1]) then
begin
tausche(zahlen[i], zahlen[i+1]);
getauscht:= TRUE;
end;
until not getauscht;
end;
Jonietz
Sort
iere
n u
nd
S
uch
en
26Teil 2
Quicksort
Jonietz
Sort
iere
n u
nd
S
uch
en
27Quicksort
Prinzip: Teile und Herrsche
Wähle ein Pivot-Element, das das Problem in zwei Teilprobleme zerlegt.
Ein Bereich enthält dann alle Elemente, die kleiner sind als das Pivot-Element, der andere Bereich alle Elemente, die größer sind.
Löse die Teilprobleme auf die gleiche Art und Weise.
Jonietz
Sort
iere
n u
nd
S
uch
en
28Quicksort - Beispiel
5 7 28 31 4
572 831 4
5 72 831 4
5 72 831 4
5 72 831 4
Jonietz
Sort
iere
n u
nd
S
uch
en
29Quicksort - Pivot-Element
Die Wahl des Pivot-Elementes beeinflusst wesentlich die Anzahl benötigter Durchgänge
schlecht:– p=min() und p=max()
gut:– p=Zahlen[(links + rechts) div 2]– Feld mittleren Wertes
optimal: ein Element das den zu sortierenden Bereich in zwei gleich große Teile partitioniert
Jonietz
Sort
iere
n u
nd
S
uch
en
30Quicksort - Zerlegen
5 72 8 314
53
Jonietz
Sort
iere
n u
nd
S
uch
en
31Quicksort - Zerlegen
5 72 8 314
5723 1
Jonietz
Sort
iere
n u
nd
S
uch
en
32Quicksort - Zerlegen
5 72 8 314
572 83 1 4
Jonietz
Sort
iere
n u
nd
S
uch
en
33Zerlege - Algorithmus
zerlege (links, rechts)
Bestimme Pivot-Element p
Wiederhole bis links > rechts
Solange Wert[links] < p
links:= links +1
Solange Wert[rechts] > p
rechts:= rechts -1
links <= rechtsja nein
links < rechtsja nein
Vertausche
Wert[links] mit Wert[rechts]
links:= links +1
rechts:= rechts -1
Jonietz
Sort
iere
n u
nd
S
uch
en
34Quicksort - Algorithmus
quicksort (anfang, ende)
links:= anfang
rechts:= ende
zerlege(links, rechts)
anfang < rechtsja nein
quicksort(anfang, rechts)
links < endeja nein
quicksort(links, ende)
Jonietz
Sort
iere
n u
nd
S
uch
en
35Aufgaben
Schreiben Sie die Funktion
function pivot (links, rechts: tIndex): tIndex;
Implementieren Sie
procedure zerlege (var links, rechts: tIndex);
und damit dann insgesamt Quicksort
procedure quicksort(anfang, ende: tIndex);
Jonietz
Sort
iere
n u
nd
S
uch
en
36Lösungsvorschlag
function pivot (links, rechts: tIndex): tIndex;
begin
pivot:= zahlen[(links + rechts) DIV 2]
end;
Jonietz
Sort
iere
n u
nd
S
uch
en
37Lösungsvorschlag
procedure zerlege (var links, rechts: tIndex);
var
p : tWert;
begin
p := pivot(links, rechts);
repeat
while zahlen[links] < p do
links:= links +1;
while zahlen[rechts] > p do
rechts:= rechts -1;
...
Jonietz
Sort
iere
n u
nd
S
uch
en
38Lösungsvorschlag
...
if (links <= rechts) then
begin
if (links < rechts) then
tausche (zahlen[links], zahlen[rechts]);
links := links +1;
rechts := rechts -1;
end;
until (links > rechts);
end;
Jonietz
Sort
iere
n u
nd
S
uch
en
39Lösungsvorschlag
procedure quicksort(anfang, ende: tIndex);
var
links, rechts: tIndex;
begin
links:= anfang;
rechts:= ende;
zerlege (links, rechts);
if (anfang < rechts) then
quicksort(anfang, rechts);
if (links < ende) then
quicksort(links, ende);
end;
Jonietz
Sort
iere
n u
nd
S
uch
en
40Weitere Sortierverfahren
Heapsort Shellsort Bucketsort Platzziffersortieren Mergesort
Jonietz
Sort
iere
n u
nd
S
uch
en
41Teil 3
Effizienz von Sortierverfahren
Jonietz
Sort
iere
n u
nd
S
uch
en
42Kriterien
Stabilität– Bleiben evtl. vorhandene Vorsortierungen erhalten?
Geschwindigkeit– Anzahl Vergleiche– Anzahl Tauschoperationen
Einfluss von Parametern auf den Sortiervorgang– Quicksort: Bestimmung des Pivot-Elementes
Jonietz
Sort
iere
n u
nd
S
uch
en
43Stabilität
Was passiert mit nach anderen Kriterien bereits sortierten Daten? Angenommen, Blau < Rot
4 41 231 4
4 41 2 31 4 Auswahl (von links)
441 2 31 4 Auswahl (von rechts)
Jonietz
Sort
iere
n u
nd
S
uch
en
44Stabilität
Beispiel: Adressdaten (Telefonbuch o.ä.) Daten:
– Name– Ort– ...
Sind bereits sortiert nach Ort, sollen jetzt nach Name sortiert werden
Die Vorsortierung soll erhalten bleiben!
Jonietz
Sort
iere
n u
nd
S
uch
en
45Komplexität
Unterscheiden 3 Fälle:– Best Case– (Average Case)– Worst Case
Aufwandsbestimmung– Messung– Zählung und arithmetische Rechnung– asymptotische Abschätzung
Jonietz
Sort
iere
n u
nd
S
uch
en
46Experimente
Verwenden Zähler zur Abschätzung des Aufwandes
Jonietz
Sort
iere
n u
nd
S
uch
en
47Experimente - Daten
2 neue Zähler:
var
tausch_z: integer = 0;
// Anzahl Tauschoperationen
vergleich_z: integer = 0;
// Anzahl Vergleichsoperationen
Jonietz
Sort
iere
n u
nd
S
uch
en
48Exkurs - Ereignissteuerung
Die Initialisierung der Zähler geschieht beim Aufruf der Sortierprozedur aus der Ereignissteuerung heraus:
procedure
TForm1.austausch_sortieren(Sender: TObject);
begin
tausch_z:= 0;
vergleich_z:= 0;
minsort;
zeige_zaehler;
zeige_zahlen;
end;Aktuelle Werte anzeigen
Zähler initialisieren
Verfahren starten
Jonietz
Sort
iere
n u
nd
S
uch
en
49Aufgaben
Erweitern Sie die Algorithmen so, dass die entsprechenden Zähler erhöht werden.– tausche– min bzw. max– minsort bzw. maxsort– bubblesort– zerlege– quicksort
Untersuchen Sie experimentell den Aufwand bei der Sortierung einiger Zahlenreihen. Wie verhalten sich die verschiedenen Verfahren bei bereits sortierten und umgekehrt sortierten Daten?
Jonietz
Sort
iere
n u
nd
S
uch
en
50Lösung (exemplarisch)
procedure tausche(var x, y: tWert);
var
hilf: tWert;
begin
hilf:= x;
x:= y;
y:= hilf;
tausch_z:= tausch_z +1;
end;
Jonietz
Sort
iere
n u
nd
S
uch
en
51Groß-O-Notation
Wenn für die Laufzeit T(n) eines Algorithmus gilt:
T(n) c*n für eine Konstante c>0 und alle Werte n>n0,
so sagt man „T(n) ist in O(n)“
(IdR reicht es den „stärksten“ Ausdruck zu wählen.)
Jonietz
Sort
iere
n u
nd
S
uch
en
52Aufwand minsort
Aufwand für die Suche des Minimums: (n Elemente)– beim 1. Durchlauf: n-1 Vergleiche– beim 2. Durchlauf: n-2 Vergleiche– beim n. Duchlauf: n-n Vergleiche
– Gesamt:
Tauschoperationen:– in jedem Durchlauf genau eine, also gesamt
n-1 Stück in O(n)
n (n - i) = .5n²-.5n ~ n² in O(n²)i=1
Jonietz
Sort
iere
n u
nd
S
uch
en
53Aufwand bubblesort
Vergleichsoperationen (best case)– beim 1. Durchlauf: n-1 Vergleiche– Fertig!
Tauschoperationen (best case)– keine
Die ursprüngliche Fassung
Jonietz
Sort
iere
n u
nd
S
uch
en
54Aufwand bubblesort
Vergleichsoperationen (worst case)– beim 1. Durchlauf: n-1 Vergleiche– beim 2. Durchlauf: n-1 Vergleiche– ...– beim n. Duchlauf: n-1 Vergleiche– Gesamt: n*(n-1) = n²-n in O(n²)
Tauschoperationen (worst case)– beim 1. Durchlauf: n-1 Austausche– beim 2. Durchlauf: n-2 Austausche– ...– beim n. Durchlauf: n-n Austausche
– Gesamt:
n (n - i) = .5n²-.5n in O(n²)i=1
Jonietz
Sort
iere
n u
nd
S
uch
en
55Aufwand Quicksort
Bestimmung des Pivot-Elementes– hier so gestaltet, dass Aufwand zur Bestimmung
vernachlässigbar– aber: Wahl des Elementes hat großen Einfluß auf den
weiteren Aufwand! Ungünstigste Wahl führt zu O(n²)!
Vereinfachte Analyse unter folgenden Bedingungen:– Anzahl Elemente 2er-Potenz: n=2k
– Zerlegung halbiert immer– Zerlegung:
fortwährende Halbierung führt zu Zerlegungstiefe log2 (n)
– führt insgesamt auf: O(n*log2(n))
Jonietz
Sort
iere
n u
nd
S
uch
en
56Messergebnisse
Überblick und Ergebnisse der Zählungen
Min/Maxsort: O(n²) Bubblesort: O(n²) Quicksort: O(n*log2(n))
n
VergleicheAustausche
9 90 999 999000 99 9900 Vergleiche0 45 0 499500 0 4950 Austausche31 26 606 512 9009 8018 Vergleiche0 5 0 50 0 500 Austausche
100 1000459
495099
499500999
10
Minsort
Bubblesort
Quicksort
Jonietz
Sort
iere
n u
nd
S
uch
en
57Teil 4
Suchalgorithmen
Jonietz
Sort
iere
n u
nd
S
uch
en
58Suchalgorithmen
Zwei grundlegende Strategien:– lineares (sequenzielles) Suchen– binäres Suchen
Beispiel Telefonbuch– Suche nach Namen: binär (naja, in etwa)– Suche nach Nummer: linear
Beispiel Reihe von Zahlen– Suche nach Minimum und Maximum: linear
Jonietz
Sort
iere
n u
nd
S
uch
en
59Lineares Suchen - Bsp
Suche nach Element 11
11 133 1751 7
11 133 1751 7
11 133 1751 7
möglich
unmöglich
Testelement
Treffer
11 133 1751 7
11 133 1751 7
11 133 1751 7
Jonietz
Sort
iere
n u
nd
S
uch
en
60Lineares Suchen
Prüfe der Reihe nach alle Elemente ab, bis das gesuchte Element gefunden ist oder keine Elemente mehr da sind.
keine Voraussetzungen an die Daten, dürfen auch unsortiert sein.
Jonietz
Sort
iere
n u
nd
S
uch
en
61Lineares Suchen - Alg.
lineare_suche (wonach)
Wiederhole bis gefunden oder alles durchlaufen
wert[pos]=wonachja nein
gefunden!
merke pos
Gehe zur
nächsten pos
Jonietz
Sort
iere
n u
nd
S
uch
en
62Binäres Suchen
Voraussetzung:sortierte Daten
Idee:– Beginne mit der Suche in der Mitte der Daten; – wenn der Suchschlüssel kleiner ist suche in der Mitte des
rechten Bereiches weiter, – wenn der Suchschlüssel größer ist in der Mitte des linken
Bereiches.
Jonietz
Sort
iere
n u
nd
S
uch
en
63Binäres Suchen - Beispiel
Suche nach Element 11
11 133 1751 7
11 133 1751 7
11 133 1751 7
möglich
unmöglich
Testelement
Treffer
11 133 1751 7
Jonietz
Sort
iere
n u
nd
S
uch
en
64Binäres Suchen - Alg.
binaeres_suchen (wonach)
links:= Anfang
rechts:= Ende
Wiederhole bis gefunden
oder links > rechts
Berechne mittlere Position
zwischen links und rechts
wonach < wert(pos)ja nein
rechts:= pos -1
wonach > wert(pos)ja nein
links:= pos +1
Jonietz
Sort
iere
n u
nd
S
uch
en
65Aufgabe
Vereinbarung:Wenn das Gesuchte nicht in den Daten enthalten ist soll -1 zurückgegeben werden!
Erweiterung der Datenstruktur:type tIndexFehler = integer;
Implementieren Sie
function lineare_suche(wonach: tWert): tIndexFehler;
function binaere_suche(wonach: tWert): tIndexFehler;
Jonietz
Sort
iere
n u
nd
S
uch
en
66Lösung
function
lineare_suche(wonach: tWert): tIndexFehler;
var
i: tIndex;
position: tIndexFehler;
begin
position:= -1; i:= 0;
repeat
if zahlen[i] = wonach then
position:= i;
i:= i+1;
until (position <> -1) OR (i-1 = user_max);
lineare_suche:= position;
end;
Jonietz
Sort
iere
n u
nd
S
uch
en
67Lösung
function
binaere_suche(wonach: tWert): tIndexFehler;
var
links, rechts, position : tIndex;
begin
links:= 0;
rechts:= user_max;
// hier eigentliche Suche ...
if (wonach = zahlen[position]) then
binaere_suche:= position
else
binaere_suche:= -1;
end;
Jonietz
Sort
iere
n u
nd
S
uch
en
68Lösung
// das hier ist die eigentliche Suche:
repeat
position:= (links + rechts) div 2;
if (wonach < zahlen[position]) then
rechts:= position -1;
else if (wonach > zahlen[position]) then
links:= position +1;
until (wonach = zahlen[position]) //Treffer!
OR (links > rechts); //nicht gefunden
Jonietz
Sort
iere
n u
nd
S
uch
en
69Lineare vs. Binäre Suche
Verdoppelt sich die Anzahl Elemente, so führt dies schlimmstenfalls zu
– einer Verdopplung des Aufwandes bei linearer Suche– einem zusätzlichen Vergleich bei binärer Suche
Einbau von Zählern verdeutlicht dies:
var
linear_z: integer = 0;
binaer_z: integer = 0;
Jonietz
Sort
iere
n u
nd
S
uch
en
70Übung
Erweitern Sie die Suchfunktionen, indem Sie die Zähler für jeden benötigten Suchschritt (jeden benötigten Vergleich) erhöhen
function binaere_suche(wonach: tWert): tIndexFehler;
function
lineare_suche(wonach: tWert): tIndexFehler;
Jonietz
Sort
iere
n u
nd
S
uch
en
71Such-Experimente
Jonietz
Sort
iere
n u
nd
S
uch
en
72Weitere Suchverfahren
Fibonacci-Suche
Sprungsuche