Sequentielle Suche

← zurück zur Startseite

Wertetabelle:

Werte 5 8 6 1 3 4 9 0 7 2

Index
0 1 2 3 4 5 6 7 8 9

1. 5 == 0 -> false -> weiter

8 == 0 -> false -> weiter
6 == 0 -> false -> weiter
0 == 0 -> true -> gib Index zurÃ¼ck

Jedes Element muss angesehen werden bis entweder das gesuchte Element gefunden ist oder das Ende erreicht wurde
Element nicht enthalten -> RÃ¼ckgabe von -1
BinÃ¤re Suche
Elemente mÃ¼ssen eine Ordnung (Sortierung) haben!

â†’ natÃ¼rliche Ordnung: ABC, Zahlen, Datum
â†’ eigene Ordnung -> siehe: Interface Comparable

Wertetabelle:
Werte 0 1 2 3 4 5 6 7 8 9

Index 0 1 2 3 4 5 6 7 8 9
1. Pivot-Element suchen $$(\frac{LÃ¤nge}{2}) \Rightarrow$$, Pivot (4) == gesuchtes Element (3) $$ \rightarrow 4 > 3 \rightarrow$$ links neben Pivot-Element suchen

Pivot-Element suchen â‡’ Pivot (1) == gesuchtes Element (3) $$\rightarrow 1 < 3 \rightarrow$$ rechts neben Pivot-Element suchen
Pivot-Element suchen â‡’ Pivot (2) == gesuchtes Element (3) $$\rightarrow 2 < 3 \rightarrow$$ rechts neben Pivot-Element suchen
Pivot-Element suchen â‡’ Pivot (3) == gesuchtes Element (3) $$\rightarrow 3 == 3 \rightarrow$$ true â†’ Index zurÃ¼ckgeben

Beispiel Pivot-Element Optimierung:
Wertetabelle:
Werte 5 21 36 44 45 63 411

Index 0 1 2 3 4 5 6
(\frac{LÃ¤nge}{2}) \rightarrow 44
Position_{Pivot} = \frac{gesuchter \: Wert - kleinster \: Wert}{grÃ¶ÃŸter \: Wert - kleinster \: Wert} * gesuchter \: Wert
= \frac{21-5}{411-5}*21 = \frac{16}{406}*21 \approx 0,83 = 1
Zeichenkettensuche
Ausgang: ababc, abc, ababad
Suche: ababd
Naiver Algorithmus (indexof)
ababc abc ababd
1. ababd(âŒ)

ababd (âŒ)
ababd (âŒ)
\vdots
x. ababd (âœ…)

KMP-Algorithmus

â†³ Knuth, Morris, Pratt

Suche
ababc abc ababd
ababd
Verschiebungstabelle
0 1 2 3 4 5

$$\textcolor{red}{-1}$$ a b a b d

0 0 1 2 0
\textcolor{red}{\textnormal{Platzhalter fÃ¼r 1 Schritt weiter}}
BM-Algorithmus

â†³ Boyer, Moore

Suche
ababc abc ababd
ababd
Bad-Match-Tabelle
max (1, LÃ¤nge des Musters - aktueller Index im Muster - 1)
a b d *

$$\bcancel{4}$$ $$\bcancel{3}$$ $$1$$ $$4$$

$$2$$ $$1$$

* = alle anderen Zeichen, die nicht im Muster sind

1.
ababd
01234
1. $$max(1, 5-0-1) = max(1,4)$$

max(1,5-1-1) = max(1,3)
max(1,5-2-1) = max(1,2)
max(1,5-3-1) = max(1,1)
max(1,5-4-1) = max(1,0)
max(1,5-0-1) = max(1,4)

Seminar Sortieralgorithmen
Bubble-Sort

Ausgangsfolge	5	7	3	0	9	1	8	6	4	2
1. Schritt	5	3	7	0	9	1	8	6	4	2
1.1	5	3	0	7	9	1	8	6	4	2
1.2	5	3	0	7	1	9	8	6	4	2
1.3	5	3	0	7	1	8	9	6	4	2
1.4	5	3	0	7	1	8	6	9	4	2
1.5	5	3	0	7	1	8	6	4	9	2
1.6	5	3	0	7	1	8	6	4	2	9
2. Schritt	5	3	0	7	1	8	6	4	2	(9)
2.1	3	5	0	7	1	8	6	4	2	(9)
2.2	3	0	5	7	1	8	9	4	2	(9)
2.3	3	0	5	1	7	8	6	4	2	(9)
2.4	3	0	5	1	7	6	8	4	2	(9)
2.5	3	0	5	1	7	6	4	2	8	(9)

3. Schritt	3	0	5	1	7	6	4	2	(8)	(9)
3.1	0	3	5	1	7	6	4	2	(8)	(9)
3.2	0	3	1	5	7	6	4	2	(8)	(9)
3.3	0	3	1	5	6	7	4	2	(8)	(9)
3.4	0	3	1	5	6	4	7	2	(8)	(9)
3.5	0	3	1	5	6	4	2	7	(8)	(9)
$$\dotsb$$	(0)	(1)	(2)	(3)	(4)	(5)	(6)	(7)	(8)	(9)

Beispiel Optimierung:

falls keine Vertauschungen -> Abbruch

Selection-Sort

1. Schritt	5	7	3	0	9	1	8	6	4	2
k = 5, i = 0	k			i
2. Schritt	0	7	3	5	9	1	8	6	4	2
k = 7, i = 1		k				i
3. Schritt	0	1	3	5	9	7	8	6	4	2
k = 3, i = 2			k							i
4. Schritt	0	1	2	5	9	7	8	6	4	3
$$\vdots$$	$$\vdots$$	$$\vdots$$	$$\vdots$$	$$\vdots$$	$$\vdots$$	$$\vdots$$	$$\vdots$$	$$\vdots$$	$$\vdots$$	$$\vdots$$
n.Schritt	0	1	2	3	4	5	6	7	8	9

Insertion-Sort
Theorie: zufÃ¤lliger Wert
Praxis: 1. Wert

Ausgangsfolge	5	7	3	0	9	1	8	6	4	2
1. Schritt	5	7	3	0	9	1	8	6	4	2
2. Schritt (3 speichern)	5	7	_	0	9	1	8	6	4	2
3. Schritt (0 speichern)	3	5	7	_	9	1	8	6	4	2
$$\vdots$$					$$\vdots$$
n. Schritt	0	1	2	3	4	5	6	7	8	9

Quicksort

5		7	3	0	9	1	8	6	4	2
Pivot	â†‘								â†‘
	2		3	0	9	1	8	6	4		7
				â†‘				â†‘
	2	3	0	4	1		8	6	9	7
					â†‘

Radix-Sort

190	55	85	91	904	24	2	77
0	1	2	3	4	5	6	7	8	9
190	91	2		904	55		77
				24	85
190	91	02	904	24	55	85	77
0	1	2	3	4	5	6	7	8	9
02		24			55		77	85	190
904									91
002	904	024	055	077	085	190	091
0	1	2	3	4	5	6	7	8	9
002	190								904
024
055
077
085
091
2	24	55	77	85	91	190	904

Count-Sort