Jonietz Sortieren und Suchen 1 IFB 2002 Daniel Jonietz

Jonietz

Sortieren und Suchen

IFB 2002

Daniel Jonietz

Jonietz

2Überblick

Teil 1: Elementare Sortieralgorithmen

Teil 2: Quicksort

Teil 2: Effizienz von Sortierverfahren

Teil 3: Suchalgorithmen

Jonietz

3Teil 1

Elementare Sortieralgorithmen

Jonietz

4Motivation

Eine Reihe von Werten liegt unsortiert vor. Ziel: Die Werte sollen (aufsteigend) sortiert werden.

Jonietz

5Datenmodell

Die Werte liegen in einer Reihung vor:

0 1 2 user_max

tIndex

tZahlen

prog_max

Jonietz

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

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

8Auswahl-Sortieren V1

5 7 2 8 3 1 4

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

Jonietz

9Auswahl-Sortieren V2

5 7 2 8 3 1 4

57 2 8 3 4

57 8 3 4

5 „in situ“

Jonietz

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

11Minimum und Maximum

Aufruf findet statt in procedure TForm1.suche_minimum(Sender: TObject); procedure TForm1.suche_maximum(Sender: TObject);

Jonietz

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

13Lösungsvorschlag

function min(anfang, ende: tIndex): tIndex;

var i, min_pos: tIndex;

min_wert: tWert;

min_pos:= anfang;

min_wert:= zahlen[min_pos];

for i:= anfang+1 to ende do

if (zahlen[i] < min_wert) then

min_pos:= i;

min_wert:= zahlen[min_pos];

min:= min_pos;

Kandidat

besserer Kandidat

Jonietz

14Lösungsvorschlag

function max(anfang, ende: tIndex): tIndex;

var i, max_pos: tIndex;

max_wert: tWert;

max_pos:= anfang;

max_wert:= zahlen[max_pos];

for i:= anfang+1 to ende do

if (zahlen[i] > max_wert) then

max_pos:= i;

max_wert:= zahlen[max_pos];

max:= max_pos;

Kandidat

besserer Kandidat

Jonietz

15Lösungsvorschlag

procedure minsort;

i, merke: tIndex;

for i:= 0 to user_max-1 do

merke:= min(i, user_max);

tausche(zahlen[merke], zahlen[i]);

Jonietz

16Lösungsvorschlag

procedure maxsort;

i, merke: tIndex;

for i:= user_max downto 1 do

merke:= max(0, i);

tausche(zahlen[merke], zahlen[i]);

Idee: Suche immer das Maximum und sammle von rechts

Jonietz

17Sortieren durch Einfügen

Idee:Nimm das nächste Element und füge es sortiert ein.

Sortieren eines Kartenspiels

Jonietz

5 7 2 8 3 1 4

2 8 3 1 45 7

2 83 1 45 7

2 831 45 7

2 831 4 5 7

Jonietz

5 7 2 8 3 1 4

7 2 8 3 1 4

2 8 3 1 4

8 3 1 4

8752 3

8752 31

4 8752 31 „in situ“

Jonietz

Verschiebeoperationen sind auf Reihungen schwierig zu realisieren

Günstig auf anderen Datenstrukturen ( Listen)

Jonietz

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

22Bubblesort - Beispiel

5 7 2 8 3 1 4

5 72 83 1 4

5 72 831 4

Jonietz

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

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

25Lösungsvorschlag

procedure bubblesort;

var i: tIndex;

getauscht: boolean;

repeat

getauscht:= FALSE;

for i:= 0 to user_max-1 do

if (zahlen[i] > zahlen[i+1]) then

tausche(zahlen[i], zahlen[i+1]);

getauscht:= TRUE;

until not getauscht;

Jonietz

26Teil 2

Quicksort

Jonietz

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

28Quicksort - Beispiel

5 7 28 31 4

572 831 4

5 72 831 4

Jonietz

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

