AuK/Sortierte Folgen WS13-14
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Java</language>
;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.
Insbesondere bei einer sortierten Liste sind die Knoten nicht in der sequentiellen Reihenfolge ihrer Eingabe angeordnet, sondern werden nach bestimmten Sortierkriterien (z.B. aufsteigend oder absteigend) geordnet.
Sortierte Listen haben Vorteile gegenüber unsortierten Listen – Daten können schneller aufgefunden werden – dies gilt insbesondere für beidseitig verkettete Listen. Denn es kann schon vor Beginn des Suchvorgangs ermittelt werden, ob das gesuchte Element eher am Ende oder am Anfang der Liste zu finden sein wird. Entsprechend kann der Suchvorgang am Ende oder am Anfang der Liste begonnen werden, was die Suchzeit erheblich verkürzt.
==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 mittels '''Array''' oder in einer '''verketteten List'''.
====Umsetzung in Java mittels 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 mittels verketteter Liste====
<code id="52ac809a2bcc8">
public class SeqSucheListe
{
static int sequentielleSucheVerketteteListe(MyLinkedList l, int k)
{
//Zum Merken des aktuellen Listenelements
MyListElement e = l.head;
for(int i = 0; i < l.numberOfElements; i++)
{
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>
===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 Funktion 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$
------------
'''Vergleich Laufzeit Lineare Suche in einem Array und in einer verketteten List'''
{| class="wikitable" style="width:500px"
|-
!n
!lineare Suche: $T(n)=5n+3$
!binäre Suche: $T(n)=6n+4$
|-
|4
|23
|29
|-
|16
|83
|45
|-
|256
|1283
|77
|-
|4096
|20483
|109
|-
|65536
|327683
|141
|-
|1048576
|5242883
|163
|-
|16777216
|83886083
|205
|-
|}
==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
===Umsetzung in Java===
<code id="52a9d771bbf9d">
static int binaereSucheArray(int[] listOfNumbers, int k) {
// unter Grenze des verbleibenden Bereichs
int u = 0;
// obere Grenze des verbleibenden Bereichs
int o = listOfNumbers.length - 1;
// aktuelle Position mit der verglichen wird
int p;
while (u <= o) {
p = (u + o) / 2;
if (listOfNumbers[p] == k) {
return p;
} else {
if (listOfNumbers[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 = binaereSucheArray(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))$
|}
==Einfügevorgang in einer sortierten Liste==
Der interne Aufbau einer sortierten Liste unterscheidet sich nur unwesentlich von einer unsortierten Liste. Wichtig ist, dass sie nicht nachträglich sortiert (wie z.B. bei Arrays üblich), sondern von Anfang an sortiert aufgebaut wird. Das heisst: Bereits beim Einfügen eines neuen Elements erhält dieses seine richtige Position in der Sortierreihenfolge - ein neuer Knoten wird nicht einfach an das Listenende angehängt, sondern an der passenden Position in die Liste eingefügt.
*Die Liste wird elementweise durchlaufen und dabei durch eine Vergleichs-operation mit den bereits vorhandenen Elementdaten die richtige Einfügeposition für den neuen Knoten bestimmt. Hierbei ist der Sortieralgorithmus zu beachten (aufsteigend oder absteigend etc.).
*Wenn die richtige Position Stelle gefunden ist, wird ein neuer Knoten erzeugt. Der Zeiger des vorausgegangenen Knoten wird auf den neu eingefügten Knoten gesetzt und der Zeiger des eingefügten Knotens auf den nachfolgenden Knoten. Entsprechend wird bei einer beidseitigen verketteten Liste auch der Rückzeiger versetzt.
[[Bild:S3alhaes_Knoten_einfügen.jpg | thumb | center |500px | Abb.1: Einfügen eines Knoten]]
Das Entfernen eines Datenelements verläuft analog: Auffinden des gesuchten Elements, dann Zeiger versetzen und Element löschen. Auch hierbei muss insbesondere das Versetzen der Zeiger sorgfältig programmiert werden, um das Zerbrechen der Liste und damit Datenverlust zu vermeiden.
====Vorgehensweise====
Eine sortierte Liste kann mit unterschiedlichen Algorithmen zum Auffinden der passenden Einfüge- bzw. Löschposition implementiert werden.
*Beim Durchlaufen der Liste wird nur ein einziger Suchzeiger benutzt. Zum Einfügen oder Löschen eines Elements muss dann jedoch ein temporärer Hilfszeiger verwendet werden, der die Adresse des folgenden Elements zwischenspeichert, bis die Operation abgeschlossen ist.
*Auf den temporären Hilfszeiger kann verzichtet werden, wenn zwei Suchzeiger zum Durchlaufen der Liste benutzt werden. Sie laufen im Schrittabstand parallel und zeigen auf die benachbarten Elemente.
=====temporärer Hilfszeiger=====
Im folgenden Beispiel soll der Datensatz "3" in eine sortierte Liste eingefügt werden. Der Suchzeiger steht zu Beginn am Listenkopf.
[[Bild:S3alhaes_Temp_zeiger_1.jpg | thumb | center |500px | Abb.2: Schritt 1]]
Zum Auffinden der richtigen Einfügeposition rückt der Suchzeiger elementweise weiter. Dabei wird über den next-Zeiger das jeweils folgende Element geprüft, ob es grösser oder kleiner ist als das Einzufügende.
[[Bild:S3alhaes_Temp_zeiger_2.jpg | thumb | center |500px | Abb.3: Schritt 2]]
Wenn die Bedingung zutrifft, dann ist die richtige Einfüge-Position für das neue Element (3) gefunden. Nachdem das neue Element erzeugt wurde, kann der next-Zeiger des aktuellen Elements umgesetzt werden. Dies darf allerdings erst geschehen, nachdem ein temporärer Hilfszeiger (temp) die Adresse des nachfolgenden Elements gesichert hat. Dann kann der next-Zeiger des vorhergehenden Elements auf die Adresse des neuen Elements gesetzt werden und der next-Zeiger des neuen Elements auf die Adresse des nachfolgenden Element, die im temporären Hilfszeiger aufbewahrt worden ist. Der Hilfszeiger wird danach nicht mehr gebraucht.
[[Bild:S3alhaes_Temp_zeiger_3.jpg | thumb | center |500px | Abb.4: Schritt 3]]
=====zwei ständige Zeiger=====
Beim Durchlaufen der Liste können alternativ auch zwei Zeiger eingesetzt werden. Am Beginn des Suchlaufs zeigen beide Zeiger zunächst gemeinsam auf den Listenkopf.
[[Bild:S3alhaes_Zwei_zeiger_1.jpg | thumb | center |500px | Abb.5: Schritt 1]]
Beim folgenden Suchvorgang zeigt der nachfolgende Zeiger auf den jeweils vorhergehenden Knoten (weil dessen next-Zeiger auf den neuen Knoten umgesetzt werden muss) und der Suchzeiger auf den aktuellen Knoten. So durchläuft der search-Zeiger die Liste knotenweise bis zum Ende und vergleicht dabei die Daten jedes Knotens mit den Daten des einzufügenden Knotens. Der last-Zeiger bleibt also immer eine Position zurück.
[[Bild:S3alhaes_Zwei_zeiger_2.jpg | thumb | center |500px | Abb.6: Schritt 2]]
Wenn die passende Position für den neuen Knoten in der sortierten Liste gefunden ist, dann wird der next-Zeiger des last-Knotens auf den neuen Knoten gesetzt und der next-Zeiger des eingefügten Knotens auf den search-Knoten. Damit ist der neue Knoten in der sortierten Liste an der richtigen Position verankert.
[[Bild:S3alhaes_Zwei_zeiger_3.jpg | thumb | center |500px | Abb.7: Schritt 3]]
===Beispiele für sortierte Listen===
====Binäre Suchbäume====
=====AVL-Bäume=====
=====Rot-Schwarzbäume=====
=====Randomisierte Suchbäume=====
====skip-Listen====
====Sparse Table====