/* Tri a bulle d'un tableau de chaines         */
/* de caracteres                               */

public class TriSelectionTableauDePosition3D {

/////////////////////////////////////////////////  

/* Type agrege de stockage des informations     */
/* relatives a une position en trois dimensions */

  static class Position3D {
    double x = 0.0;
    double y = 0.0;
    double z = 0.0; };

/* Methode de calcul de la distance              */
/* entre une Positon3D et l'origine              */
    
static double distanceOrigine(Position3D p) {
  double d;
  d = Math.sqrt(p.x*p.x+p.y*p.y+p.z*p.z);
  return d;
}

/* Methode de recherche de l'indice de la valeur */
/* maximale d'un tableau de Position3D restreint */
/* a ses n premieres valeurs                     */
  
  static int indiceDuMaximum(int n,Position3D [] t) {
    double max;
    int iMax;
    double d;
    int i;
    max = distanceOrigine(t[n]);
    iMax = n;
    for ( i = n-1 ; i >= 0 ; i = i-1 ) {
      d = distanceOrigine(t[i]);
      if ( d > max ) {
        max = d;
        iMax = i; } }
    return iMax;
  }

/* Methode de tri par selection d'un tableau    */
/* de Position3D en fonction de la distance     */
/* a l'origine                                  */    

  static void triSelectionTableauDePosition3D(Position3D [] t) {
    int i;
    Position3D aux;
    int iMax;
    for ( i = t.length-1 ; i > 0 ; i = i-1 ) {
      iMax = indiceDuMaximum(i,t);
      if ( iMax != i ) {
        aux = t[iMax];
        t[iMax] = t[i];
        t[i] = aux; } }
  }

/////////////////////////////////////////////////

/* Affichage d'une Position3D formatee (x,y,z) */
  
  static void afficher(Position3D p) {
    System.out.format("(%5.3f, %5.3f, %5.3f)",p.x,p.y,p.z);
  }
  
/* Methode d'affichage d'un tableau            */
/* de Position3D (avec distances à l'origine)  */
  
  static void affichage(Position3D [] tp) {
    int i;
    for ( i = 0 ; i < tp.length ; i = i+1 ) {
      afficher(tp[i]);
      Ecran.afficherln(" - ",distanceOrigine(tp[i])); }
  }

/* Methode de creation d'une Position3D tiree  */
/* placee au hasard dans le cube de diagonale  */
/* (0.0,0.0,0.0) - (10.0,10.0,10.0)            */
  
  static Position3D position3DAleatoire() {
    Position3D p = new Position3D();
    p.x = 10.0*Math.random();
    p.y = 10.0*Math.random();
    p.z = 10.0*Math.random();
    return(p);
  }

/* Programme principal                         */

  public static void main(String [] args) {
    int n;
    Position3D [] tp;
    int i;
    Ecran.afficher("Nombre de Position3D ? ");
    n = Clavier.saisirInt();
    tp = new Position3D[n];
    for ( i = 0 ; i < n ; i++ ) {
      tp[i] = position3DAleatoire(); }
    Ecran.sautDeLigne();
    affichage(tp);
    Ecran.sautDeLigne();
    triSelectionTableauDePosition3D(tp);
    affichage(tp);
  }
}