Zum Inhalt springen
Topos Uranos
Deutsch

Suchen und Sortieren

Zusammenfassung

Suchen und Sortieren sind die beiden grundlegenden Probleme auf Sammlungen, und zwischen ihnen besteht ein Tauschgeschäft: Einmal zu sortieren kostet etwas, verbilligt aber jede spätere Suche. Die Lektion schreibt von Hand die lineare und die binäre Suche, die auf sortierten Daten in jedem Schritt die Hälfte verwirft; sie begründet die binäre Suche mit ihrer Invariante, beweist, dass sie terminiert, zählt ihre Durchläufe und untersucht die drei Fehler, die sie zunichtemachen. Es folgen das Sortieren durch Auswahl und durch Einfügen, mit ihren Invarianten und der genauen Zählung ihrer Vergleiche; danach dieselben Probleme mit der Ranges-Bibliothek, und die Rechnung, die entscheidet, wann es sich lohnt, vor dem Suchen zu sortieren.

Lernziele

  1. Die lineare und die binäre Suche implementieren und die binäre mit ihrer Invariante begründen („ist der Wert vorhanden, so liegt er zwischen low und high“), samt dem Beweis, dass sie terminiert.
  2. Das Sortieren durch Auswahl und durch Einfügen implementieren, die Invariante jedes Verfahrens formulieren und ihre Vergleiche im besten und im schlechtesten Fall zählen.
  3. std::ranges::sort, std::ranges::contains, std::ranges::find, std::ranges::binary_search und std::ranges::lower_bound gegebenenfalls anstelle der eigenen Fassungen verwenden und dabei ihre Vorbedingungen beachten.
  4. Je nach Anzahl der vorgesehenen Suchen entscheiden, ob es sich lohnt, die Daten vor dem Suchen zu sortieren, und die Entscheidung mit der Zählung der Vergleiche begründen.

Lineare Suche

Suchen heißt, zu einer gegebenen Sammlung und einem Wert zu beantworten, ob der Wert vorhanden ist und wo. Ohne Information über die Ordnung der Daten gibt es keine andere Strategie, als sie einzeln anzusehen: Das ist die lineare Suche. Ist der Wert nicht vorhanden, so gibt dieser Kurs values.size() zurück, die erste Position, die nicht zum Vektor gehört: Sie ist kein gültiger Index, sodass sie nicht mit einer Antwort verwechselt wird, und sie ist dieselbe Konvention, der die Bibliothek folgt, wie sich im fünften Teil der Lektion zeigen wird.

C++-Programm
#include <cstddef>#include <print>#include <vector>​// Vorbedingung: keine.// Nachbedingung: gibt den kleinsten Index i mit values[i] == target zurück,// oder values.size(), wenn target nicht vorhanden ist.std::size_t linearSearch(const std::vector<int>& values, int target){    // Invariante: target ist nicht in values[0], ..., values[i - 1].    for (std::size_t i{0}; i < values.size(); ++i) {        if (values[i] == target) {            return i;        }    }    return values.size();}​int main(){    const std::vector<int> codes{405, 112, 318, 207, 112, 530};    for (const int target : {207, 112, 999}) {        const std::size_t pos{linearSearch(codes, target)};        if (pos == codes.size()) {            std::println("{}: nicht vorhanden", target);        } else {            std::println("{}: Position {}", target, pos);        }    }}
Ausgabe
207: Position 3112: Position 1999: nicht vorhanden

Die Invariante in Zeile 10 liefert die Korrektheit. Zu Beginn, mit i gleich 0, sagt sie etwas über ein leeres Teilstück aus und ist wahr. Gilt sie zu Beginn eines Durchlaufs und ist values[i] nicht der gesuchte Wert, so gilt sie an dessen Ende mit einem Element mehr. Nun hat die Schleife zwei Ausgänge: Wird return i; ausgeführt, so ist values[i] der gesuchte Wert und, nach der Invariante, war es kein früheres Element, woraus folgt, dass i das erste Vorkommen ist (deshalb wird die 112, die zweimal vorkommt, an Position 1 gemeldet); endet die Schleife über ihre Bedingung, so ist i gleich values.size(), und die Invariante sagt, dass der Wert nirgends vorhanden ist. Das return innerhalb der Schleife beendet die Funktion und mit ihr die Schleife, und es erspart ein Flag.

Gemessen werden die Kosten, im Sinne der Lektion Die Kosten eines Algorithmus, an den Vergleichen values[i] == target. Ist der Wert nicht vorhanden, so werden genau nn ausgeführt, einer pro Element: der schlechteste Fall. Steht er an Position pp, so sind es p+1p + 1. Die lineare Suche ist also O(n)O(n): doppelt so viele Daten, doppelt so viel Arbeit. Ohne zusätzliche Information geht es nicht besser: Ein Algorithmus, der ein Element nicht ansähe, wüsste nicht, ob der Wert dort stand.