public class TriRapideGraphique {

  static class Pion {
      int val;
      double px;
      double py; }

  static int tc[];
  static Pion tp[];
  static int tECi;
  static int tECf;
  static int pivot = -1;
  static int iPiv = -1;
  static private int tpval;
  static private double tppx;
  static private double tppy;

  static void affichage() {
    EcranGraphique.clear();
    if(iPiv != -1) {
      EcranGraphique.setColor(0, 0, 0);
      EcranGraphique.drawText(20, 30, 3, "Pivot : %d", new Object[] { Integer.valueOf(pivot) }); }
    for(int i = 0; i < tp.length; i++) {
      if(iPiv == i)
          EcranGraphique.setColor(0, 0, 200);
      else
      if(i < tECi)
          EcranGraphique.setColor(0, 200, 0);
      else
      if(i >= tECi && i <= tECf)
          EcranGraphique.setColor(200, 0, 0);
      else
          EcranGraphique.setColor(0, 0, 0);
      EcranGraphique.drawRect((int)Math.round(tp[i].px), (int)Math.round(tp[i].py), 39, 39);
      EcranGraphique.drawText((int)Math.round(tp[i].px + 10D + (double)(tp[i].val >= 10 ? 0 : 5)), (int)Math.round(tp[i].py + 25D), 3, "%d", new Object[] { Integer.valueOf(tp[i].val) });}
    EcranGraphique.flush();
    EcranGraphique.wait(10);
  }

  static void animationPermutation(int i, int j) {
    double d = tp[i].px;
    double d1 = tp[i].py;
    double d2 = tp[j].px;
    double d3 = tp[j].py;
    int k = tp[i].val;
    int l = tp[j].val;
    double d4 = (tp[i].px + tp[j].px) / 2D;
    double d5 = (tp[i].py + tp[j].py) / 2D;
    double d6 = Math.abs(tp[i].px - d4);
    for(int i1 = 0; i1 <= 45; i1++) {
      double d7 = (3.1415926535897931D * (double)i1) / 45D;
      tp[j].px = (int)(d4 + d6 * Math.cos(d7));
      tp[j].py = (int)(d5 + 50D * Math.sin(d7));
      tp[i].px = (int)(d4 + d6 * Math.cos(3.1415926535897931D + d7));
      tp[i].py = (int)(d5 + 50D * Math.sin(3.1415926535897931D + d7));
      affichage();
      EcranGraphique.wait(10); }
    tp[i].px = d;
    tp[i].py = d1;
    tp[i].val = l;
    tp[j].px = d2;
    tp[j].py = d3;
    tp[j].val = k;
    affichage();
    EcranGraphique.wait(10);
  }

  static int pivotage(int [] ai,int i,int j,int k) {
    int l;
    pivot = l = ai[iPiv = k];
    animationPermutation(k,j);
    iPiv = j;
    ai[k] = ai[j];
    ai[j] = l;
    int k1 = i;
    for( int l1 = i ; l1 < j ; l1++ ) {
      if( ai[l1] > ai[j] )
        continue;
      if( l1 != k1 ) {
        animationPermutation(k1,l1);
        int i1 = ai[l1];
        ai[l1] = ai[k1];
        ai[k1] = i1; }
      k1++; }
    if( j != k1 ) {
      animationPermutation(k1, j);
      int j1 = ai[j];
      ai[j] = ai[k1];
      ai[k1] = j1; }
    iPiv = -1;
    return k1;
  }

  static void triRapide(int ai[],int i,int j) {
    tECi = i;
    tECf = j;
    if( j == i+1 ) {
      if( ai[j] < ai[i] ) {
        animationPermutation(i,j);
        int l = ai[i];
        ai[i] = ai[j];
        ai[j] = l; } }
    else {
      int i1 = i;
      int k = pivotage(ai,i,j,i1);
      if( k > i+1 )
        triRapide(ai,i,k-1);
      if ( k < j-1 )
        triRapide(ai,k+1,j); }
    tECi = j+1;
  }

  static void triRapide(int ai[]) {
    triRapide(ai,0,ai.length-1);
  }

  public static void main(String args[]) {
    int ai[] = Bibliotheque.initRand(19,99);
    tc = Bibliotheque.clone(ai);
    tp = new Pion[ai.length];
    for( int i = 0 ; i < ai.length ; i++ ) {
      tp[i] = new Pion();
      tp[i].val = ai[i];
      tp[i].px = 10D + (double)i*40D;
      tp[i].py = 60D;}
    EcranGraphique.init(50,50,840,280,800,200,"Tri rapide");
    EcranGraphique.setClearColor(255,255,255);
    affichage();
    Bibliotheque.affichageTableau(ai);
    triRapide(ai);
    affichage();
    Bibliotheque.affichageTableau(ai);
  }
}
