Structure

les structures
connaitre les unité: x mod 10 345 mod 10 = 5
recuperer l'incide c'un tableau for(int i=tabjeux.length-1;i>=1;i--){
for(int j=tabjeux[tabjeux.length-1].length-1;j>=1;j--){
indice= (i*(tableau[tableau.longueur-1].longueur-1))-((tableau[tableau.longueur-1].longueur-1)-j);
}
}
les structures
inverser deux variables en xor A <- A - B
B <- A + B
A <- B - A




les listes
structure
algorithme language java language C
enregistrement liste {
  entier valeur;
  Liste suivant;

  fonction sans retour Liste(entier premier,Liste reste){
   valeur<- premier;
   suivant<- reste;
  }

  fonction avec retour entier tete(){
   retourne this.valeur;
  }

  fonction avec retour entier queue(){
   retourne this.suivant;
  }
} 		public class liste {
  static class Liste{
  private int valeur;
  private Liste suivant;

  public Liste(int premier,Liste reste){
   valeur= premier;
   suivant= reste;
  }

  public int tete(){
   return(valeur);
  }

  public Liste queue(){
   return(suivant);
 }
} 		typedef struct element element;
 struct element
 {
   int val;
   struct element *nxt;
 };typedef element* llist;
appartient
Appel -> boolean present=maliste.appartient(x,l)

fonction avec retour boolean appartient(entier x,liste l)
 tant que (l différent de vide) faire
  si (l.valeur== x) alors retourne vrai
  l<- l.suivant;
 fin tant que
retourne false;
fin
insérer après
Appel -> maliste=maliste.insererapres(x,y,l)

fonction sans retour insererapres(entier x,entier y,liste l)
  tant que (l différent de null)
    si (l.valeur différent de x) alors l<- l.suivant
    sinon
      liste q = new liste(y,p.suivant);
      p.suivant=q;
      retourne l
    fin si
  fin tan que
fin




les Piles
structure
algorithme language java language C
enregistrement Piles
{
 Liste L;

  Piles(){
   this.L<-null;
  }

  fonction avec retour booleen estVide(Piles p){
   retourne p.L==null;
  }

  fonction sans retour empiler(entier a,Piles p){
   p.L<-CreerListe(a,p.L);
  }

  fonction sans retour depiler(Piles p) {
   p.L<-p.L.suivant;
  }

  fonction avec retour entier sommet(Piles p){
   retourne(p.L.tete());
  }
} 		static class Piles
{
  private Liste L;

  public Piles(){
   L=null;
  }

  public boolean estVide(Piles p){
   return p.L==null;
  }

  public void empiler(int a,Piles p){
   p.L=CreerListe(a,p.L);
  }

  public void depiler(Piles p) {
   p.L=p.L.queue();
  }

  public int sommet(Piles p){
   return(p.L.tete());
  }
} 		struct stack
{
  struct stack *prev;
  struct stack *next;
  void *data;
};

stack_s *stack_new (void)
{
  return (NULL);
}

void stack_push (stack_s ** pp_stack, void *data)
{
  if (pp_stack != NULL)
  {
   stack_s *p_p = *pp_stack;
   stack_s *p_l = NULL;
   p_l = malloc (sizeof (*p_l));
   if (p_l != NULL)
   {
    p_l->data = data;
    p_l->next = NULL;
    p_l->prev = p_p;
    if (p_p != NULL)
     p_p->next = p_l;
    *pp_stack = p_l;
   }
   else
   {
    fprintf (stderr, "Memoire insuffisante\n");
    exit (EXIT_FAILURE);
   }
  }
  return;
}

void *stack_pop (stack_s ** pp_stack)
{
  void *ret = NULL;

  if (pp_stack != NULL && *pp_stack != NULL)
  {
   stack_s *p_l = *pp_stack;
   stack_s *p_p = p_l->prev;

   if (p_p != NULL)
    p_p->next = NULL;
   ret = p_l->data;
   free (p_l);
   p_l = NULL;
   *pp_stack = p_p;
  }
  return (ret);
}
dans le fichier .h
typedef struct stack stack_s;
stack_s *stack_new (void);
void stack_push (stack_s **, void *);
void *stack_pop (stack_s **);
void stack_delete (stack_s **);



les files
structure
algorithme language java language C
enregistrement file
 tableau d'entier[] tab;
 entier queue;
 entier tete;
 entier taille;
fin enregistrement

 fonction avec retour file creefile(entier x)
  File f;
  f.taille=x;
  f.tab=new int[f.taille];
  f.queue=0;
  f.tete=0;
  return f;
 }

 fonction avec retour boolean estVide(File f){
  return(f.tete==f.queue);
 }

 fonction avec retour boolean estPleine(File f){
  return(((f.queue+1)%f.taille)==f.tete);
 }

 fonction avec retour entier enfiler(int x,File f){
  if(estPleine(f))return (-1);
  f.tab[f.queue]=x;
  f.queue=(f.queue+1)%f.taille;
  return(0);
 }

 fonction avec retour entier defiler(int x,File f){
  if(estVide(f))return (-1);
  x =f.tab[f.tete];
  f.tete=(f.tete+1)%f.taille;
  return(0);
  }
}
 static class File{
 private int[] tab;
 private int queue;//pointe sur une case vide qui recevra le prochain élément
 private int tete;//pointe sur lélément le plus ancient dans la tete
 private int taille; //ne contiendras pas plus de taille -1 elements
}

