Sortierte Folgen WS13-14

Aus ProgrammingWiki

Archivierte Version vom 2013-12-12T14:04:35+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Einleitung
- 1.1 Sortierte Folgen
- 1.2 Verwendung
2 Suchen in einer sortierten Folge

Autoren: Dominik Bitterlich; 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 enthalten“ 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

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;
}

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);
}

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

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;
}

Man erhält: T(n) = 5n + 3

Laufzeit im worst case auf einer verketteten List

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;
   }

Man erhält: T(n) = 6n + 4