AuK/Sortierte Folgen WS13-14

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===

==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'''.

<language>Java</language>
====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.outprintln ("Gefundener Index:  "+result);
}
}

</run>

====Umsetzung in Java auf einer verketteten Liste====