public static File creefile(int t){
 File f=new File();
 f.taille=t;
 f.tab=new int[f.taille];
 f.queue=0;
 f.tete=0;
 return f;
}

public static boolean estVide(File f){
 return(f.tete==f.queue);
}

public static boolean estPleine(File f){
 return(((f.queue+1)%f.taille)==f.tete);
}

public static int enfiler(int x,File f){
 if(estPleine(f))return (-1);
 f.tab[f.queue]=x;
 f.queue=(f.queue+1)%f.taille;
 return(0);
}

 public static int defiler(int x,File f){
 if(estVide(f))return (-1);
 x =f.tab[f.tete];
 f.tete=(f.tete+1)%f.taille;
 return(0);
}

 typedef struct Element Element;
 struct Element
 {
  int nombre;
  Element *suivant;
 };
typedef struct File File;
 struct File
 {
  Element *premier;
 };

void enfiler(File *file, int nvNombre)
{
 Element *nouveau = malloc(sizeof(*nouveau));
 if (file == NULL || nouveau == NULL)
 {
  exit(EXIT_FAILURE);
 }
 nouveau->nombre = nvNombre;
 nouveau->suivant = NULL;
 if (file->premier != NULL) /* La file n'est pas vide */
 {
  /* On se positionne à la fin de la file */
  Element *elementActuel = file->premier;
  while (elementActuel->suivant != NULL)
  {
   elementActuel = elementActuel->suivant;
  }
  elementActuel->suivant = nouveau;
 }
 else /* La file est vide, notre élément est le premier */
 {
  file->premier = nouveau;
 }
}

int defiler(File *file)
{
 if (file == NULL)
 {
  exit(EXIT_FAILURE);
 }
 int nombreDefile = 0;
 /* On vérifie s'il y a quelque chose à défiler */
 if (file->premier != NULL)
 {
  Element *elementDefile = file->premier;
  nombreDefile = elementDefile->nombre;
  file->premier = elementDefile->suivant;
  free(elementDefile);
 }
 return nombreDefile;
}




les Arbre
structure
algorithme language java language C
enregistrement arbre
 entier valeur;
 arbre filsdroit;
 arbre filsgauche;
fin enregistrement

fonction avec retour arbre creearbre(entier x,arbre G,arbre D)
 arbre A;
 A.valeur<- x;
 A.filsgauche<- G;
 A.filsdroit<- D;
 retourne A;
fin
chercher
fonction avec retour boolean chercher(entier x,arbre A)
 debut
  si (a==null) alors retourne faux
  sinon
   si A.valeur==x alors retourne vraix;
   sinon
    si x<A.valeur alors
     retourne chercher(x,A.filsgauche)
    sinon
     retourne chercher(x,A.filsdroit)
    fin si
   fin si
  fin si
 fin
calculer hauteur
fonction avec retour entier calculerhauteur(arbre a)
 debut
  si (a==null) alors retourne 1;
  retourne 1+ Max(calculerhauteur(A.filsdroit),calculerhauteur(A.filsgauche))
  fin si
 fin
