Sortierte Folgen WS13-14

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

M sei die Menge der ganzen Zahlen und die gegebene Ordung “<” auf M ist die übliche größer/kleiner Beziehung zwischen zwei ganzen Zahlen.

1. Die gegebene, aufsteigend sortierte Folge sei:

Gesucht werden soll nach k = 35.

Die gewünschte Ausgabe ist der Index 8.

2. Die gegebene, aufsteigend sortierte Folge sei:

Gesucht werden soll nach k = 17.

Die gewünschte Ausgabe ist nicht enthalten.

M sei die Menge der Wörter der deutschen Sprache und die gegebene Ordung “<” auf M ist die Reihenfolge, in der die Wörter im Duden erscheinen (im Folgenden 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.