30Quicksort - Zerlegen

5 72 8 314

Jonietz

5 72 8 314

5723 1

Jonietz

5 72 8 314

572 83 1 4

Jonietz

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

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

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

36Lösungsvorschlag

function pivot (links, rechts: tIndex): tIndex;

pivot:= zahlen[(links + rechts) DIV 2]

Jonietz

37Lösungsvorschlag

procedure zerlege (var links, rechts: tIndex);

p : tWert;

p := pivot(links, rechts);

repeat

while zahlen[links] < p do

links:= links +1;

while zahlen[rechts] > p do

rechts:= rechts -1;

Jonietz

38Lösungsvorschlag

if (links <= rechts) then

if (links < rechts) then

tausche (zahlen[links], zahlen[rechts]);

links := links +1;

rechts := rechts -1;

until (links > rechts);

Jonietz

39Lösungsvorschlag

procedure quicksort(anfang, ende: tIndex);

links, rechts: tIndex;

links:= anfang;

rechts:= ende;

zerlege (links, rechts);

if (anfang < rechts) then

quicksort(anfang, rechts);

if (links < ende) then

quicksort(links, ende);

Jonietz

40Weitere Sortierverfahren

Heapsort Shellsort Bucketsort Platzziffersortieren Mergesort

Jonietz

41Teil 3

Effizienz von Sortierverfahren

Jonietz

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

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

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

45Komplexität

Unterscheiden 3 Fälle:– Best Case– (Average Case)– Worst Case

Aufwandsbestimmung– Messung– Zählung und arithmetische Rechnung– asymptotische Abschätzung

Jonietz

46Experimente

Verwenden Zähler zur Abschätzung des Aufwandes

Jonietz

47Experimente - Daten

2 neue Zähler:

tausch_z: integer = 0;

// Anzahl Tauschoperationen

vergleich_z: integer = 0;

// Anzahl Vergleichsoperationen

Jonietz

48Exkurs - Ereignissteuerung

Die Initialisierung der Zähler geschieht beim Aufruf der Sortierprozedur aus der Ereignissteuerung heraus:

procedure

TForm1.austausch_sortieren(Sender: TObject);

tausch_z:= 0;

vergleich_z:= 0;

minsort;

zeige_zaehler;

zeige_zahlen;

end;Aktuelle Werte anzeigen

Zähler initialisieren

Verfahren starten

Jonietz

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

50Lösung (exemplarisch)

procedure tausche(var x, y: tWert);

hilf: tWert;

hilf:= x;

x:= y;

y:= hilf;

tausch_z:= tausch_z +1;

Jonietz

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

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

53Aufwand bubblesort

Vergleichsoperationen (best case)– beim 1. Durchlauf: n-1 Vergleiche– Fertig!

Tauschoperationen (best case)– keine

Die ursprüngliche Fassung

Jonietz

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

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

56Messergebnisse

Überblick und Ergebnisse der Zählungen

