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


  // Initialisierung des Feldes
  n = IOTools.readInteger("Bitte die Feldgroesse eingeben: ");
  feld = new int[n];
  System.out.println();
  for (i=0; i<feld.length; i++) 
    feld[i] = IOTools.readInteger("Bitte a[" + i + "] eingeben: ");
  System.out.println();
  
  // Ausgabe
  for (i=0; i<feld.length; i++) 
    System.out.print(feld[i] + "  ");
  System.out.println();

  // Partition
  i = 0;
  j = feld.length - 1;
  
  x = feld[(i + j)/2]; // prinzipiell beliebiges Element moeglich!
  System.out.println("Pivotelement: " + x);
  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); 
  System.out.println("Indexueberschneidung bei i = " + i + " und j = " + j);
 
  // Ausgabe
  for (i=0; i<feld.length; i++) 
    System.out.print(feld[i] + "  ");
  System.out.println();
  return;
  }
}