Suchen in Listen, Einfügen, Sortieren

Synopsis: Durchsuchen von Liste

Kennst Du?

Eine Methode Merker.kennstDu(n: GZ):Text soll folgendes Verhalten zeigen:

Wird eine bereits gemerkte, bekannte Zahl eingegeben, gibt sie "Kenn ich!" zurück.
Ist die Zahl unbekannt, wird sie gemerkt und es wird zurückgegeben: "Kenn ich nicht!".
Ist der Speicher voll, wird er verdoppelt und es wird zurückgegeben: "Speicher verdoppelt: "

public class Merker{
  int zahl[] = new int[3];
  int eFindex = 0; // erster freier Index
  String kennstDu(int n){
  }
}

Entwickeln Sie die Methode und ein Struktogramm. Lösung...

Wie viele Vergleiche müssen bei 50 Einträgen durchschnittlich getätigt werden? Diskutieren Sie ihren Ansatz.

Analyse des Aufwands durch Messung

Um den Aufwand zu messen machen wir ein Experiment. 100 zufällige Zahlen im Bereich 1..n werden erzeugt und gemerkt, dabei wird die Anzahl der Vergleiche bei der Suche gemessen. Drei Verfahren sollen Verglichen werden: Quelltext

Analysieren Sie die Effizienz der Verfahren und machen sich mit den Prinzipien vertraut.

Sortieren der Liste mit Bubble-Sort

void bubbleSort(){
  boolean unordnung;
  int i=1,k, temp;
  do{
    unordnung = false; // wir gehen von Ordnung aus
    for (k= zahl.length-1; k>=i; k--){
      if (zahl[k-1]>zahl[k]){  // wenn es nicht ordentlich ist,
        temp=zahl[k];          // wird getauscht
        zahl[k]=zahl[k-1];
        zahl[k-1]=temp;
        unordnung = true;
      }
    }
    i++;
  }while (unordnung); // wiederhole solange noch getauscht werden muss
}