rotation
fonction avec retour arbre rotationGauche(arbre A)
 debut
  arbre B;
  B<-A.filsdroit;
  A.filsdroit<-B.filsgauche;
  B.filsgauche<-A
  retourne B;
 fin

fonction avec retour arbre rotationDroite(arbre A)
 debut
  arbre B;
  B<-A.filsgauche;
  A.filsgauche<-B.filsdroit;
  B.filsdroit<-A
  retourne B;
 fin

fonction avec retour arbre rotationDG(arbre A)
 debut
  SI(A != null)
    rotationDroite(A.filsDroit);
    rotationGauche(A);
  fin si
 fin

fonction avec retour arbre rotationGD(arbre A)
 debut
  SI(A != null)
    rotationGauche(A.filsGauche);
    rotationDroite(A);
  fin si
 fin
supprimer
fonctin avec retour arbre supprimer(arbre A,valeur x)
 debut
  si (a==vide) alors
    retourne vide;
  fin si
  si (x==A.valeur et A.filsdroit==vide) alors
   retourne A.filsgauche
  fin si
  si (x==A.valeur et A.filsgauche!=vide et A.filsdroit!=vide) alors
   A.valeur<-max(A.filsgauche);
   A.filsgauche<-dmax(a.filsgauche);
   retourn A;
  fin si
  si (x>a.valeur) alors
   A.filsgauche<-supprimer(A.filsdroit,x);
  fin si
  si (x<a.valeur) alors
   A.filsdroit<-supprimer(A.filsgauche,x);
  fin si

fonction avec retour entier max(arbre A)
 debut
  si (A.filsdroit==vide) alors
   retourne A.valeur;
  retourne max(A.filsdroit);
 fin

fonction avec retour entier dmax(arbre A)
 debut
  si (A.filsdroit==vide) alors
   retourne A.filsgauche;
  retourne dmax(A.filsdroit);
 fin




