AuK/Sortierte Folgen WS13-14
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
;Autoren
:[mailto://s3dobitt@stud.hszg.de Dominik Bitterlich]<br/>
:[mailto://s3alhaes@stud.hszg.de Alexander Häse]
==Einleitung==
===Sortierte Folgen===
In der Informatik ist eine Folge eine Aneinanderreihung von Symbolen eines Alphabets.
Ein Alphabet ist eine endliche Menge von voneinander unterscheidbaren Symbolen, die aus Zeichen oder Buchstaben bestehen. Diese können mit Hilfe bestimmter Algorithmen sortiert werden. Bekannte Sortieralgorithmen sind Selection Sort, Insertion Sort, Quicksort, Countingsort und Heapsort. Die neu entstandene Folge nennt man Sortierte Folge. Diese Folgen können in der Informatik zum Beispiel in Arrays oder Listen umgesetzt werden.
===Verwendung===
<language>Java</language>
<language>Java</language>
==Suchen in einer sortierten Folge==
===Algorithmisches Problem===
Bei der Suche in einer ''sortieren Folge'' ist es das Ziel ein bestimmtes Element k in einer Menge $M$ zu finden und z.B. dessen Index auszugeben.
Eingegeben werden soll eine endliche, aufsteigend ''sortierte Folge'' $e_0, e_1… e_n$ von
Elementen aus einer Menge $M$, auf der eine Ordnung “$<$” gegeben ist.
Außerdem soll ein Element $k ∈ M$, welches gesucht werden soll angeben werden.
Ausgeben werden soll der Index des Elementes, $i ∈ {0, 1 … n}$ sodass $e_i = k$ gilt, vorausgesetzt ein solcher Index existiert. Ansonsten wird „'''nicht enthalte'''n“ ausgegeben werden.
===Beispiele===
====Beispiel 1====
$M$ sei die Menge der ganzen Zahlen und die gegebene
Ordnung “$<$” auf $M$ ist die übliche größer/kleiner Beziehung
zwischen zwei ganzen Zahlen.
1. Die gegebene, aufsteigend sortierte Folge sei:
$4; 6; 8; 9; 13; 15; 16; 21; 35; 47; 51; 126; 211$
Gesucht werden soll nach $k = 35$.
Die gewünschte Ausgabe ist der Index $8$.
2. Die gegebene, aufsteigend sortierte Folge sei:
$4; 6; 8; 9; 13; 15; 16; 21; 35; 47; 51; 126; 211$
Gesucht werden soll nach $k = 17$.
Die gewünschte Ausgabe ist '''nicht enthalten'''.
====Beispiel 2====
$M$ sei die Menge der Wörter der deutschen Sprache und
die gegebene Ordnung “$<$” auf $M$ ist die Reihenfolge, in der
die Wörter im Duden erscheinen oder auch
lexikographische Ordnung genannt.
Die gegebene, aufsteigend sortierte Folge sei:
$alt, beige, braun, eng, gesund, japanisch, jung, xenophob$
Gesucht werden soll nach $k = kalt$.
Die gewünschte Ausgabe ist '''nicht enthalten'''.
===Lineare Suche===
Lineare Suche ist ein Algorithmus, der auch unter dem Namen sequentielle Suche bekannt ist. Er ist der einfachste Suchalgorithmus überhaupt.
Die Aufgabe besteht hier darin, ein Element in einer Liste oder einem Array mit $n$ Elementen zu finden.
Die Arbeitsweise ist hier folgende:
'''1.''' Gehe die Indizes $i$ der Elemente in der gegebenen ''sortierten Folge'' beginnend bei $0$ einen nach dem anderen durch.
'''1.1''' Falls $e_i$ gleich $k$ ist, dann brich die Suche ab und gib den Index $i$ aus.
'''1.2''' Sonst
'''1.2.1''' Falls $k < e_i$ ist, dann brich die Suche ab und gib '''nicht enthalten''' aus.
'''1.2.2''' Sonst gehe zum nächsten Element in der Folge.
'''2.''' Falls die Suche nicht zwischendurch abgebrochen wurde, gib '''nicht enthalten''' aus.
Umsetzen kann man den Algorithmus nun in einem '''Array''' oder in einer '''verketteten List'''.
====Umsetzung in Java auf einem Array====
<code id="52a87c2475863">
static int LineareSucheArray (int[] listOfNumbers, int k)
{
for(int i=0; i<listOfNumbers.length; i =i+1)
{
if (listOfNumbers [i]==k)
{
return i;
}
else
{
if (k < listOfNumbers [i])
{
return -1;
}
}
}
return -1;
}
</code>
<run id="52a87c24758ec">
int[] Folge = {4,6,8,9,13,15,16,21,35,47,51,126,211};
int k = 35;
int result = LineareSucheArray(Folge, k);
if (result < 0)
{
System.out.println("Nicht enthalten");
}
else
{
System.out.println ("Gefundener Index: "+result);
}
</run>
====Umsetzung in Java auf einer verketteten Liste====
===Analyse der linearen Suche===
Die Analyse dieses Algorithmus im Rahmen dieser Vorlesung wird aus zwei Schritten bestehen:
* 1. Es ´muss gezeigt werden, dass dieser Algorithmus für alle zulässigen Eingaben das Gewünschte leistet
* 2. Es muss abgeschätzt werden, wie lange der Algorithmus im schlimmsten Fall - worst case braucht.
Dass die sequentielle Suche das Gewünschte leistet, scheint erst einmal klar zu sein.
Also wird sich eingehender mit der Laufzeit des Algorithmus beschäftigt.
====Annahmen zur Analyse der Laufzeit====
Es wird angenommen, dass die Ausführung etwa folgender Bausteine eines Algorithmus auf jedem Rechner nach einer bestimmten Zeit abgeschlossen ist, die nicht von der Eingabe abhängen:
* Vergleich
* Zuweisung eines Wertes an eine Variable
* Addition von zwei ganzen Zahlen
* Rückgabe eines Wertes aus einer Methode
Außerdem der wird festgehalten das diese Anweisungen/Befehle in konstanter Zeit ausgeführt werden können und sie werden als elementare Anweisungen/Befehle bezeichnet.
====Laufzeit in Abhängigkeit von der Eingabe====
Sich Gedanken über die Laufzeit eines Algorithmus zu machen, bedeutet also zu zählen, wie viele elementare Anweisungen insgesamt im Algorithmus ausgeführt
werden. Diese Anzahl wird aber in den meisten Fällen davon abhängen, welche Eingabe dem Algorithmus übergeben wurde.
'''Beispiele:'''
Der Einfachheit halber zählen wir erst einmal nur die Vergleiche, die zwischen $k$ und Elementen aus $M$ in der gegebenen Folge durchgeführt werden.
* Folge: $4, 6, 8, 9, 13, 15, 16, 21, 35, 47, 51, 126, 211$
* $k = 8$
* Die Anzahl der Vergleiche beträgt $5$: zwei Mal mit $4$, zwei Mal mit $6$, ein Mal mit $8$
* Folge: $4, 6, 8, 9, 13, 15, 16, 21, 35, 47, 51, 126, 211$
* $k = 7$
* Die Anzahl der Vergleiche beträgt $6$: zwei Mal mit $4$, zwei Mal mit $6$, zwei Mal mit $8$
* Folge: $4, 6, 8, 9, 13, 15, 16, 21, 35, 47, 51, 126, 211$
* $k = 300$
* Die Anzahl der Vergleiche beträgt $26$: jeweils zwei Mal mit jedem Element der Folge
====Laufzeit im schlimmsten Fall (worst case)====
In dieser Vorlesung wird sich für die größte Laufzeit interessiert , die man für alle zulässigen Eingaben erhalten kann (''worst Case Analyse''). Bei der linearen Suche gilt offenbar: Die Suche nach einem Element $k$ in einer sortieren Folge mit $n$ Elementen benötigt nie mehr als $2n$ Vergleiche ( von $k$ mit Elementen aus der gegebenen Folge).
Es kann also die Anzahl $V$ dieser Vergleiche im worst Case als Funtkion darstellen:
* $V$: $\mathbb{N}\rightarrow \mathbb{N} $ mit $V(n)= 2n$
Analog kann dieser Algorithmus als eine Funktion:
$T$: $\mathbb{N}\rightarrow \mathbb{N}$
wobei $T(n)$ dann die maximale Anzahl von elementaren Anweisungen ist (nicht nur Vergleiche!), die für eine Eingabefolge mit $n$ Elementen ausgeführt werden.
'''Laufzeit im worst case auf einem Array'''
<code id="52a9c4aa4df40">static int LineareSucheArray (int[] listOfNumbers, int k)
{
for(int i=0; i<listOfNumbers.length; i =i+1)
{
if (listOfNumbers [i]==k)
{
//passenden Index gefunden
return i;
}
else
{
if (k < listOfNumbers [i])
{
//k nicht in Folge enthalten
return -1;
}
}
}
//k nicht in Folge enthalten
return -1;
}</code>
Man erhält: $T(n) = 5n + 3$
---------------------------
'''Laufzeit im worst case auf einer verketteten List'''
<code id="52a9c4aa4e081"> static int LineareSucheVerketteteListe(VerketteteListe Folge, int k)
{
//Zum Merken des aktuellen Listenelements
ListenElement e = Folge.head;
for(int i = 0; i < Folge.anzahlElemente; i+1)
{
if(e.z == k)
{
//passenden Index gefunden
return i;
}
else
{
if(k < e.z)
{
//k nicht in Folge enthalten
return -1;
}
else
{
//Gehe zum naechsten Listenelement
e = e.next;
}
}
}
//k nicht in Folge enthalten
return -1;
}</code>
Man erhält: $T(n) = 6n + 4$
==Idee zur Beschleunigung der Suche==
Wenn die sortierte Folge als Array gegeben ist, dann kann $k$ im ersten Schritt mit einem beliebigen Element in der sortierten Folge verglichen werden.
Man muss also nicht von vorn nach hinten durchlaufen wie in einer verketteten Liste.
Beispiel: $k = 37$ und die sortierte Folge sei wieder:
$4; 6; 8; 9; 13; 15; 16; 21; 35; 47; 51; 126; 211$
Man kann k mit dem Element an Position 3 vergleichen(also mit der 9).
Ergebnis: Wenn die $37$ überhaupt in der sortierten Folge enthalten ist, dann muss sie an einer Position größer oder gleich $4$ stehen.
Beispiel: $k = 3$7 und die sortierte Folge sei wieder:
$4; 6; 8; 9; 13; 15; 16; 21; 35; 47; 51; 126; 211$
Ebenso könnten wir $k$ mit dem Element an Position 9 vergleichen (also mit der $47$).
Ergebnis: Wenn die $37$ überhaupt in der sortierten Folge enthalten ist, dann muss sie an einer Position kleiner oder gleich $8$ stehen.
Beachte: In beiden Fällen führt ein Vergleich zum Ausschluss einer ganzen Reihe von Elementen der sortierten Folge für die weitere Suche.
Man möchte nun gern eine Garantie folgender Art: Nach dem Vergleich von $k$ mit einem geeigneten Element der sortierten Folge können immer mindestens soundso viele Elemente von der weiteren Suche ausgeschlossen
werden.
Mit dem Element an welcher Position sollte man $k$ also zuerst vergleichen'''?'''
===Algorithmus binäre Suche===
Gegeben ist eine sortierte Folge in einem Array$ A$ der Länge $n$ und das gesuchte Element $k$.
1.Mit $u$ und $o$ seien im Folgenden immer die erste und die letzte Position im Array bezeichnet, zwischen denen $k$ liegen muss (wenn es überhaupt in $A$ enthalten ist).
2.Setze $u = 0$ und $o = n -1$.
3. Solange $u <=o $
3.1 Berechne $p=[(o+u)/2]$.
3.2 Falls $A[p]$ gleich $k$ ist, brich die Suche ab und gib die Position $p$ aus.
3.3 Sonst
3.3.1 Falls $A[p]$ kleiner als $k$ ist, setze $u =p+1$.
3.3.2 Sonst setze $o = p -1$
4. Gib ''Nicht enthalten'' aus
<language>Java</language>
===Umsetzung in Java===
<code>static int binaereSuche(int[] a, int k)
{
//unter Grenze des verbleibenden Bereichs
int u = 0;
//obere Grenze des verbleibenden Bereichs
int o = a.length - 1;
//aktuelle Position mit der verglichen wird
int p;
while(u <= o)
{
p = (u+o)/2;
if(a[p] == k) {return p;}
else
{
if(a[p] < k) {u = p + 1;}
else {o = p - 1;}
}
}
//k nicht in Folge enthalten
return -1;
</code>
<run id="52a9d0eab9b4f"> int[] folge = {4,6,8,9,13,15,16,21,35,47,51,126,211};
int k = 35;
//Suche nach k
int result = binaereSuche(folge,k);
if(result < 0)
{
System.out.println("Nicht enthalten");
}
else
{
System.out.println("Gefundener Index: " + result);
}</run>
===Laufzeit der binären Suche im worst case===
====Wie viele Durchläufe im worst case?====
====Vergleich Laufzeit Lineare Suche und binäre Suche====
{| class="wikitable" style="width:500px"
|-
!n
!lineare Suche: $T(n)=5n+3$
!binäre Suche: $T(n)<=8log_2 n +13$
|-
|4
|23
|29
|-
|16
|83
|45
|-
|256
|1283
|77
|-
|4096
|20483
|109
|-
|65536
|327683
|141
|-
|1048576
|5242883
|163
|-
|16777216
|83886083
|205
|-
|}
In den meisten Fällen ist man bei der Analyse der Laufzeit nur am asymptotischen Verhalten der Funktion $T(n)$ interessiert welche in der $O$-Notation festgehalten ist:
*Die worst case Laufzeit der sequentiellen Suche in einer sortierten Folge von $n$ Elementen ist in $O(n)$.
*Die worst case Laufzeit der binären Suche in einer sortierten Folge von $n$ Elementen ist in $O(log_2 n)$.
Bei dieser Analyse sollte jedoch zusätzlich erwähnt werden, dass diese Laufzeit abhängig von der Laufzeit des eventuell voran gegangenen Sortieralgorithmus ist.
{| class="wikitable sortable"
|-
! Name !! Best Case !! Average Case !! Worst Case
|-
| Selection Sort || $\mathcal{O}(n^2)$ || $\mathcal{O}(n^2)$ || $\mathcal{O}(n^2)$
|-
| Insertion Sort || $\mathcal{O}(n)$ || $\mathcal{O}(n^2)$ || $\mathcal{O}(n^2)$
|-
| Mergesort || $\mathcal{O}(n \cdot log(n))$ || $\mathcal{O}(n \cdot log(n))$ || $\mathcal{O}(n \cdot log(n))$
|-
| Quicksort || $\mathcal{O}(n \cdot log(n))$ || $\mathcal{O}(n \cdot log(n))$ || $\mathcal{O}(n^2)$
|-
| Countingsort || $\mathcal{O}(n+m)$ || $\mathcal{O}(n+m)$ || $\mathcal{O}(n+m)$
|-
| Heapsort || $\mathcal{O}(n \cdot log(n))$ ||$\mathcal{O}(n \cdot log(n))$ || $\mathcal{O}(n \cdot log(n))$
|}