Traduction en Java
Tri rapide Quicksort
 
Une classe Java solution du problème :

Le sous programme Java implantant l'algorithme de tri rapide :
 

 
 
 
 
 

 

 

Une classe complète permettant l'exécution du sous-programme précédent :
 
class ApplicationTriQSort  {
 

static int[] table = new int[21] ; // le tableau à trier : 21 éléments 
    static void AfficherTable ( ) {
     // Affichage du tableau sans les sentinelles
        int n = table.length-2;
        for ( int i = 1; i <= n; i++) 
            System.out.print(table[i]+" , ");
         System.out.println();
    }

     static void InitTable  ( ) {
     // remplissage aléatoire du tableau 
        int n = table.length-2;
        for ( int i = 1; i <= n; i++) 
          table[i] = (int)(Math.random()*100);
        table[0] = -Integer.MAX_VALUE;
        table[n+1] = Integer.MAX_VALUE;
    }

 static void main(String[ ] args) {
         InitTable ( );
         int n = table.length-2;
         System.out.println("Tableau initial :");
         AfficherTable ( );
         QSort(1,n);
         System.out.println("Tableau une fois trié :");
        AfficherTable ( );
  }
static int partition (int G, int D )
      { // partition / Sedgewick /
        int i, j, piv, temp;
         piv = table[D];
         i = G-1;
         j = D;
        do {
           do i++; while (table[i]<piv);
           do j--; while (table[j]>piv);
            temp = table[i];
            table[i] = table[j];
            table[j] = temp;
        }while(j>i);
         table[j] = table[i];
         table[i] = table[D];
         table[D] = temp;
        return i;
      }
 
       static void QSort (int G, int D )
      { // tri rapide, sous-programme récursif
        int i;
        if (D>G) {
            i = partition(G,D);
            QSort(G,i-1);
            QSort(i+1,D);
         }
  }
}

Image en diagrammes structurés JGrasp-Like du programme

informations sur les diagrammes

Source recopiable (cliquez sur le lien)

Tableau initial :
68 , 2 , 61 , 81 , 2 , 27 , 10 , 79 , 5 , 70 , 33 , 72 , 38 , 49 , 49 , 4 , 69 , 18 , 20

Tableau une fois trié :
2 , 2 , 4 , 5 , 10 , 18 , 20 , 27 , 33 , 38 , 49 , 49 , 61 , 68 , 69 , 70 , 72 , 79 , 81
 
 

Remonter