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

  // Initialisierung des Feldes 
  n = IOTools.readInteger("Bitte Feldgroesse eingeben: ");
  feld = new int[n];
  for (i=0; i<feld.length; i++) 
    feld[i]=IOTools.readInteger("Bitte a[" + i + "] eingeben:");
  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;
  }
}