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