// tri_rapide.java
import java.io.*;
import java.util.*;
class CTabvaleurs { // Attributs
  static final int TAILLE=50;
  private int[] tab_valeurs ;
  private int nbval         ;
  private int val_gauche    ;
  private int val_droite    ;
  // Constructeur
  CTabvaleurs()
  {tab_valeurs=new int[TAILLE];nbval=0;val_gauche=-1;val_droite=-1;}
  // Autres méthodes
  public int gauche()
  {if (val_gauche==-1) val_gauche=0;return val_gauche;}
  public int droite()
  {if (val_droite==-1) val_droite=nbval-1;return val_droite;}
  public void affichage(int debut, int fin)
  { for (int i=debut ; i<=fin ; i++)
        System.out.printf("%4d", tab_valeurs[i]) ;
    System.out.printf("\n") ;
  }
  public void chargement()
  { int val=0;
    System.out.printf("Liste de valeurs entières ") ;
    System.out.printf("(-1 pour fin) : \n")         ;
    Scanner Entree = new Scanner(System.in)         ;
    while (val != -1)
    { val=Entree.nextInt()                    ;
      if (val != -1) tab_valeurs[nbval++]=val ;
    }
    Entree.close();
  }
  public void tri_rapide(int _gauche, int _droite)
  { if (_gauche < _droite)
    { int pivot=partition(_gauche,_droite) ;
      tri_rapide(_gauche,pivot-1)          ;
      tri_rapide(pivot+1,_droite)          ;
    }
  }
  public int partition(int _gauche, int _droite)
  { int clef=tab_valeurs[_droite];
    int i=_gauche-1;
    int j=_droite  ;
    while (i<=j)
    { while (((++i)<_droite)&&(tab_valeurs[i]<clef))    ;
      while (((--j)>(_gauche-1))&&(tab_valeurs[j]>clef));
      if (i<j) // Echange des cases
      { int temp=tab_valeurs[i]       ;
        tab_valeurs[i]=tab_valeurs[j] ;
        tab_valeurs[j]=temp           ;
      }
    }
    // Echange final avec le pivot
    int temp=tab_valeurs[i]             ;
    tab_valeurs[i]=tab_valeurs[_droite] ;
    tab_valeurs[_droite]=temp           ;
    return i ;
  }
}
// === Programme principal ===
public class tri_rapide {
 public static void main(String[] args) {
  CTabvaleurs Liste = new CTabvaleurs() ;
  Liste.chargement() ;
  Liste.tri_rapide(Liste.gauche(),Liste.droite()) ;
  Liste.affichage(Liste.gauche(),Liste.droite())  ;
 }
}