Informatik am GSG

Untersuchen Sie, ob man beide Algorithmen auf beide Reihungen anwenden kann.

Die beiden Algorithmen finden in verschiedenen Situationen einen bestimmten Wert in einer Reihung.
Nun untersuchen Sie, wie aufwendig die beiden Verfahren im Vergleich zueinander sind. Wenn man die Laufzeit eines Algorithmus untersuchen möchte, kann man die Dauer, wie lange dieser Algorithmus läuft, zählen. Die Ausführungszeit wird in der Online-IDE immer ausgegeben, wenn ein Programm vollständig abgelaufen ist:

Implementieren Sie ein Programm Suchalgorithmen, in dem es beide Suchoperationen als Operationen gibt.
Testet die Operationen mit einer Ganzzahl-Reihung von Zufallszahlen der Größe 20 und einer sortierten Ganzzahl-Reihung der Größe 20.

Jetzt soll untersucht werden, wie sich die Laufzeit in Abhängigkeit der Anzahl der Elemente in den Reihungen verändert.
Die folgenden Operationen helfen bei der Erzeugung von Reihung mit Zufallszahlen und geben diese zurück.

public int lineareSuche(int[] reihung, int gesucht) {
    for (int i = 0; i < reihung.length; i++) {
        if (reihung[i] == gesucht) {
            return i;
        }
    }
    return -1;
}

public int binaereSuche(int[] reihung, int gesucht) {
    int links = 0;
    int rechts = reihung.length - 1;
    while (links <= rechts) {
        int mitte = links + (rechts - links) / 2;
        if (reihung[mitte] == gesucht) {
            return mitte;
        } else {
            if (reihung[mitte] < gesucht) {
                links = mitte + 1;
            } else {
                rechts = mitte - 1;
            }
        }
    }
    return -1;
}

public int[] sortierteReihung(int anzahl) {
    int[] reihe = new int[anzahl];
    int count = 0;
    while (count < anzahl) {
        int zufallszahl = (int) (Math.random() * reihe.length);
        if (!istInReihe(reihe, zufallszahl, count)) {
            reihe[count] = zufallszahl;
            count++;
        }
    }
    // Sortiere die Reihe
    bubbleSort(reihe);
    return reihe;
}

public int[] zufallsReihung(int anzahl) {
    int[] reihe = new int[anzahl];
    int count = 0;
    while (count < anzahl) {
        int zufallszahl = (int) (Math.random() * reihe.length);
        if (!istInReihe(reihe, zufallszahl, count)) {
            reihe[count] = zufallszahl;
            count++;
        }
    }
    return reihe;
}

// Prueft, ob eine Zahl bereits in der Reihe vorhanden ist
private boolean istInReihe(int[] reihe, int zahl, int count) {
    for (int i = 0; i < count; i++) {
        if (reihe[i] == zahl) {
            return true; // Zahl ist bereits vorhanden
        }
    }
    return false; // Zahl ist nicht vorhanden
}

// Bubble Sort Methode
public void bubbleSort(int[] array) {
    int n = array.length;
    boolean swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                // Vertausche die Elemente
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

Operationen zur Erstellung von Ganzzahl-Reihung

Erweitern Sie Ihr Programm so, dass Sie zunächst

• für eine nicht sortierte Reihung die Laufzeit mit der linearen Suche und für eine sortierte Reihung die Laufzeit mit der binären Suche messen und aufschreiben.
• Anschließend sollen 10.000 Durchgänge gemessen, dann die durchschnittliche Laufzeit berechnet und aufgeschrieben werden.

In dieser Teilaufgabe untersuchen Sie theoretisch die Veränderung der Laufzeit, in Abhängigkeit der Größe der Reihung.
Untersuchung der linearen Suche:
Angenommen, eine unsortierte Reihhung hat 5 Elemente:

Überlegen Sie, wie häufig die lineare Suche eine Zahl in den folgenden Fällen vergleichen muss:

• Die Zahl 5 wird gesucht.
• Die Zahl 4 wird gesucht.
• Die Zahl 1 wird gesucht.

Nun verdoppelt sich die Anzahl der Elemente in der Reihung:

Geben Sie an, wie sich der Aufwand verändert, wenn 5, 4 oder 6 gesucht werden.

Untersuchung der binären Suche:
Angenommen, eine sortierte Reihhung hat 5 Elemente:

Überlegen Sie, wie häufig die binäre Suche eine Zahl in den folgenden Fällen vergleichen muss:

• Die Zahl 5 wird gesucht.
• Die Zahl 2 wird gesucht.
• Die Zahl 9 wird gesucht.

Nun verdoppelt sich die Anzahl der Elemente in der Reihung:

Geben Sie an, wie sich der Aufwand verändert, wenn 4, 7 oder 0 gesucht werden.

Ordnen Sie die folgenden Aussagen einem der beiden Suchverfahhren zu:

1. Im schlimmsten Fall müssen alle n Elemente durchsucht werden, was zu einer maximalen Anzahl von Vergleichen führt. Dies bedeutet, dass die Anzahl der Vergleiche linear zur Größe der Reihung wächst.
2. Bei jedem Vergleich wird die Größe des Suchraums halbiert.
3. Es wird ein Teile-und-Herrsche-Ansatz verwendet, bei dem das Suchproblem in kleinere Teilprobleme zerlegt wird.
4. Diese Suche funktioniert bei alle, auch unsortierten, Reihungen.

Effizienz der Binären Suche

1. Teile-und-Herrsche-Ansatz: Die binäre Suche verwendet einen Teile-und-Herrsche-Ansatz, bei dem das Suchproblem in kleinere Teilprobleme zerlegt wird. Sie vergleicht das gesuchte Element mit dem mittleren Element der Reihung und entscheidet basierend auf diesem Vergleich, ob das gesuchte Element in der linken oder rechten HälOe der Reihung liegt.
2. Reduzierung des Suchraums: Bei jedem Vergleich wird die Größe des Suchraums halbiert.
3. Effzienz bei großen Datenmengen: Aufgrund der Wachstumsrate ist die binäre Suche besonders effizient bei großen Datenmengen. Selbst bei sehr großen Reihungen bleibt die Anzahl der nötigen Vergleiche relativ gering.

Ineffizienz der Linearen Suche

1. Einfachheit: Die lineare Suche ist ein einfacher Algorithmus, der jedes Element der Reihung der Reihe nach durchläuft, bis das gesuchte Element gefunden wird oder das Ende der Reihung erreicht ist.
2. Vollständige Durchsuchung: Im schlimmsten Fall muss die lineare Suche alle ( n ) Elemente durchsuchen, was zu einer maximalen Anzahl von Vergleichen führt. Dies bedeutet, dass die Anzahl der Vergleiche linear zur Größe der Reihung wächst.
3. Unsortierte Daten: Da die lineare Suche keine Annahmen über die Anordnung der Elemente trifft, ist sie bei unsortierten Daten die einzige Möglichkeit, um sicherzustellen, dass das gesuchte Element gefunden wird. Dies führt dazu, dass sie ineffizienter ist, insbesondere wenn die Reihung groß ist.

Fazit
Die binäre Suche ist effizienter als die lineare Suche, da sie die Anzahl der Vergleiche reduziert, indem sie den Suchraum bei jedem Schritt halbiert. Dies macht sie besonders gut geeignet für große, sortierte Datenmengen. Die lineare Suche hingegen ist ineffizient für große oder unsortierte Datenmengen, da sie im schlimmsten Fall alle Elemente durchsuchen muss.