Introduction à l'algorithmique 14 - Le tri rapide

Bonjour à tous! Comme prévu aujourd'hui on va voir un autre algorithme de tri, plus performant que le tri à bulles: il s'agit du "tri rapide" (aussi appelé "Quick sort").

Cet algorithme est un peu plus exotique que celui du tri à bulles, il fait appel à plusieurs notions importantes: notamment la récursivité. Si vous n'êtes pas encore à l'aise avec ce concept, je vous invite à revoir <a title="Fonctions récursives" href="https://www.demily-clement.com/2013-10-30-introduction-a-lalgorithmique-11-les-fonctions-recursives.html">ce billet</a>.

Le principe de cet algorithme est de placer un "pivot", puis de faire passer les valeurs plus petites que ce pivot à gaucheet de faire passer les valeurs plus grandes à droitede celui-ci.

On appellera cette étape le partitionnement du tableau. Cette étape est répétée récursivement, sur tous les sous-tableaux! "diviser pour régner"

Pseudo-code de la fonction principale:

DéBUT
tab <- [5, 6, 42, 1, 5, 2, 121, 9, 8, 7, 3, 12, 0, 38, 33, 25, 23, 87, 96]
  ECRIRE "Voici le tableau a trier", tab
  ECRIRE "Voici le tableau trié", QUICK_SORT(tab, 1, COMPTER(tab))
FIN

Pseudo-code de la fonction PARTITIONNER:

ENTRER REFERENCE tab, index_debut, taille
  pivot <- tab[index_debut]
  index_gauche <- p - 1
  index_droite <- taille + 1
  boucler <- 1
  TANTQUE boucler = 1 FAIRE
    RéPéTER
      index_droite <- index_droite - 1
    JUSQU'à tab[index_droite] <= pivot
    RéPéTER
      index_gauche <- index_gauche + 1
    JUSQU'à tab[index_gauche] >= pivot
    SI index_gauche < index_droite ALORS
      tmp <- tab[index_gauche]
      tab[index_gauche] <- tab[index_droite]
      tab[index_droite] <- tmp
    SINON
      boucler <- 0
    FINSI
  FINTANTQUE
RETOURNER index_droite

Comme expliqué plus haut, le principe de l'algorithme réside en partie dans cette fonction.

J'aimerais juste revenir sur le mot-clé REFERENCE. Vous avez du le remarquer: les paramètres des fonctions ne gardent pas les modifications que l'on fait dans le corps de la fonction. Les paramètres sont donc des variables copiéesdepuis la fonction principale. (dans ce cas)

Le seul moyen que l'on connaissait jusqu'à présent pour récupérer des informations d'une fonction était par la valeur de retour.

Le mot-clé REFERENCE sert à contrer ce problème, maintenant toutes modifications sur la variable "tab" sera répercutée partout dans l'algorithme.

Cet aparté fait, on peut revenir à la suite de l'algorithme!

Pseudo-code de la fonction QUICK_SORT:

ENTRER tab, index_debut, taille
  SI index_debut < taille ALORS
    index_droite <- PARTITIONNER(tab, index_debut, taille)
    QUICK_SORT(tab, index_debut, index_droite)
    QUICK_SORT(tab, index_droite + 1, taille)
  FINSI
RETOURNER tab

J'ai essayé de donner un nom clair à mes variables, afin que ça soit le plus simple possible à comprendre.

Je vous conseille une fois de plus de regarder l'exécution pas à pas pour bien tout comprendre.

Un mot sur la complexité algorithmique du tri rapide:

• Pour le meilleurs des cas (tableau trié): O(n)
• Pour un cas moyen: O(nlog(n))
• Pour le pire des cas: O(n²)

En vérité, la complexité algorithmique varie beaucoup selon la manière de la sélection du pivot: pour une sélection arbitraire, la complexité algorithmique tend plus vers le O(n²). En revanche, pour un pivot aléatoire ou un pivot optimal, la complexité algorithmique passe en O(nlog(n)).

La récursivité est certainement l'une des notions les plus délicates à appréhender pour les débutants. C'est un peu "mystique" aux premières utilisations, mais à force de pratique on prend conscience du plein potentiel de cette technique!

Je vous propose de voir demain un problème algorithmique très connu!

A demain!