public class Merker2{
  final int SPEICHER = 1000; // Listengroesse und Anzahl der Zufallszahlen
  int zahl[] = new int[SPEICHER];
  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: "+SPEICHER);
      System.out.println("Bereich: 1.."+bereich+" Vergleiche: "+vergleiche+" Gemerkte Zahlen: " +eFindex);
      System.out.println("--------------------------------------");
      i++;
    }
  }
  
  void messe(int kandidat,int bereich){
    int i,zufall;
    zahl = new int[SPEICHER];
    eFindex = 0;
    vergleiche = 0;
    i = 0;
    while(i<SPEICHER){
      zufall = (int)(Math.random()*bereich);
      if (zufall == 0){
        //System.out.println("Zufallszahl ist 0");
      }
      else {
        switch (kandidat){
          case 0: vergleiche += kennstDu(zufall); break;
          case 1: vergleiche += kennstDu2(zufall); break;
          case 2: vergleiche += kennstDu3(zufall); break;
        }  
        i++;
      }
    }
  }
  
  int kennstDu(int n){
    int i=0;
    while ( i< eFindex){ // solange Merkzahlen
      if (n == zahl[i])  // gefunden
        return i;
      i++;    
    }
    zahl[eFindex++]=n; // neue Zahl hinten anfuegen
    return i;
  }
  
  int kennstDu2(int n){  // sortiertes Einfuegen
    int k,i=0;
    while (i< eFindex && zahl[i] < n) i++; // laufe, bis moegliche Vergleichszahl
    if (n == zahl[i])  // gefunden
      return i;
    for (k=eFindex;k>i;k--) // Platz an Position i schaffen um neue Zahl einzufuegen
      zahl[k]=zahl[k-1];     
    zahl[i]=n; // neue Zahl einfuegen
    eFindex++;
    return i;
  }
  
  int kennstDu3(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 < zahl[m]){
        r = m - 1;
        e=m; // Einfuegeposition merken
      }  
      else if(n > zahl[m])
        e=l = m + 1;
      else  // gefunden
        return i;		
    }
    for (k=eFindex;k>e;k--) // Platz an Position e schaffen um neue Zahl einzufuegen
      zahl[k]=zahl[k-1];     
    zahl[e]=n;
    eFindex++;
    return i;
  }
}