Suchen und Sortieren - userpages.uni-koblenz.desoftlang/oopmcourse/slides/searchsort.pdf · (C) Ralf Lämmel, OOPM, Universität Koblenz-Landau Permutationstest 14 // Assume all elements

Suchen und SortierenOOPM, Ralf Lämmel

Unterhaltet Euch mal mit Euren Großeltern wie Sortieren

früher funktionierte!

(C) Ralf Lämmel, OOPM, Universität Koblenz-Landau

Das Such-Problem

Eingabe: Ein Feld a mit n Elementen vom Typ t.Ein Wert x vom Typ t.

Ausgabe: Ein Boolescher Wert:

true: Es gibt ein 0 <= i < n so dass a[i] == xfalse: sonst

Alternative: Gib (ersten) Index i zurück.

2

Wir nehmen nichts weiter an als dass wir Gleichheit für t

bestimmen können.


Lineare Suche (Index-Rückgabe)

3

public static int linear(int[] a, int x) {

for (int i=0; i<a.length; i++)

if (a[i] == x) return i;

return -1;

}Beachte: eine For-Each-

Schleife wäre hier nicht (sinnvoll) anwendbar, da wir i zurückgeben

wollen!

Siehe package algorithm.search


Binäre Suche

Basierend auf der Annahme, dass das Eingabefeld (etwa aufsteigend) sortiert ist, beginnend in der Mitte des Feldes, suche das Element mittels Halbierung des Suchraums in jedem Schritt.

Die Suche beginnt mit i = Mitte.

Wenn a[i] = x, dann gefunden.

Wenn a[i] < x, dann in rechter Hälfte fortsetzen.

Wenn a[i] > x, dann in linker Hälfte fortsetzen.

...

4


Testen der Sortiertheit

5

Beispiel 1:

Eingabe: {1,2,3,4}

Ausgabe: true

Beispiel 2:

Eingabe: {1,3,2,4}

Ausgabe: false


Das Problem des Testens der Sortiertheit

Eingabe:

Ein Feld a mit n Elementen vom Typ t.

Ausgabe:

Ein Boolescher Wert:

true: a[i-1] <= a[i] für alle i mit 1 <= i < n

false: sonst

6

http://www.bambinipronto.com.au/


Probleme: Kontenverwaltung, Videokompression, ...

Programme: (Effektive) Problemlösungen

Spezifikationen: (“Gute”) Problembeschreibungen

Modelle: Abstraktionen von Problemlösungen u.a.

7

Ist diese Problembeschreibung eine Spezifikation, ein Modell oder

ein Programm?

Eingabe:

Ein Feld a mit n Elementen vom Typ t.

Ausgabe:

Ein Boolescher Wert:

true: a[i-1] <= a[i] für alle i mit 1 <= i < n

false: sonst


Sortiertheitstest

8

public static boolean isSorted(int[] a) {


if (a[i-1] > a[i])

return false; // inversion found

return true; // no inversion found

}

Siehe package algorithm.search


Binäre Suche

9

public static int binary(int[] a, int x) {int first = 0; // first index in rangeint last = a.length - 1; // last index in rangewhile (first <= last) {

int middle = first + ((last - first) / 2);if (a[middle] < x) {

first = middle + 1; // go to the right} else if (a[middle] > x) {

last = middle - 1; // go to the left} else

return middle;}return -1; // not found

} Siehe package algorithm.search


Zusammenfassung:Einfache Suchalgorithmen

Dimensionen der Variationen:

Effizienz (Laufzeit-Komplexität)

Annahmen über Eigenschaften des Feldes

Annahmen über Operationen (Gleichheitstest, etc.)

10


Das Sortier-Problem

11

23 57

Eine unsortierte Liste

2 3 5 7

Die sortierte Liste


Das Sortier-Problem

Eingabe: Ein Feld a mit n Elementen des Typs t

Annahme: Vergleichbarkeit (<,=) für Typ t

Ausgabe:

Ein Feld b

b ist sortiert.

b ist eine Permutation von a

12

Beachte: Dies ist eine Problembeschreibung (im

Gegensatz zu einer Lösung).


PermutationstestEingabe: Feld a und b gleicher Länge

Annahme: Gleicheitstest für Typ t verfügbar.

Ausgabe:

Gibt es eine 1:1 Abbildung von a auf b?