les graphes
structure
algorithme language java language C
arc
fonction avec retour boolean arc(entier x, entier y,graphe[][] g)
 si( x>g.taille()-1||y>g.taille()-1
   retourne faux;
retourne g[y][x];
  boolean arc(int x,int y)
  {
   if(x>this.graphe.length-1||y>this.graphe.length-1)
    return false;
   return this.graphe[y][x];
  }
arrete
fonction avec retour boolean arc(entier x, entier y,graphe[][] g)
 si( x>g.taille()-1||y>g.taille()-1
   retourne faux;
retourne g[y][x] ou g[x][y];
 boolean arete(int x,int y)
  {
   if(x>this.graphe.length-1||y>this.graphe.length-1)
    return false;
   return (this.graphe[x][y]||this.graphe[y][x]);
  }
successeur
fonction avec retour List successeur(entier s,graphe[][] g){
  List<entier> liste= new listet<entier> ();
  si (s>g.taille()-1)
   return liste;
  pour ( i allant de 0 à g.taille())
  {
   si (g[i][s]==vrai)
    liste.add(i);
  }
  retourne liste;
}
  List<Integer> successeur(int s){
  List<Integer> liste= new ArrayList<Integer> ();
   if(s>this.graphe.length-1)
    return liste;
   for(int i=0;i<this.graphe.length;i++)
   {
    if(this.graphe[i][s])
     liste.add(i);
   }
   return liste;
  }
predecesseur
 fonction avec retour List predecesseur(entier s,graphe[][] g){
  List<entier> liste= new listet<entier> ();
   si (s>g.taille()-1)
    return liste;
   pour ( i allant de 0 à g.taille())
   {
    si (g[s][i]==vrai)
     liste.add(i);
   }
   retourne liste;
  }
  List<Integer> predecesseur(int s){
   List<Integer> liste= new ArrayList<Integer> ();
    if(s>this.graphe.length-1)
     return liste;
    for(int i=0;i<this.graphe.length;i++)
    {
     if(this.graphe[s][i])
      liste.add(i);
    }
    return liste;
   }
descendant
 fonction avec retour List descendant(entier s,graphe[][] g){
   List<entier> liste_temporaire= new listet<entier> ();
   List<entier> liste= new listet<entier> ();
   liste_temporaire=successeur(s,g);
   tant que(!liste_temporaire different de vide) faire
   {
    pour(i allant de 0 à liste_temporaire.taille()) faire
    {
     si(liste ne contient pas (liste_temporaire(i)))
     {       liste_temporaire.ajoutertout(successeur(liste_temporaire(i),g));
      liste.ajouter(liste_temporaire(i));
      liste_temporaire.supprimer(i);
     }
     sinon
     {
      liste_temporaire.supprimer(i);
     }
    }
   }
   pour(i allant de 0 à liste.taille())    {
    si(s==liste(i))
    {
     liste.supprimer(i);
    }
   }
   retourne liste;
  }
  List<Integer> descendant(int s){
   List<Integer> liste_temporaire=new ArrayList<Integer>();
   List<Integer>liste=new ArrayList<Integer>();
   liste_temporaire=this.successeur(s);
   while(!liste_temporaire.isEmpty())
   {
    for(int i = 0; i < liste_temporaire.size(); i++)
    {
     if(!liste.contains(liste_temporaire.get(i)))
     {       liste_temporaire.addAll(this.successeur(liste_temporaire.get(i)));
      liste.add(liste_temporaire.get(i));
      liste_temporaire.remove(i);
     }
     else
     {
      liste_temporaire.remove(i);
     }
    }
   }
   for(int x = 0; x < liste.size(); x++)    {
    if(s==liste.get(x))
    {
     liste.remove(x);
    }
   }
   return liste;
  }
ancetres
 fonction avec retour List ancetres(entier s,graphe[][] g){
   List<entier> liste_temporaire= new listet<entier> ();
   List<entier> liste= new listet<entier> ();
   liste_temporaire=predecesseur(s,g);
   tant que(!liste_temporaire different de vide) faire
   {
    pour(i allant de 0 à liste_temporaire.taille()) faire
    {
     si(liste ne contient pas (liste_temporaire(i)))
     {       liste_temporaire.ajoutertout(predecesseur(liste_temporaire(i),g));
      liste.ajouter(liste_temporaire(i));
      liste_temporaire.supprimer(i);
     }
     sinon
     {
      liste_temporaire.supprimer(i);
     }
    }
   }
   pour(i allant de 0 à liste.taille())    {
    si(s==liste(i))
    {
     liste.supprimer(i);
    }
   }
   retourne liste;
  }
  List<Integer> ancetres(int s){
   List<Integer> liste_temporaire=new ArrayList<Integer>();
   List<Integer>liste=new ArrayList<Integer>();
   liste_temporaire=this.predecesseur(s);
   while(!liste_temporaire.isEmpty())
   {
    for(int i = 0; i < liste_temporaire.size(); i++)
    {
     if(!liste.contains(liste_temporaire.get(i)))
     {       liste_temporaire.addAll(this.predecesseur(liste_temporaire.get(i)));
      liste.add(liste_temporaire.get(i));
      liste_temporaire.remove(i);
     }
     else
     {
      liste_temporaire.remove(i);
     }
    }
   }
   for(int x = 0; x < liste.size(); x++)    {
    if(s==liste.get(x))
    {
     liste.remove(x);
    }
   }
   return liste;
  }




les trie

le trie à bulle
structure
algorithme language java language C
fonction sans retour Trie_a_Bulle(entier[] T)
ENtrée : tableau d'entier T tel que longueur(T)>=2
sorie :modifie T tel que les valeurs initiales T soient triées en ordre croissant

debut
  pour i<-Longueur(T-2) à 0 faire
   pour j<-0 à i faire
    si T[j]>T[j+1]alors
     echanger(T,i,j+1)
    finsi
   finpour
  finpour
fin
 public class triebulle
{
 
  public static void echanger(int[] tab, int i, int j)
  {
   int temp=tab[j];
   tab[j]=tab[i];
   tab[i]=temp;
  }
  public static int[] triBulle(int[] tab)
  {
   for(int i=tab.length-2;i>=0;i--){
    for(int j=0;j<=i;j++){
     if(tab[j]>tab[j+1]){
      echanger(tab,j,j+1);
     }
    }
   }
   return tab;
  }
}
complexité O(n²)
stabilité oui
en place oui




le trie par selection du maximum
structure
algorithme language java language C
Fonction dans retour Tri-Par_Selection_du_Maximum(entier[] T)
0 imax ifin
[][][][][][][][][][][][][][][][][][][][][][][][]
Entrée : tableau d'entier T tel que longueur(T)>=2
sorie :modifie T tel que les valeurs initiales T soient triées en ordre croissant

debut
 entier imax,ifin
  pour ifin<-longueur(T)-1 à 1 faire
   //recherche de l'indice du max entre 0 et fin
   imax<-0
   pour i<-1 à ifin faire
    si T[i]> T[imax] alors
     imax<-i
    finsi
   finpour
   Echange(T,imax,ifin)
 finpour
fin
 public class Tri_Par_Selection_du_Maximum
{
  public static void echanger(int[] tab, int i, int j)
  {
   int temp=tab[j];
   tab[j]=tab[i];
   tab[i]=temp;
  }
  public static void TriParSelectionduMaximum(int[] T){
  int imax,ifin;
   for(ifin=T.length-1;ifin>=1;ifin--)
   {
    imax=0;
    for(int i=1;i<=ifin;i++){
     if(T[i]>T[imax])
     imax=i;
    }
    echanger(T,imax,ifin);
   }
  } }
complexité O(n²) ou n la longueur de T
stabilité possible (...)
enplace : oui




le trie par insertion
structure
algorithme language java language C
Fonction dans retour Tri_Par_Insertion(entier[] T)
[][][][][][][][][][][][]

[][][][]][][[][][]][[]][]
debut
 entier lg,i,j,clef
 lg<longueur(T)
 pour i<-((lg-1)-1) à 0 faire   //T est trié à partir de la position i+1
  clef<-T[i]
  //recherche de la place de la clef
  j<--i+1
   tanque j<lg et T[j] <clef faire
   T[j-1]<-T[j]
   j<-j+1
  fin tantque
  T[j-1]<-clef
 finpour
 fin
 public class Tri_Par_Insertion
{
  public static void TriParInsertion(int[] T){
  int lg,i,j,clef;
  lg=T.length;
   for(i=((lg-1)-1);i>=0;i--){//T est trié à partir de la position i+1
    clef=T[i];//recherche de la place de la clef
    j=i+1;
    while(j<lg && T[j]<clef){
     T[j-1]=T[j];      j=j+1;
    }
    T[j-1]=clef;
   }
  }
}
complexité : O(n²) ou n la longueur de T mais meme si le tableau est tié cet algo seras toujours en n² ce CON ne regarde pas
stabilité :
enplace :




le trie par dénombrement
structure
algorithme language java language C
Fonction avec retour entier [] Tri_Par_Denombrement(entier[] T,entier k)
on suppose que chacun des élements du tableau sont des entiers compris entre k et k-1
on suppose que tout les entiers sont différents

pour un entier x dans le tableau il existe m entiers dans le tableau qui lui sont inférieurs ou égaux si est en position m-1 dans le tableau trié
debut
 entierTS[Longueur(T)]
 entier C[k]
 pour i<--0 à k-1 faire
  C[i]<--0
 finpour
 pour i<--0 à longueur(T)-1 faire
  C[T[i]]<--1
 finpour
 pour i<--1 à k -1 faire
  C[i]<--C[i]+C[i-1]
 finpour
 pour i<--0 à longueur(T)-1 faire
  TS[C[T[i]]-1]<--T[i]
 finpour
 retourne TS
fin
complexité : O(n+k)
stabilité :
enplace :




le trie par fusion
structure
algorithme language java language C
Fonction sans retour TrieFusion(entier[] T, entier p, entier r)
entreee 0<p,r<Longueur(T)
sortie: modifie T tel que le sous-tableau T[p...r] est trié

debut
 si p < r alors
   q<--(p+r) div 2
   TrieFusion(T,p,q)
   TrieFusion(T,q+1,r)
   FUSION(T,p,q,r)
 finsi
fin

fonction sans retour FUSIONentier[] T, entier p, entier q,entier r)
entrée 0<=p<=q<=r<Longueur(T) des entiers. les sous tableaux T[p..r] et T[q+1..r] sont triés
sortie: modifier T tel que le sous-tableau T[p..r] est trié
entier lg,ld,i,ig,id
entier[] G,D//g et d sont les sous tableaux
debut
 lg<--q-p+1
 ld<--r--(q+1)+1
 G<-- creer entier[lg+1];
 D<-- creer entier[ld+1];
 pour i<--0 à ld-1 faire
  D[i]<--T[p+i]
 finpour
 pour i<--0 à ld-1 faire
  D[i]<--T[q+1+i]
 fin pour
 G[ld]<-- +infini;
 D[ld]<-- +infini;
 ig<--0
 id<--0
 pour k<--p à r faire
  si G[ig]<=D[id] alors
    T[k]<--G[id]
    ig<ig+1
   sinon
    T[k]<--D[id]
    id<--id+1
   finsi
 finpour
