Objectif : Ecrire un programme C# implémentant l'algorithme du tri rapide.
 

Spécifications de l’algorithme :
 

Global :Tab[min..max] tableau d'entier    fonction Partition( G , D : entier )  résultat : entier  // méthode de Sedgewick  Local : i , j ,  piv , temp : entier  début      piv  ¬  Tab[D];      i  ¬ G-1;      j  ¬ D;      repeter         repeter  i ¬  i+1 jusquà Tab[i] >= piv;         repeter  j ¬  j-1 jusquà Tab[j] <= piv;         temp ¬  Tab[i];         Tab[i] ¬  Tab[j];         Tab[j] ¬  temp      jusquà j <= i;      Tab[j] ¬  Tab[i];      Tab[i] ¬  Tab[d];      Tab[d] ¬  temp;      résultat ¬  i FinPartition Algorithme TriRapide( G  , D : entier ); Local :  i : entier  début  si D > G alors     i ¬ Partition( G , D );    TriRapide( G , i-1 );    TriRapide( i+1 , D );  Fsi FinTRiRapide

Implantation en C#

On ajoute deux sentinelles au tableau, une au début (minimum absolu) l'autre à la fin (maximum absolu). Ce qui se traduira en C# par la déclaration d'un tableau t[m], les cellules t[0] et t[m+1] contiennent les deux sentinelles, les cellules utiles allant alors de 1 à m.(de 1 à table.Length-2)
 
 

Proposition de squelette de classe C# à implanter :
 

class ApplicationTriSelect   {   static int[] table;  // le tableau à trier par exemples 19 éléments   /*  les cellules [0] et [20] contiennent des sentinelles,        les cellules utiles vont de 1 à 19.(de 1 à table.length-2)   */   static void AfficherTable ( )    {   // Affichage du tableau     ........   }   static void InitTable  ( )    { // Initialisation du tableau      .........   }   static void QSort (int G, int D )   {   // sous-programme de Tri rapide     .........    }   static int partition (int G, int D )   {  // partition / méthode de Sedgewick /     .........    }    static void Main(string[ ] args)     {       InitTable ( );       int n = table.Length-2;      System.Console.WriteLine("Tableau initial :");      AfficherTable ( );      QSort(1,n);      System.Console.WriteLine("Tableau une fois trié :");      AfficherTable ( );      System.Console.Read();    }   }  }

Remonter