Suchfunktion

3.3.2.2 Algorithmen auf Datenstrukturen

Algorithmen zur Verarbeitung größerer Datenmengen setzen voraus, dass die Daten in einer geeigneten Struktur vorliegen. Für viele Algorithmen spielen dabei die Grundprobleme Suchen, Traversieren und Sortieren eine Rolle.

Suchverfahren werden benutzt, um die Existenz und die Position eines Elements in einer Datenstruktur zu ermitteln (zum Beispiel bei der Artikelsuche in einem Webshop, bei der Rufnummernsuche im Telefonbuch, bei der Webrecherche). Die Schülerinnen und Schüler verwenden abhängig von der jeweiligen Problemstellung und Datenstruktur (zum Beispiel Array, Baum) unterschiedliche Verfahren (lineare und binäre Suche, Breiten- und Tiefensuche).

Sortierverfahren spielen in der Informatik eine große Rolle, da viele Algorithmen effizienter arbeiten, falls die Daten sortiert vorliegen. Dies lässt sich mithilfe von einfachen Sortierverfahren wie Selectionsort oder höheren Sortierverfahren wie Quicksort lösen.

Für ein und dasselbe Problem gibt es oftmals verschiedene Lösungsverfahren, die sich in Speicher- und Zeitkomplexität sowie – bei Näherungsverfahren – in der Genauigkeit der Lösung unterscheiden. Neben klassischen Such- und Sortierproblemen werden auch komplexere Problemstellungen untersucht.

Die Schülerinnen und Schüler können

Fußleiste