fin
//la complexité c'est le nombre d'étage fois la taille du tableau 		public class Trie_Fusion
{
 public static void triFusion(int tableau[])
 {
  int longueur=tableau.length;
  if (longueur>0)
  {
   triFusion(tableau,0,longueur-1);
  }
 }
 private static void triFusion(int tableau[],int deb,int fin)
 {
  if (deb!=fin)
  {
   int milieu=(fin+deb)/2;
   triFusion(tableau,deb,milieu);
   triFusion(tableau,milieu+1,fin);
   fusion(tableau,deb,milieu,fin);
  }
 }
 private static void fusion(int tableau[],int deb1,int fin1,int fin2)
 {
  int deb2=fin1+1;//on recopie les éléments du début du tableau
  int table1[]=new int[fin1-deb1+1];
  for(int i=deb1;i<=fin1;i++)
  {
   table1[i-deb1]=tableau[i];
  }
  int compt1=deb1;
  int compt2=deb2;
  for(int i=deb1;i<=fin2;i++)
  {
   if (compt1==deb2) //c'est que tous les éléments du premier tableau ont été utilisés
   {
    break; //tous les éléments ont donc été classés
   }
   else if (compt2==(fin2+1)) //c'est que tous les éléments du second tableau ont été utilisés
   {
    tableau[i]=table1[compt1-deb1]; //on ajoute les éléments restants du premier tableau
    compt1++;
   }
   else if (table1[compt1-deb1]<tableau[compt2])
   {
    tableau[i]=table1[compt1-deb1]; //on ajoute un élément du premier tableau
    compt1++;
   }
   else
   {
    tableau[i]=tableau[compt2]; //on ajoute un élément du second tableau
   compt2++;
   }
  }
 }
}
Arbre des appels récursifs : log2(n)+1 niveaux complexité en teps © (n log2 n)
stabilité : oui
enplace : non