Ausgangs- und Bildelement sind jeweils gleich.

13

1

3

2

3

1

2


Permutationstest

14

// Assume all elements of the arrays to be distinctpublic static boolean isPermutation(int[] a, int[] b) {

if (a.length != b.length)return false;

for (int x : a) {boolean found = false;for (int y : b)

if (x == y) {found = true;break;

}if (!found)

return false;}return true;

}

Dies kann wesentlich eleganter beschrieben werden wenn wir

Label-basiertes Break/Continue verwenden.

Vorbedingung

Siehe package algorithm.sorting


Permutationstest (kompaktere Variante)

15

// Assume all elements of the arrays to be distinctpublic static boolean isPermutation(int[] a, int[] b) {

if (a.length != b.length)return false;

l1: for (int x : a) {for (int y : b)

if (x == y)continue l1;

return false;}return true;

}

Wie lässt sich diese Annahme aufgeben?



Verallgemeinerter Permutationsansatz

16

Eingabe: Felder a und b gleicher Länge l.Ausgabe: Boolescher Wert “Ist a eine Permutation von b?”(Eine mögliche) Vorgehensweise:

Initialisiere ein Boolesches Feld c der Länge l mit false.Für jedes Element x von a

Gibt es einen Index i mit x == b[i] und c[i] == false?- Ja: Setze c[i] = true.- Nein: Gib false zurück.


Verallgemeinerter Permutationsansatz

17

public static boolean isPermutation(int[] a, int[] b) {if (a.length != b.length)

return false;boolean[] c = new boolean[a.length];for (int i=0; i<c.length; i++)

c[i] = false;l1: for (int x: a) {

for (int i = 0; i < b.length; i++)if (x==b[i] && !c[i]) {

c[i] = true;continue l1;

}return false;

}}

Fangfrage: Können wir an dieser

Stelle stattdessen eine Methode für etwa lineare

Suche in b wiederverwenden?



Warum Sortieren in OOPM?

Grundlegende Technik in der Programmierung

Hervorragende Eignung für weitere Themen:

Laufzeitanalyse (Laufzeitkomplexität)

Speicherplatzanalyse (Speicherkomplexität)

Iterative vs. rekursive Lösungen

Verifikation

18


Ausgewählte Sortierverfahren

BubbleSort -- Sortieren durch Sprudeln

SelectionSort -- Sortieren durch Auswahl

InsertionSort -- Sortieren durch Einfügen

MergeSort -- Sortieren durch Mischen

19


Ausgabe eines Feldes(Gut zum visuellen Testen!)

20

Beispiel

Eingabe: {1,2,3,4}

Ausgabe: 1 2 3 4 (in der “Standardausgabe”)


Ausgabe eines Feldes

21

public static void print(int[] a) {


System.out.print(a[i] + " ");

System.out.println();

}

Siehe package data.vector

Eingabe: {1,2,3,4}

Ausgabe: 1 2 3 4 (in der “Standardausgabe”)


Der Ergebnistyp void

void ist ein spezieller vordefinierter Typ.

void ist formal ein Menge mit einem Element.

Verwendung:

Funkion berechnet keine Ergebnisse.

Beispiele: Mutationen, Ausgaben

22

BubbleSort - Beispiel

Inversionen benachbarter Elemente sind markiert.

★ 1.Runde8 2 4 9 72 8 4 9 72 4 8 9 72 4 8 9 7

★ 2.Runde2 4 8 7 92 4 8 7 92 4 8 7 92 4 7 8 9

★ 3.Runde2 4 7 8 92 4 7 8 92 4 7 8 92 4 7 8 9

9 ist nach oben “gebubbelt”.

Warum haben wir eine 3. Runde?


BubbleSort - Vorgehensweise

Wiederhole Pässe durch die Eingabe.

Beseitige Inversionen benachbarter Elemente.

Brich ab nach einem Pass ohne Inversionen.

Folgerung: Große Elemente “bubbeln” nach oben.

24


BubbleSort - Implementation

25

public static void bubbleSort(int[] a) {boolean swapped; // to notice swaps during a passdo {

swapped = false;for (int i=1; i<a.length; i++)

if (a[i-1] > a[i]) {// Swap!int swap = a[i];a[i] = a[i-1];a[i-1] = swap;swapped = true;

}} while (swapped); // another pass if swaps happened

}Siehe package algorithm.sorting


