import Prog1Tools.IOTools;
public class Find2{
  public static void main(String[] args) {
  int [] feld;
  int i, j, k, x, n, links, rechts, temp;
  int zzAlt, zzNeu, a, c, m;

  // Initialisierung des Zufallszahlengenerators
  System.out.println("Initialisierung des ZZ-Generators");
  zzAlt = IOTools.readInteger("Bitte den Seed eingeben: ");
  a = IOTools.readInteger("Bitte a eingeben: ");
  c = IOTools.readInteger("Bitte c eingeben: ");
  m = IOTools.readInteger("Bitte m eingeben: ");
  System.out.println();

  // Initialisierung des Feldes
  n = IOTools.readInteger("Bitte die Feldgroesse eingeben:");
  feld = new int[n];
  for (i=0; i<feld.length; i++) {
    zzNeu = ((a * zzAlt) + c) % m;
    // Achtung! Werden nur pos. Zahlen gewuenscht, dann folg. einkommentieren:
    if (zzNeu < 0)
      zzNeu = zzNeu + m;
    zzAlt=zzNeu;
    feld[i]=zzNeu;
  }
  System.out.println();

  // Initialisierung von k
  System.out.println("Bitte k eingeben (0 <= k < " + n + ")");
  System.out.println("0 steht dabei fuer das kleinste Element");
  System.out.println((n-1) + " steht fuer das groesste Element"); 
  k = IOTools.readInteger("k = ");
  System.out.println();
  
  // Ausgabe
  for (i=0; i<feld.length; i++) 
    System.out.print(feld[i] + "  ");
  System.out.println();


  // Find
  links = 0;
  rechts = feld.length-1;
  while (links < rechts) {
    i = links;
    j = rechts;
    x = feld[k];
    
    // Aufteilen
    do {
      while (feld[i] < x) 
        i++;    // Suche von links her
      while (feld[j] > x)
        j--;    // Suche von rechts her
      if (i <= j) {
        temp = feld[i];
        feld[i] = feld[j];
        feld[j] = temp;
        i++;
        j--;
      } 
    } while (i <= j); 
    if (j < k)
      links = i;
    if (k < i)
      rechts = j;
  }
  // Ausgabe
  for (i=0; i<feld.length; i++) 
    System.out.print(feld[i] + "  ");
  System.out.println();
  System.out.println("Das " + k + "-kleinste Element ist " + feld[k]);
  return;
  }
}