le trie rapide
structure
algorithme language java language C
Fonction sans retour TrieRapide (Quick SORT)(entier[] T)
sortie modifie T tels que T soit trié
QuickSort_Rec(T,0,Longueur(T)-1)

fonction sans retour QuickSort_rec(entier[] T,enter p,entier r)
entrée 0<=p,r<Longueur(T)
sortie modifie T tel que le sous-tableau T[p..r] soit trié
debut
 entier q
 si p<r alors
  q<-- Partitionner(T,p,q)
  QuickSort_Rec(T,p,q-1)
  QuickSort_Rec(T,q+1,r)
 finsi
fonction avec retour entier Partition(entier[] T, entier p, entier r)
entrée 0<=p,r<Longueru(T)
sortie: modifie T et retourne la valeur de q telle que debut
 entier pivot,i,j,q
 pivot<--T[r]
 i<--p-1
 pour j<--p à r-1 faire // on s'arrete à la case juste avant le pivot
  si T[j]<= pivot alors
    i<--i+1
    Echanger(T,i,j)
   finsi
 finpour
 Echanger(T,i+1,r)
fin
q<--i+1
retourner q
 public class Quick_Sort

{   private static int array[];
  private static int length;
 
  public static void QuickSort(int[] inputArr) {
   if (inputArr == null || inputArr.length == 0) {
    return;
   }
   array = inputArr;
   length = inputArr.length;
   quickSort(0, length - 1);
  }

  private static void quickSort(int lowerIndex, int higherIndex) {
   int i = lowerIndex;
   int j = higherIndex;
   int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
    while (i <= j) {
     while (array[i] > pivot) {
      i++;
     }
    while (array[j] > pivot) {
     j--;
    }
    if (i <= j) {
     exchangeNumbers(i, j);
     i++;
     j--;
    }
   }
   if (lowerIndex < j)
    quickSort(lowerIndex, j);
   if (i < higherIndex)
    quickSort(i, higherIndex);
   }

