Programmes de tri

Préambule

Dans cette partie, nous allons montrer comment créer des programmes de tri sur des tableaux. Ces programmes sont basés sur des algorithmes de tri classiques enseignés dans toutes les filières de formation à la programmation.

Tri par sélection

Le tri par sélection consiste à parcourir un tableau de valeurs pour sélectionner la plus grande valeur et la placer en première position. Ensuite, il suffit de parcourir à nouveau le tableau pour placer la deuxième plus grande valeur et ainsi de suite. 

Construction du tri par sélection

La vidéo présente comment construire un programme basé sur ce principe. Plusieurs méthodes sont possibles répondant à ce principe. Dans cette version, pour placer la plus grande valeur à l’indice i, on compare successivement les valeurs d’indice supérieur. Dès qu’une valeur est plus grande, on l’échange avec la valeur d’indice i.

Programme AlgoTouch de tri par sélection

Voici un programme similaire réalisé avec la nouvelle version d’AlgoTouch. Dans ce programme les données sont triées par ordre croissant. Pour commencer, la plus petite valeur est placée en première position, puis la plus petite valeur suivante est placée en seconde position, etc.  Contrairement à l’algorithme précédent, à une étape donnée i, l’algorithme utilisé cherche la position de la plus petite valeur (son indice) avant de la mettre à sa place par échange avec la position i. Dans la version précédente, à chaque fois qu’une valeur était plus petite que la valeur courante, on l’échangeait avec la valeur courante.

Ce programme utilise 3 macros:

  1. triSelection effectue le tri complet
  2. positionMin détermine la position de la plus petite valeur à partir de l’indice i
  3. swap échange la valeur à l’indice i avec celle à la position min

On peut lancer le programme triSelection soit en mode pas à pas, soit en mode automatique, soit en mode sans interruption. On peut aussi voir comment fonctionne le programme positionMin en le lançant après plusieurs étapes de triSelection. La encore, les modes pas à pas et automatique sont à privilégier.

Tri par insertion

Le tri par insertion repose sur le principe suivant : si les n premières valeurs du tableau sont déjà triées, placer la valeur suivante consiste à l’insérer parmi ces valeurs.

Construction du tri par insertion

Plusieurs programmes permettent de réaliser le tri par insertion. Cette vidéo présente une version dans laquelle lorsqu’il s’agit d’insérer l’élément d’indice i dans le sous tableau t[0..i-1], on l’échange avec l’élément d’indice i-1. Puis on recommence si nécessaire en échangeant avec l’élément d’indice i-2, jusqu’à ce qu’il soit correctement placé.

Programme AlgoTouch de tri par insertion

Voici une autre version du tri par insertion en AlgoTouch. Le principe général de l’algorithme reste le même. Seule la méthode pour insérer une valeur est différente. Dans cette version, à l’étape i, la valeur t[i] est stockée dans une variable val. Les éléments d’indice inférieur à i sont décalés à droite tant qu’ils sont supérieurs à val. Lorsque ce n’est plus le cas, la valeur val est placée juste après.

Le programme contient 2 macros:

  1. triInsertion effectue le tri complet
  2. insererEltOrdreI insère l’élément d’indice i

On peut lancer le programme triInsertion soit en mode pas à pas, soit en mode automatique, soit en mode sans interruption. On peut aussi voir comment fonctionne le programme insererElementOrdreI en le lançant après plusieurs étapes de triInsertion. La encore, les modes pas à pas et automatique sont à privilégier. A noter que ce programme n’effectue pas d’opération d’échange, certaines valeurs sont uniquement décalées d’une position.

Tri bulles

Le principe du tri bulle est très simple. Parcourir un tableau, tant que deux éléments consécutifs sont non ordonnés, les échanger. Parcourir à nouveau le tableau et s’arrêter lorsqu’aucun échange n’a été effectué. C’est que les éléments sont dans l’ordre.

Programme de tri bulles

Voici un programme de tri bulles en AlgoTouch qui s’inspire du principe énoncé plus haut. Le programme est constitué de 2 macros :

  1. TriBulles qui effectue le tri complet
  2. Parcours qui effectue un passage sur le tableau pour effectuer des échanges si nécessaires

Une variable permut, initialisée à 0,  est utilisée pour savoir si une permutation à été effectuée pendant un parcours. Dans ce cas, elle passe à 1. Elle permet d’arrêter les parcours si sa valeur est restée à 0.

Tri par séparation

Le principe du tri par séparation consiste d’abord à séparer le tableau en deux parties puis à trier chacune des parties indépendamment. Un algorithme de séparation consiste d’abord à choisir une valeur, appelée pivot. Puis à placer toutes les valeurs du tableau inférieures ou égales à gauche du pivot et les valeurs supérieures à droite du pivot. Il suffit alors de trier la partie gauche puis la partie droite du pivot. Pour réaliser ce tri, on fait appel à la récursivité.

 

Pour illustrer le principe de séparation, considérons le tableau ci-contre. On choisit la première valeur (50) comme pivot.

Après séparation, le pivot a été déplacé à l’indice 5. Toutes les valeurs d’indice inférieur sont inférieures au pivot et toutes les valeurs d’indice supérieur sont supérieures au pivot. 

Le tri par séparation est le tri le plus rapide, on l’appelle communément QuickSort. Ce tri ne peut être réalisé directement avec AlgoTouch puisqu’il nécessite la prise en charge de la récursivité. C’est une notion extrêmement puissante mais non abordée dans le cadre que nous avons choisi : l’apprentissage de la programmation à des débutants. Cependant, nous pouvons programmer un algorithme de séparation des valeurs d’un tableau. 

Exemple de programme de séparation

Il existe de multiples façons de séparer un tableau. Voici un exemple. Ce programme sépare un tableau a entre les indices g et d avec comme pivot la valeur de a[g]. Le résultat est un tableau dont toutes les valeurs “à gauche” sont inférieures ou égales au pivot et toutes les valeurs “à droite” sont supérieures au pivot. La variable s contient l’indice où a été déplacé le pivot.

Le principe est le suivant :

  • on définit le pivot comme étant la première valeur du tableau
  • on parcourt le tableau de gauche à droite
  • tant que les valeurs sont inférieures ou égales au pivot, on avance
  • lorsqu’on trouve une valeur plus grande, on la place en fin de tableau. Pour cela, on l’échange avec t[d], et on décrémente d. Ainsi les valeurs supérieures au pivot seront placées à la suite depuis la fin du tableau jusqu’à d (exclu)
  • le processus s’arrête lorsque la dernière valeur a été traitée

Le programme est constitué de 2 macros :

  1. Partition qui réalise la séparation du tableau entre les indices g (gauche) et d (droit). Le pivot est défini en g. En résultat, s est le nouvel indice du pivot, les valeurs d’indice inférieur à s sont inférieures ou égales au pivot et les valeurs d’indice supérieur à s sont supérieures au pivot
  2. Adroite qui envoie “à droite” une valeur supérieure au pivot. Plus précisément, en fin de tableau à partir de l’indice d.

Avant de lancer le programme Partition, il faut vérifier que les indices g et d définissent bien les bornes du tableau à séparer. Lorsque le tableau a été séparé une première fois, on peut relancer le programme Partition sur la partie gauche du pivot, puis sur la partie droite. A chaque fois la valeur du pivot est à sa place et il suffit de séparer à nouveau les deux sous tableaux.

Bien sur, ce procédé est fastidieux mais il a le mérite d’illustrer le principe de fonctionnement d’un algorithme de séparation. En moyenne, cet algorithme est le plus rapide.