Min/Maxsort: O(n²) Bubblesort: O(n²) Quicksort: O(n*log2(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

Minsort

Bubblesort

Quicksort

Jonietz

57Teil 4

Suchalgorithmen

Jonietz

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

59Lineares Suchen - Bsp

Suche nach Element 11

11 133 1751 7

möglich

unmöglich

Testelement

Treffer

11 133 1751 7

Jonietz

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

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

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

63Binäres Suchen - Beispiel

Suche nach Element 11

11 133 1751 7

möglich

unmöglich

Testelement

Treffer

11 133 1751 7

Jonietz

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

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

66Lösung

function

lineare_suche(wonach: tWert): tIndexFehler;

i: tIndex;

position: tIndexFehler;

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;

Jonietz

67Lösung

function

binaere_suche(wonach: tWert): tIndexFehler;

links, rechts, position : tIndex;

links:= 0;

rechts:= user_max;

// hier eigentliche Suche ...

if (wonach = zahlen[position]) then

binaere_suche:= position

binaere_suche:= -1;

Jonietz

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

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:

linear_z: integer = 0;

binaer_z: integer = 0;

Jonietz

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

71Such-Experimente

Jonietz

72Weitere Suchverfahren

Fibonacci-Suche

Sprungsuche

Jonietz Sortieren und Suchen 1 IFB 2002 Daniel Jonietz

Documents

Funktionale Programmierung IFB 1/2002 Klaus Becker

Direktes Auswählen1 Sortieren durch direktes Auswählen Präsentation der Arbeitsweise des Sortieralgorithmus Sortieren durch direktes Auswählen

Suchen und Sortieren - Max Planck Institute for Informatics

Sortieren - Unterrichtsmaterial für Zyklus 1 · 2018. 9. 2. · Sortieren - Unterrichtsmaterial für Zyklus 1 CS Unplugged Sortiernetzwerke: um Sortierprozesse zu beschleunigen,

Information und ihre Darstellung: XHTML & CSS IFB Speyer Daniel Jonietz 2007

Industriefußböden (IFB) Dr. H.-W. Pilhofer 1 AWP Fasertechnik GmbH & Co. KG Wirtschaftliche Bemessung und Ausführung von Industriefußböden (IFB)

FÖRDERMÖGLICHKEITEN DURCH DIE IFB · PDF filefÖrderangebote der stadt hamburg fÖrdermÖglichkeiten durch die ifb hamburg hamburg, 30. august 2017 in der ifb

arrays und vectors, Suchen und Sortieren - fbi.h-da.de · PDF file2006 Pearson Education, Inc. All rights reserved. 1 7 arrays und vectors, Suchen und Sortieren

Algorithm Engineering von Anfang an: Sortieren und ...mehlhorn/AlgorithmEngineering/sanders_sb.pdf · Sanders: Algorithm Engineering 1 Algorithm Engineering von Anfang an: Sortieren

Rechnernetze und Datenübertragung IFB 2003 Daniel Jonietz

IFB - Richtlinie Baus · PDF fileIFB - Richtlinie Bauschutzabdichtungen Herausgegeben durch das IFB - Institut für Flachdachbau und Bauwerksabdichtung Münnichplatz 1, 1110 Wien

Algorithmische Grundstrukturen IFB 2002 Klaus Becker

FH-Hof Sortieren mit Binären Bäumen Richard Göbel

Kapitel 9: Sortierverfahren - Hochschule Konstanzbittel/ain_fprog/Vorlesung/09... · 2020. 9. 21. · Kapitel 9: Sortierverfahren §Problemstellung §Sortieren durch Einfügen §Sortieren

Information und ihre Darstellung: XHTML & CSS · 2013. 6. 5. · Information und ihre Darstellung: XHTML & CSS PL Speyer Daniel Jonietz 2011

Übersicht Mathe-Tag 1.Sortieren, Klassifizieren, Ordnen a)Legosteine nach Farben sortieren b)Bauklötze nach Formen/Größe/Farben sortieren c)Wäscheklammern

Strukturierte Programmierung IFB 2002 Tobias Selinger

Algorithmen und Datenstrukturen Sortieren · PDF fileUniversität Freiburg - Institut für Informatik - Graphische Datenverarbeitung Algorithmen Sortieren , Suchen, Optimieren Datenstrukturen

ifb- Familienreport - stmas. · PDF fileZur Lage der Familie in Bayern Schwerpunkt: Familienfreundlichkeit in Bayern ifb- Familienreport Bayern 2014 Ursula Adam, Tanja Mühling, Harald

FINANZIERUNG INNOVATIVER STARTUPS ......FINANZIERUNG INNOVATIVER STARTUPS – CROWDFUNDING, VC, FÖRDERPROGRAMME ODER HAUSBANK? Martin Jung, IFB Hamburg Dr. Heiko Milde, IFB Innovationsstarter