  private static void exchangeNumbers(int i, int j) {
   int temp = array[i];
   array[i] = array[j];
   array[j] = temp;
  }
}
partitionnement O(n) ou n=r-p+1 complexité :au pire des cas: ©(n²)(si on lui donne un tableau trié il est pire que le reste
complexité :©au meilleur des cas ©(nlog(n))
stabilité :
enplace :




le trie par tat
structure
algorithme language java language C
Fonction sans retour TrieParTat(entier[] T)
un noeud:
racine du sous arbre gauche
Gauche=2i+1
racine du sous arbre droit:
Droite=2i+1+1
Y[Gauche(i)]<=T[i] et T[Droite(i)]<=T[i]

debut  entier i,n,tailleTas
 n<--Longueur(T)
 tailletas<--n
 ConstruireTas(T)
 pour i<--n-1 à 1 faire
  Echanger(T,0,i)
  tailleTas<-tailleTas-1
  Entasser(T,0,tailleTas)
 finpour
mise à jour du tas pour la position i:
Entasser(T,i,tailleTas)

fonction sans retour ConstruireTas(Entier[] T)
debut
 entier i,n,tailletas
 n<--Longueur(T)
 tailleTas<--n
 pour i<--(n div 2) -1 à 0 faire
   Entasser(T,i,tailleTas)
 finpour
fonction sans retour entasser(entier[] T, entier i, entier trier tailleTas)
debut
 entier g,d,plusGrand
 g<--Gauche(i)
 d<--Droite(i)
 plusGrand<--i
  si g<tailleTas alors
   si T[g] > T[plusgrand] alors
     plusgrand<--g
   finsi
   si d <tailletas alors
     si T[d] > T[plusgrand] alors
      plusgrand<--d
    finsi
   finsi
  finsi
  si plusgrand différent de i alors
    Echanger(t,i,plusgrand)
    Entasser(t,plusgrand,tailletas)
  finsi

public class tri_par_tat
{

  public static void TrieParTat(int[] T){
  int i,n,tailleTas;
  n=T.length;
  tailleTas=n;
  ConstruireTas(T);
  for(i=n-1;i>=1;i--){
   Echanger(T,0,i);
   tailleTas=tailleTas-1;
   Entasser(T,0,tailleTas);
  }
  Entasser(T,i,tailleTas);
  }

  public static void Echanger(int[] T,int a, int i){
  int temp = T[a];
  T[a] = T[i];
  T[i] = temp;
  }
  public static void ConstruireTas(int[] T){
  int i,n,tailleTas;
  n=T.length;
  tailleTas=n;
  for(i=(n / 2)-1;i>= 0;i--){
   Entasser(T,i,tailleTas);
  }
  }

  public static int Gauche(int i){
  return 2*i+1;
  }

  public static int Droite(int i){
  return 2*i+1+1;
  }

  public static void Entasser(int[] T,int i,int tailleTas){
  int g,d,plusGrand;
  g=Gauche(i);
  d=Droite(i);
  plusGrand=i;
   if(g<tailleTas){
    if(T[g] > T[plusGrand]){
     plusGrand=g;
    }
     if(d <tailleTas){
      if(T[d] > T[plusGrand]){
       plusGrand=d;
      }
     }
    }
   if(plusGrand !=i){
    Echanger(T,i,plusGrand);
     Entasser(T,plusGrand,tailleTas);
    }
   }
 }
complexité :
stabilité :
enplace :




la longueur des plus long sous mot communs entre x et y
entier n,m,i,j
entier[][] L
debut
 m<-- longueur(x);n<-- longueyr(y)
 L<-- cree entier[m+1][n+1]
 pour i allant de 0 à m faire
  L[i,0]<--m
 finpour
 pour j allant de 1 a n faire
  L[0,j]<--0
  pour i allant de 1 a m faire
   si x[i-1]=y[j-1] alors
    L[i,j]<--L[i-1,j-1]+1
   sinon si L[i-1,j]>L[i,j-1] alors
    L[i,j] <-- L[i-1,j]
   sinon
    L[i,j] <-- L[i,j-1]
   fin si
  finpour
 finpour
 retourner L[m,n]
fin
complexité
stabilité
enplace