Listen: Einfügen, Suchen, Sortieren

public class MerkerSuche{
  static int[] speicher = new int[3]; // Speicherliste
  static int eFindex; // = 0; // erster freier Index
  static void anhaengen(int n){
    if (eFindex >= speicher.length)
      verdoppleSpeicher();
    speicher[eFindex++]=n;
  }
  static void vorneEinfuegen(int n){
    int i;
    if (eFindex >= speicher.length)
      verdoppleSpeicher();
    for(i=eFindex;i>0;i--){  // nach hinten verschieben
      speicher[i]=speicher[i-1];
    }
    speicher[0]=n;
    eFindex++;
  }
  static void merke(int n){
    int i;
    for(i=0;i<eFindex;i++){ 
      if(speicher[i]==n) // wenn schon bekannt
        return; // Operation verlassen
    }
    if (eFindex >= speicher.length)
      verdoppleSpeicher();
    speicher[eFindex++]=n;
  }
  static void verdoppleSpeicher(){
    int[] neu= new int[speicher.length*2]; // neue Liste erzeugen
    int i;
    for (i=0;i<speicher.length;i++) // in neue Liste kopieren
      neu[i]=speicher[i];
    speicher=neu;  // Verweis nun auf neue Liste
    System.out.println("Speicher verdoppelt: "+speicher.length);
  }
  static void bubbleSort(){
    boolean unordnung;
    int i=1,k, temp;
    do{
      unordnung = false; // wir gehen von Ordnung aus
      for (k= eFindex-1; k>=i; k--){
        if (speicher[k-1]>speicher[k]){  // wenn es nicht ordentlich ist,
          temp=speicher[k];          // wird getauscht
          speicher[k]=speicher[k-1];
          speicher[k-1]=temp;
          unordnung = true;
        }
      }
      i++;
    }while (unordnung); // wiederhole solange noch getauscht werden muss
  }
  static void test(){
    merke(23);
    merke(12);
    merke(20);
    merke(3);
    merke(1);
    bubbleSort();
  }
  static boolean suche(int n){ // lineares Suchen
    int i=0;
    while (i< eFindex && speicher[i] < n) i++; // laufe, bis moegliche Vergleichszahl
    return speicher[i] == n; // gefunden oder nicht
  }
  static boolean sucheBinaer(int n){ // binaeres Suchen
    int r,l,m=0,e=0,k;
    l = 0;  // linke Marke
    r = eFindex - 1;  // rechte Marke
    while(l <= r){  // solange noch durchsuchbarer Bereich
      m = (r + l) / 2; // Mitte zwischen den Marken
      if(n < speicher[m]){ // unter der Mitte?
        r = m - 1;
      }  
      else if(n > speicher[m]) // ueber der Mitte?
        l = m + 1;
      else  // gefunden
        return true;		
    }
    return false; // nix gefunden
  }
}

public class MerkerEffizienz{
  final int SPEICHERGROESSE = 1000; // Listengroesse und Anzahl der Zufallszahlen
  int speicher[] = new int[SPEICHERGROESSE];
  int eFindex = 0; // erster freier Index
  int vergleiche = 0; // Anzahl der Vergleiche
  final String VERFAHREN[] = {"Ungeordnete Liste","Sortiertes Einfuegen linear","Sortiertes Einfuegen mit binaerer Suche"};
 
  void messung(int bereich){ // alle Verfahren messen
    int i=0;
    while (i< VERFAHREN.length){ // fuer alle Verfahren
      messe(i,bereich);
      System.out.println(VERFAHREN[i]+" Listengroesse und Anzahl Zufallszahlen: "+SPEICHERGROESSE);
      System.out.println("Bereich: 1.."+bereich+" Vergleiche: "+vergleiche+" Gemerkte Zahlen: " +eFindex);
      System.out.println("--------------------------------------");
      i++;
    }
  }
 
  void messe(int kandidat,int bereich){
    int i,zufall;
    speicher = new int[SPEICHERGROESSE];
    eFindex = 0;
    vergleiche = 0;
    i = 0;
    while(i<SPEICHERGROESSE){
      zufall = (int)(Math.random()*bereich);
      if (zufall == 0){
        //System.out.println("Zufallszahl ist 0");
      }
      else {
        switch (kandidat){
          case 0: vergleiche += merke(zufall); break;
          case 1: vergleiche += merke2(zufall); break;
          case 2: vergleiche += merke3(zufall); break;
        }  
        i++;
      }
    }
  }
 
  int merke(int n){
    int i=0;
    while ( i< eFindex){ // solange Merkzahlen
      if (n == speicher[i])  // gefunden
        return i;
      i++;    
    }
    speicher[eFindex++]=n; // neue Zahl hinten anfuegen
    return i;
  }
 
  int merke2(int n){  // sortiertes Einfuegen
    int k,i=0;
    while (i< eFindex && speicher[i] < n) i++; // laufe, bis moegliche Vergleichszahl
    if (n == speicher[i])  // gefunden
      return i;
    for (k=eFindex;k>i;k--) // Platz an Position i schaffen um neue Zahl einzufuegen
      speicher[k]=speicher[k-1];     
    speicher[i]=n; // neue Zahl einfuegen
    eFindex++;
    return i;
  }
 
  int merke3(int n){  // sortiertes Einfuegen mit binaerer Suche
    int r,l,m=0,e=0,k,i=0;
    l = 0;  // linke Marke
    r = eFindex - 1;  // rechte Marke
    while(l <= r){  // solange noch durchsuchbarer Bereich
      i++;  // Vergleichszaehler
      m = (r + l) / 2; // Mitte zwischen den Marken
      if(n < speicher[m]){
        r = m - 1;
        e=m; // Einfuegeposition merken
      }  
      else if(n > speicher[m])
        e=l = m + 1;
      else  // gefunden
        return i;		
    }
    for (k=eFindex;k>e;k--) // Platz an Position e schaffen um neue Zahl einzufuegen
      speicher[k]=speicher[k-1];     
    speicher[e]=n;
    eFindex++;
    return i;
  }
}