class Erbsen {


  /**
   * Das Array erbse[] enthaelt alle Erbsen (=Zahlen)
   * (der "grosse" Haufen).*/
  private static int[] erbse;
  /**
   * In dem Array gute[] sollen am Ende die groesseren
   * Erbsen sein. (der Haufen mit den "guten" Erbsen)*/
  private static int[] gute;
  /**
   * In dem Array schlechte[] sollen am Ende die kleineren
   * Zahlen stehen. (der Haufen mit den "schlechten" Erbsen)*/
  private static int[] schlechte;

  /**
   * Die Anzahl der Erbsen. Diese Zahl wird beim Aufruf des
   * Konstruktors uebergeben.*/
  static int AnzahlErbsen;



  /**                     Konstruktor
   *
   * In einem Konstruktor werden globale Variablen initialisiert,
   * d.h. auf bestimmte Werte gesetzt.
   * In diesem Fall werden die Arrays je nach Anzahl Erbsen erzeugt
   * und das Array erbse[] wird mit zufaellig erzeugten Werten
   * zwischen 100-999 gefuellt.
   *
   */
  public Erbsen(int n) {

    AnzahlErbsen = n;
    erbse     = new int[AnzahlErbsen];
    gute      = new int[(AnzahlErbsen+1)/2];
    schlechte = new int[(AnzahlErbsen+1)/2];

    // Erzeugen der Zufallszahlen und Fuellen des Arrays erbsen[].
    for(int i=0;i<AnzahlErbsen;i++){
      erbse[i]=(int)(java.lang.Math.random()*899+100);
    }
    // Infos schreiben
    System.out.println("\nQuicksort Algorithmus, Fabian Wleklinski, 30.11.1998");
    java.util.Date date = new java.util.Date();
    System.out.println("\n"+date.toString());
  }

  // der klassische Quicksort (rekursiv)
  static void Quicksort( int [] elements, int min, int max ) {

    if (max > min) {

      int i = min;
      int j = max;

      int x = elements[ (min + max) / 2 ];
      do {
        while ( elements[ i ] < x ) i++;
        while ( elements[ j ] > x ) j--;

        if (i <= j) {
          int temp = elements[ i ];
          elements[ i ] = elements[ j ];
          elements[ j ] = temp;
          i++;
          j--;
        }
      }

      while (i <= j);

      Quicksort( elements, min, j );
      Quicksort( elements, i, max );
    }
  }


  /** Das ist eure Aufgabe: */
  static void Aschenbroedel() {

    /* In dieser Methode sollen die Erbsen aufgeteilt werden
     * auf einen guten und einen schlechten Haufen, d.h. auf
     * die beiden Arrays gute[] und schlechte[]. Bei ungerader
     * Anzahl Erbsen soll eine mehr auf den guten Haufen.
     */

    // Quicksort auf das Array Erbse anwenden
    Quicksort( erbse, 0, erbse.length - 1 );

    // Das Array "erbse" in "gute" und "schlechte" aufteilen
    for (int i=0; i<(erbse.length)/2; i++)
      schlechte[ i ] = erbse[ i ];

    int j=0;
    for (int i=(erbse.length)/2; i<erbse.length; i++){
      gute[ j ] = erbse[ i ];
      j++;
    }

  }


  /** Main-Methode */
  public static void main(String argv[]) {


    /* Aufruf des Konstruktors und Uebergabe der Anzahl Erbsen */
    Erbsen erbs = new Erbsen(51);

    // Ausgabe der zufaellig erzeugten Zahlen
    System.out.println("\n------------------ Alle Erbsen : ------------------");
    for(int i=0;i<AnzahlErbsen;i++) {
      System.out.print(erbse[i]+"   ");
      // zur besseren Lesbarkeit:
      if((i+1)%
      15==0)
	System.out.println();
    }

    System.out.println("\n\nSortiere jetzt!\n");

    /* Aufruf der "Aus einem Haufen mach zwei Haufen"-Methode    ;-) */
    Aschenbroedel();


    System.out.println("\n------------------- Die guten: --------------------");
    for(int i=0;i<(int)(AnzahlErbsen+1)/2-1;i++) {
      System.out.print(gute[i]+"   ");
      if((i+1)%15==0)
        System.out.println();
    }
    if(gute[(AnzahlErbsen+1)/2-1]!=0)
      System.out.println(gute[(AnzahlErbsen+1)/2-1]);

    System.out.println("\n----------------- Die schlechten:  ----------------");
    for(int i=0;i<(int)(AnzahlErbsen+1)/2-1;i++) {
      System.out.print(schlechte[i]+"   ");
      if((i+1)%15==0)
	System.out.println();
    }
    if(schlechte[(AnzahlErbsen+1)/2-1]!=0)
      System.out.println(schlechte[(AnzahlErbsen+1)/2-1]);

    System.out.println("\n\nSo, das wars\n");
    }
  }