{ Recherche et retour de la valeur minimale      }
{ présente dans un tableau d'entiers             }
{ sans organisation particuliere                 }
{ Methode sequentielle                           }
{ t : le tableau d'entiers de recherche          }
{     (au moins une valeur)                      }

entier fonction valeurMinimale(-> entier [] t)
  entier i
  entier min
  min <- t[0]
  si longueur(t) > 1 alors
    pour i de 1 à longueur(t)-1 faire
      si t[i] < min alors
        min <- t[i]
      fsi
    fait
  fsi
  retourner min
fin fonction

/* Fonction de recherche et retour de la valeur  */
/* minimale contenue dans un tableau de int      */
/* sans organisation particuliere                */
/* Methode sequentielle                          */
/* t : Le tableau d'entiers de recherche         */
/*     (au moins une valeur)                     */

static int valeurMinimale(int [] t) {
  int min = t[0];
  for ( int i = 1 ; i < t.length ; i++ ) {
    if ( t[i] < min ) {
      min = t[i]; } }
  return min;
}

{ Test de la présence d'une valeur entiere      }
{ dans un tableau d'entiers                     }
{ sans organisation particuliere                }
{ Methode sequentielle                          }
{ Retour de vrai si présent, faux sinon         }
{ v : Entier recherché                          }
{ t : Le tableau d'entiers de recherche         }

booleen fonction estPresent(-> entier v,
                            -> entier [] t)
  booleen trouve <- faux
  entier i <- 0
  tantque ( trouve == faux ) et ( i < longueur(t) ) faire
    si t[i] == v alors
      trouve <- vrai
      sinon
      i <- i+1
    fsi
  fait
  retourner trouve
fin fonction

/* Fonction de recherche de la presence          */
/* d'une valeur entiere dans un tableau de int   */
/* sans organisation particuliere                */
/* Methode sequentielle                          */
/* Retour de true si présent, false sinon        */
/* v : Entier recherché                          */
/* t : Tableau d'entiers de recherche            */

static boolean estPresent(int v,int [] t) {
  boolean trouve = false;
  int i = 0;
  while ( ( trouve == false ) && ( i < t.length ) ) {
    if ( t[i] == v ) {
      trouve = true; }
      else {
      i++; } }
  return trouve;
}

{ Test de la présence d'une valeur entiere      }
{ dans un tableau d'entiers trie                }
{ par ordre croissant                           }
{ Methode sequentielle                          }
{ Retour de vrai si présent, faux sinon         }
{ v : Entier recherché                          }
{ t : Le tableau d'entiers de recherche         }
{     (trié par ordre croissant)                }

booleen fonction estPresent(-> entier v,
                            -> entier [] t)
  booleen trouve <- faux
  booleen run <- vrai
  entier i <- 0
  tantque run == vrai faire
    si t[i] == v alors
      run <- faux
      trouve <- vrai
      sinon
      si t[i] > v alors
        run <- faux
        sinon
        i <- i+1
        si i == longeur(t) alors
          run <- faux
        fsi
      fsi
    fsi
  fait
  retourner trouve
fin fonction

/* Recherche sequentielle de la presence         */
/* d'un int dans un tableau de int trié          */
/* par ordre croissant                           */
/* Retour de true si présent, false sinon        */
/* v : Entier recherché                          */
/* t : Tableau d'entiers de recherche            */
/*     (trié par ordre croissant)                */

static boolean estPresent(int v,int [] t) {
  boolean run = true;
  boolean trouve = false;
  int i = 0;
  while ( run == true ) {
    if ( t[i] == v ) {
      run = false;
      trouve = true; }
      else {
        if ( t[i] > v ) {
        run = false; }
        else {
        i++;
        if ( i == t.length ) {
          run = false; } } } }
  return trouve;
}

/* Recherche sequentielle de la presence         */
/* d'un int dans un tableau de int trie          */
/* Version optimisee                             */
/* v : Entier recherché                          */
/* t : Tableau d'entiers de recherche            */
/*     (trié par ordre croissant)                */

static boolean estPresent2(int v,int [] t) {
  int i = 0;
  while ( ( i != t.length ) && ( t[i] < v ) ) {
    i++; }
  return ( ( i < t.length ) && ( t[i] == v ) );
}

{ Test de la présence d'une valeur entiere      }
{ dans un tableau d'entiers trie                }
{ par ordre croissant                           }
{ Methode dichotomique                          }
{ Retour de vrai si présent, faux sinon         }
{ v : Entier recherché                          }
{ t : Le tableau d'entiers de recherche         }
{     (trié par ordre croissant)                }

booleen fonction estPresent(-> entier v,
                            -> entier [] t)
  booleen run <- vrai
  booleen trouve <- faux
  entier indi <- 0
  entier indf <- longueur(t)-1
  entier indm
  tantque run == vrai faire
    si indf == indi alors
      si t[indi] == v alors
        trouve <- vrai
      fsi
      run <- faux
      sinon
      si indf == indi+1 alors
        si t[indi] == v ou t[indf] == v alors
          trouve <- vrai
        fsi
        run <- faux
        sinon
        indm <- (indi+indf)/2
        si t[indm] == v alors
          run <- faux
          trouve <- vrai
          sinon
          si v < t[indm] alors
            indf <- indm-1
            sinon
            indi <- indm+1
          fsi
        fsi
      fsi
    fsi
  fait
  retourner trouve
fin fonction

/* Recherche dichotomique de la presence         */
/* d'un int dans un tableau de int trie          */
/* par ordre croissant                           */
/* Retour de true si présent, false sinon        */
/* v : Entier recherché                          */
/* t : Tableau d'entiers de recherche            */
/*     (trié par ordre croissant)                */

static boolean estPresent(int v,int [] t) {
  boolean run = true;
  boolean trouve = false;
  int indi = 0;
  int indf = t.length-1;
  int indm;
  while ( run == true ) {
    if ( indf == indi ) {
      if ( t[indi] == v ) {
        trouve = true; }
      run = false; }
      else {
      if ( indf == indi+1 ) {
        if ( ( t[indi] == v ) || ( t[indf] == v ) ) {
          trouve = true; }
        run = false; }
        else {
        indm = (indi+indf)/2;
        if ( t[indm] == v ) {
          run = false;
          trouve = true; }
          else {
          if ( v < t[indm] ) {
            indf = indm-1; }
            else {
            indi = indm+1; } } } } }
  return trouve ;
}

{ Fonction de recherche et retour                }
{ de la position d'un entier                     }
{ dans un tableau d'entiers                      }
{ trié par ordre croissant                       }
{ et restreint aux indices 0 a n-1 inclus        }
{ (n premières valeurs du tableau)               }
{ v : Valeur entière recherchée                  }
{ n : Nombre de valeurs initiales du tableau     }
{     parmi lesquelles la recherche est réalisée }
{ t : Le tableau trié d'entiers de recherche     }

entier fonction positionInsertion(-> entier v,
                                  -> entier n,
                                  -> entier [] t)
  entier p <- n
  faire
    p <- p-1
  tant que ( ( p >= 0 ) et ( v < t[p] ) )
  p <- p+1
  retourner p
fin fonction

{ Action de décalage de une cellule              }
{ vers la droite du contenu des cellules         }
{ d'indice indi à indice indf inclus             }
{ d'un tableau d'entiers                         }
{ indi : L'indice initial de décalage            }
{ indf : L'indice final de décalage              }
{ t : Le tableau d'entiers où le décalage        }
{     est réalisé                                }

action decalage(-> entier indi,
                -> entier indf,
                -> entier [] t ->)
  entier i
  pour i de indf à indi pas -1 faire
    t[i+1] <- t[i]
  fait
fin action

{ Action de tri "par insertion"                  }
{ par ordre croissant des valeurs                }
{ contenues dans un tableau d'entiers            }
{ t : Le tableau d'entiers à trier               }
{     par ordre croissant                        } 

action triInsertion(-> entier [] t ->)
  entier i
  entier p
  entier v
  pour i de 1 à longueur(t)-1 faire
    p <- positionInsertion(t[i],i,t)
    si p <> i alors
      v <- t[i]
      decalage(p,i-1,t)
      t[p] <- v
    fsi
  fait
fin action

/* Fonction de recherche et retour                */
/* de la position d'un int dans un tableau d'int  */
/* trié par ordre croissant et restreint          */
/* aux indices 0 a n-1 inclus                     */
/* (n premières valeurs du tableau)               */
/* v : Valeur int recherchée                      */
/* n : Nombre de valeurs initiales du tableau     */
/*     parmi lesquelles la recherche est réalisée */
/* t : Tableau trié d'entiers de recherche        */

static int positionInsertion(int v,int n,int [] t) {
  int p = n;
  do {
    p--; }
  while ( ( p >= 0 ) && ( v < t[p] ) );
  return p+1;
}

/* Fonction de décalage de une cellule            */
/* vers la droite du contenu des cellules         */
/* d'indice indi à indf inclus                    */
/* d'un tableau d'int                             */
/* indi : L'indice initial de décalage            */
/* indf : L'indice final de décalage              */
/* t : Le tableau d'int où le décalage            */
/*     est réalisé                                */

static void decalage(int indi,int indf,int [] t) {
  for ( int i = indf ; i >= indi ; i-- ) {
    t[i+1] = t[i]; }
}

/* Fonction de tri "par insertion"                */
/* par ordre croissant des valeurs                */
/* contenues dans un tableau d'int                */
/* t : Le tableau d'int à trier                   */
/*     par ordre croissant                        */

static void triInsertion(int [] t) {
  for ( int i = 1 ; i < t.length ; i++ ) {
    int p = positionInsertion(t[i],i,t);
    if ( p != i ) {
      int v = t[i];
      decalage(p,i-1,t);
      t[p] = v; } }
}

{ Fonction de recherche et retour de l'indice   }
{ de la valeur maximale d'un tableau d'entier   }
{ restreint à ses n+1 premieres valeurs         }
{ n : L'indice inclus jusqu'auquel la recherche }
{     de valeur maximale est réalisée           }
{ t : Le tableau d'entier où la recherche       }
{     de valeur maximale est réalisée           }
  
entier fonction indiceMaximum(-> entier n,
                              -> entier [] t)
  entier iMax <- 0
  entier i
  pour i de 0 à n faire
    si t[i] > t[iMax] alors
      iMax <- i
    fsi
  fait
  retourner iMax
fin fonction
  
{ Action de tri "par selection"                 }
{ par ordre croissant des valeurs contenues     }
{ dans un tableau d'entiers                     }
{ t : Le tableau d'entiers à trier              }
{     par ordre croissant                       }

action triSelection(-> entier [] t ->)
  entier i
  entier aux
  entier iMax
  entier n <- longueur(t)
  pour i de 1 à n-1 faire
    iMax <- indiceMaximum(n-i,t)
    si iMax <> n-i alors
      aux <- t[iMax]
      t[iMax] <- t[n-i]
      t[n-i] <- aux
    fsi
  fait
fin action

/* Fonction de recherche et retour de l'indice   */
/* de la valeur maximale d'un tableau d'int      */
/* restreint à ses n+1 premieres valeurs         */
/* n : L'indice inclus jusqu'auquel la recherche */
/*     de valeur maximale est réalisée           */
/* t : Le tableau d'int où la recherche          */
/*     de valeur maximale est réalisée           */

static int indiceDuMaximum(int n,int [] t) {
  int iMax = 0;
  for ( int i = 1 ; i <= n ; i++ ) {
    if ( t[i] > t[iMax] ) {
      iMax = i; } }
  return iMax;
}

/* Fonction de tri "par selection"               */
/* par ordre croissant des valeurs contenues     */
/* dans un tableau d'int                         */
/* t : Le tableau d'int à trier                  */
/*     par ordre croissant                       */

static void triSelection(int [] t) {
  int n = t.length;
  for ( int i = 1 ; i <= n-1 ; i++ ) {
    int ind = n-i;
    int iMax = indiceDuMaximum(ind,t);
    if ( t[iMax] != t[ind] ) {
      int aux = t[iMax];
      t[iMax] = t[ind];
      t[ind] = aux; } }
}

{ Action de tri à bulle par ordre croissant   }
{ des valeurs contenues                       }
{ dans un tableau d'entiers                   }
{ t : Le tableau d'entiers à trier            }
{     par ordre croissant                     }

action triBulle(-> entier [] t ->)
  entier i
  entier j
  entier aux
  pour i de 0 à longueur(t)-2 faire
    pour j de 0 à longueur(t)-2-i faire
      si t[j] > t[j+1] alors
        aux <- t[j]
        t[j] <- t[j+1]
        t[j+1] <- aux
      fsi
    fait
  fait
fin action

/* Fonction de tri à bulle par ordre croissant   */
/* des valeurs contenues dans un tableau d'int   */
/* t : Le tableau d'int à trier                  */
/*     par ordre croissant                       */

static void triBulle(int [] t) {
  int n = t.length;
  for ( int i = 0 ; i < n-1 ; i++ ) {
    for ( int j = 0 ; j < n-i-1 ; j++ ) {
      if ( t[j] > t[j+1] ) {
        int aux = t[j];
        t[j] = t[j+1];
        t[j+1] = aux; } } }
}

{ Action de tri à bulle par ordre croissant   }
{ des valeurs contenues                       }
{ dans un tableau d'entiers                   }
{ Version optimisée                           }
{ t : Le tableau d'entiers à trier            }
{     par ordre croissant                     }

action triBulleOptimise(-> entier [] t ->)
  entier j
  entier aux
  booleen permutation
  entier np <- longueur(t)-1
  faire
    permutation <- faux
    pour j de 0 à np-1 faire
      si t[j] > t[j+1] alors
        aux <- t[j]
        t[j] <- t[j+1]
        t[j+1] <- aux
        permutation <- vrai
      fsi
    fait
    np <- np-1
  tantque permutation == vrai
fin action

/* Fonction de tri à bulle par ordre croissant   */
/* des valeurs contenues dans un tableau d'int   */
/* Version optimisée                             */
/* t : Le tableau d'int à trier                  */
/*     par ordre croissant                       */

static void triBulleOptimise(int [] t) {
  boolean permutation;
  int np = t.length-1;
  do {
    permutation = false;
    for ( int j = 0 ; j < np ; j++ ) {
      if ( t[j] > t[j+1] ) {
        int aux = t[j];
        t[j] = t[j+1];
        t[j+1] = aux;
        permutation = true; } }
    np--; }
  while ( permutation ) ;
}

{ Action de fusion en un tableau trié               }
{ de deux sous-tableaux contigus triés              }
{ définis au sein d'un tableau d'entiers            }
{ Le sous-tableau 1 contient les t1 entiers         }
{ situés à partir de l'indice i1                    }
{ Le sous-tableau 2 contient les t2 entiers         }
{ situés à partir de l'indice i1+t1                 }
{ t   : Le tableau d'entiers contenant              }
{       les deux sous-tableaux contigus             }
{ i1  : L'indice dans t du premier entier           }
{       du premier sous-tableau                     }
{ t1  : Le nombre d'entiers du premier sous-tableau }
{ t2  : Le nombre d'entiers du second sous-tableau  }

action fusion(-> entier [] t ->,
              -> entier i1,
              -> entier t1,
              -> entier t2)
  entier deb <- i1
  entier i2 <- i1+t1
  entier l <- t1+t2
  entier l1 <- i1+t1
  entier l2 <- l1+t2
  entier [l] tf
  entier i
  pour i de 0 à l-1 faire
    si i1 == l1 alors
      tf[i] <- t[i2]
      i2 <- i2+1
      sinon
      si i2 == l2 alors
        tf[i] <- t[i1]
        i1 <- i1+1
        sinon
        si t[i1] < t[i2] alors
          tf[i] <- t[i1]
          i1 <- i1+1
          sinon
          tf[i] <- t[i2]
          i2 <- i2+1
        fsi
      fsi
    fsi
  fait
  pour i de 0 à l-1 faire
    t[deb+i] <- tf[i]
  fait
fin action

{ Action de tri par fusion par ordre croissant      }
{ d'un tableau d'entiers des indices indi           }
{ à indf compris                                    }
{ t    : Le tableau d'entiers à trier               }
{        par ordre croissant                        }
{ indi : L'indice initial des valeurs à trier       }
{ indf : L'indice final des valeurs à trier         }

action triFusion(-> entier [] t ->,
                 -> entier indi,
                 -> entier indf)
  entier nbVal <- indf-indi+1
  entier iMedian
  entier aux
  si nbVal > 1 alors
    si nbVal == 2 alors
      si t[indf] < t[indi] alors
        aux <- t[indi]
        t[indi] <- t[indf]
        t[indf] <- aux
      fsi
      sinon
      iMedian <- (indi+indf)/2
      triFusion(t,indi,iMedian)
      triFusion(t,iMedian+1,indf)
      fusion(t,indi,iMedian-indi+1,indf-iMedian)
    fsi
  fsi
fin action

{ Action de tri par fusion par ordre croissant      }
{ d'un tableau d'entiers                            }
{ t : Le tableau d'entiers à trier                  }
{     par ordre croissant                           }

action triFusion(-> entier [] t ->)
  triFusion(t,0,longueur(t)-1)
fin action

/* Action de fusion en un tableau trié               */
/* de deux sous-tableaux contigus triés              */
/* définis au sein d'un tableau d'entiers            */
/* Le sous-tableau 1 contient les t1 entiers         */
/* situés à partir de l'indice i1                    */
/* Le sous-tableau 2 contient les t2 entiers         */
/* situés à partir de l'indice i1+t1                 */
/* t   : Le tableau d'entiers contenant              */
/*       les deux sous-tableaux contigus             */
/* i1  : L'indice dans t du premier entier           */
/*       du premier sous-tableau                     */
/* t1  : Le nombre d'entiers du premier sous-tableau */
/* t2  : Le nombre d'entiers du second sous-tableau  */

static void fusion(int [] t,int i1,int t1,int t2) {
  int deb = i1;
  int i2 = i1+t1;
  int l = t1+t2;
  int l1 = i1+t1;
  int l2 = l1+t2;
  int [] tf = new int[l];
  for ( int i = 0 ; i < l ; i++ ) {
    if ( i1 == l1 ) {
      tf[i] = t[i2];
      i2++; }
      else {
      if ( i2 == l2 ) {
        tf[i] = t[i1];
        i1++; }
        else {
        if ( t[i1] < t[i2] ) {
          tf[i] = t[i1];
          i1++; }
          else {
          tf[i] = t[i2];
          i2++; } } } }
  for ( int i = 0 ; i < l ; i++ ) {
    t[deb+i] = tf[i]; }
}

/* Fonction de tri par fusion                        */
/* par ordre croissant d'un tableau d'entiers        */
/* des indices indi a indf compris                   */
/* t    : Le tableau d'int à trier                   */
/*        par ordre croissant                        */
/* indi : L'indice initial des valeurs à trier       */
/* indf : L'indice final des valeurs à trier         */

static void triFusion(int [] t,int indi,int indf) {
  int nbVal = indf-indi+1;
  if ( nbVal > 1 ) {
    if ( nbVal == 2 ) {
      if ( t[indf] < t[indi] ) {
        int aux = t[indi];
        t[indi] = t[indf];
        t[indf] = aux; } }
      else {
      int iMedian =(indi+indf)/2;
      triFusion(t,indi,iMedian);
      triFusion(t,iMedian+1,indf);
      fusion(t,indi,iMedian-indi+1,indf-iMedian); } }
}

/* Fonction de tri par fusion                        */
/* par ordre croissant d'un tableau d'int            */
/* t : Le tableau d'int à trier                      */
/*     par ordre croissant                           */

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

{ Fonction de reorganisation d'un tableau t     }
{ d'entiers des indices indi a indf inclus      }
{ par replaçage à gauche de toutes les valeurs  }
{ plus petites que t[pivot], à droite de toutes }
{ les valeur plus grande que t[pivot]           }
{ et au centre de toutes les valeurs egales     }
{ à t[pivot]                                    }
{ Retourne l'indice de la valeur d'indice       }
{ maximum, apres replaçage, de toutes           }
{ les valeurs égales à t[pivot]                 }

entier fonction pivotage(-> entier [] t ->,
                         -> entier indi,
                         -> entier indf,
                         -> entier pivot)
  entier i
  entier j <- indi
  entier aux <- t[pivot]
  t[pivot] <- t[indf]
  t[indf] <- aux
  pour i de indi à indf-1 faire
    si t[i] <= t[indf] alors
      aux <- t[i]
      t[i] <- t[j]
      t[j] <- aux
      j <- j+1
    fsi
  fait
  aux <- t[indf]
  t[indf] <- t[j]
  t[j] <- aux
  retourner j
fin fonction

{ Action de tri rapide par ordre croissant      }
{ d'un tableau d'entiers des indices indi       }
{ à indf compris                                }
{ Méthode de choix du pivot : Valeur située     }
{ à l'indice moyen de indi et indf              }
{ t    : Le tableau d'entiers à trier           }
{        par ordre croissant                    }
{ indi : L'indice initial des valeurs à trier   }
{ indf : L'indice final des valeurs à trier     }

action triRapide(-> entier [] t ->,
                 -> entier indi,
                 -> entier indf)
  entier iMedian
  entier aux
  entier pivot
  entier nbVal <- indf-indi+1
  si nbVal > 1 alors
    si nbVal == 2 alors
      si t[indf] < t[indi] alors
        aux <- t[indi]
        t[indi] <- t[indf]
        t[indf] <- aux
      fsi
      sinon
      pivot <- (indi+indf)/2
      iMedian <- pivotage(t,indi,indf,pivot)
      triRapide(t,indi,iMedian-1)
      triRapide(t,iMedian+1,indf)
    fsi
  fsi
fin action

{ Action de tri rapide par ordre croissant      }
{ d'un tableau d'entiers                        }
{ Pivot choisi : Valeur médiane du tableau      }
{ t : Le tableau d'entiers à trier              }
{     par ordre croissant                       }

action triRapide(-> entier [] t ->)
  triRapide(t,0,longueur(t)-1)
fin action

/* Fonction de reorganisation d'un tableau       */
/* d'entiers des indices indi a indf inclus      */
/* par replacage a gauche de toutes les valeurs  */
/* plus petites que t[pivot], a droite de toutes */
/* les valeurs plus grandes que t[pivot]         */
/* et au centre de toutes les valeurs egales     */
/* a t[pivot]                                    */
/* Retourne l'indice de la valeur d'indice       */
/* maximum, apres replacage, de toutes           */
/* les valeurs egales a t[pivot]                 */

static int pivotage(int [] t,int indi,int indf,int pivot) {
  int j = indi;
  int aux = t[pivot];
  t[pivot] = t[indf];
  t[indf] = aux;
  for ( int i = indi ; i < indf ; i++ ) {
    if ( t[i] <= t[indf] ) {
      if ( i != j ) {
        aux = t[i];
        t[i] = t[j];
        t[j] = aux; }
      j++; } }
  if ( indf != j ) {
    aux = t[indf];
    t[indf] = t[j];
    t[j] = aux; }
  return j;
}

/* Fonction de tri rapide par ordre croissant    */
/* d'un tableau d'int des indices                */
/* indi a indf compris                           */
/* Méthode de choix du pivot : Valeur située     */
/* à l'indice moyen de indi et indf              */
/* t    : Le tableau d'int à trier               */
/*        par ordre croissant                    */
/* indi : L'indice initial des valeurs à trier   */
/* indf : L'indice final des valeurs à trier     */

static void triRapide(int [] t,int indi,int indf) {
  int nbVal = indf-indi+1;
  if ( nbVal > 1 ) {
    if ( nbVal == 2 ) {
      if ( t[indf] < t[indi] ) {
        int aux = t[indi];
        t[indi] = t[indf];
        t[indf] = aux; } }
      else {
      int pivot = (indi+indf)>>1;
      int iMedian = pivotage(t,indi,indf,pivot);
      triRapide(t,indi,iMedian-1);
      triRapide(t,iMedian+1,indf); } }
}

/* Fonction de tri rapide par ordre croissant    */
/* d'un tableau d'int                            */
/* Pivot choisi : Valeur médiane du tableau      */
/* t : Le tableau d'int à trier                  */
/*     par ordre croissant                       */

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