SelectionSort - Beispiel

26

8 2 4 9 7

2 4 7 8 9

2 4 7 8 9

2 4 7 9 8

2 4 8 9 7

2 8 4 9 7

Zeitachse


SelectionSort - Vorgehensweise

Entferne kleinstes Element x aus Eingabe.

Füge x der Ausgabe zu.

Wiederhole Schritte bis die Eingabe leer ist.

Folgerung: Ausgabe entsteht linear.

27


SelectionSort - Implementation

28

public static void selectionSort(int[] a) {for (int i=0; i<a.length; i++) {

// Find least element among the remaining onesint least = i;for (int j=i+1; j<a.length; j++)

if (a[j] < a[least])least = j;

// Swap current element with least oneif (least != i) {

int swap = a[i];a[i] = a[least];a[least] = swap;

}}

} Siehe package algorithm.sorting


InsertionSort - Beispiel

29

8 2 4 9 7

2 4 7 8 9

2 4 8 9 7

2 4 8 9 7

2 8 4 9 7

8 2 4 9 7

Zeitachse


InsertionSort - Vorgehensweise

Unterteilung

sortierter Präfix (anfangs leer)

unsortierter Rest (anfangs die Eingabe)

Wiederholung

Einfügen des Kopfes vom Rest in den Präfix

30


InsertionSort - Implementation

31

public static void insertionSort(int[] a) {for (int i=1; i<a.length; i++) {

int x = a[i]; // Element to be inserted// Insert elements in their prefix// Shift right elements if necessaryint j = i;while (j > 0 && a[j-1] > x) {

a[j] = a[j-1];a[j-1] = x;j--;

}}



MergeSort

32

Merge

Rekursives Sortieren

Linke Hälfte Rechte Hälfte

Zwischenergbnis

Teilung der Eingabe

Zwischenergbnis

Sortiertes Ergebnis


MergeSort - Beispiel

33

8 2 4 9 7

8 2 4 9 7

8 2 4 9 7

79 9 7

7 9428

4 7 92 8

2 4 7 8 9

commons.wikimedia.orgcommons.wikimedia.org


Mischen

34

2 8 4 7 9

2 84 7 9


MergeSort - Implementation

35

public static void mergeSort(int[] a, int[] temp, int min, int max) {

// Cease on trivial sorting problem

if (!(min<max))

return;

// Divide

int middle = ( min + max ) / 2 ;

// Solve smaller problems recursively

mergeSort(a,temp,min,middle);mergeSort(a,temp,middle+1,max);

// Merge via temporary array

merge(a,temp,min,middle,max);}



Merge - Implementation

36

public static void merge(int[] a, int[] temp, int min, int middle, int max) {

int i = min; // loop over left half

int j = middle+1; // loop over right half

int k = min; // loop over merged result

while (k<=max)

temp[k++] = (i <= middle && (j > max || a[i] < a[j])) ?

a[i++] // copy from left half

: a[j++]; // copy from right half

// Commit temporary result

for (k=min; k<=max; k++)

a[k] = temp[k];



Fangfragen

1. Können Sie sich ein Anwendungsszenario vorstellen, in der das spezifische Verhalten von SelectionSort (im Hinblick auf die Ergebnisentstehung) besser ist, als das von InsertionSort?

2. Welches Sortierverfahren würden Sie wählen, wenn Sie mit 10 HIWIs eine Klausur von 400 Studenten kontrollieren und diese am Ende nach der Matrikelnummer sortiert stapeln müssten?

37


Vertiefung in “Algorithmen und Datenstrukturen”

Weitere Verfahren (z.B. QuickSort, HeapSort)

Nichttriviale Implementationen

Nicht-vergleichsbasierte Verfahren

Genauere Herleitung von Komplexitäten

...

38


Zusammenfassung Sortieren ist ein fundamentales Problem.Viele Wege führen nach Rom.

Ausblick Welcher Weg ist effizient(er)?Wie weiß man, dass korrekt sortiert wird?Wie abstrahiert man z.B. von dem Elementtyp?...

Documents

Suchen und Sortieren - userpages.uni-koblenz.desoftlang/oopmcourse/slides/searchsort.pdf · (C) Ralf Lämmel, OOPM, Universität Koblenz-Landau Permutationstest 14 // Assume all elements