Algorithme de Las Vegas

L'algorithme de tri rapide aléatoire, ou quicksort randomisé consiste à trier un tableau d'éléments en utilisant diviser pour régner :

1. choisir aléatoirement un pivot (i.e. un élément du tableau) ;
2. partitionner le tableau en plaçant les éléments strictement plus petits que le pivot à gauche (sous-tableau A), puis le pivot, puis les éléments plus grands que le pivot (sous-tableau B) ;
3. trier récursivement les sous-tableaux A et B.

Le résultat est un tableau constitué d'un tri du tableau A, suivi du pivot, suivi d'un tri du tableau B.

On effectue l'algorithme de tri rapide randomisé sur un exemple. Les pivots successifs sont surlignés en gris.

On effectue l'algorithme de tri rapide randomisé sur le même exemple en surlignant en gris les pivots successifs. On obtient un autre ordre de tri

L'aléatoire se situe au niveau du choix des pivots. Le résultat est un tableau trié, quels que soient les choix de pivots, i.e. le résultat est toujours correct. En revanche, le temps d'exécution dépend de ces choix. C'est, en fait, un tri souvent utilisé sur des tableaux de grandes tailles parce que, de manière empirique, il donne de bons résultats en complexité temporelle[5]. Dans les figures à droite, l'algorithme est exécuté deux fois sur le même échantillon ; on voit que l'on obtient un tableau trié dans les deux cas, alors que les pivots sont choisis aléatoirement.

• Si l'algorithme choisit toujours le pivot le plus petit (ou le plus grand)[6], alors le partitionnement est déséquilibré. Le temps d'exécution vérifie l'équation de récurrence ${\displaystyle T(n)=T(0)+T(n-1)+\Theta (n)}$ et on a ${\displaystyle T(n)=\Theta (n^{2})}$.
• Si l'algorithme pouvait choisir toujours le pivot médian, c'est-à-dire au milieu du tableau (par une sorte d'oracle), la relation de récurrence serait ${\displaystyle T(n)\leq 2*T(n/2)+\Theta (n)}$et on a ${\displaystyle T(n)=\Theta (nlog(n))}$.

Pour simuler l'oracle, on prend un choix aléatoire du pivot en espérant qu'il nous donnera souvent un pivot situé pas très loin de la médiane.

La version Las Vegas du tri rapide choisit aléatoirement le pivot dans la liste à trier, tout en gardant le reste de l'algorithme inchangé. En voici le code en langage Python :

# Import des modules nécessaires
from random import *		# Outils et fonctions d'aléatoires
# Fonction de séparation de listes selon le pivot
def separation(liste, pivot, n):
	"""
		Entrée: une liste, un pivot et la place du pivot dans la liste
		Sortie: deux listes
		- la première contenant les éléments plus petits que le pivot
		- la seconde contenant les éléments plus grands ou égal au pivot
	"""
	# Les listes à remplir
	listePetit = []
	listeGrand = []
	# Traitement liste à séparer
	for (i, x) in enumerate(liste):
		# Exclusion du pivot
		if i == n: continue
		# Séparation
		if x >= pivot: listeGrand.append(x)
		else: listePetit.append(x)
	# for
	# On renvoie le tuple contenant les deux listes
	return (listePetit, listeGrand)
# separation()
# Fonction tri rapide
def quicksort(liste):
	"""
		Entrée: une liste
	  	Sortie: la liste triée
	"""
	# Longueur de la liste
	n = len(liste)
	# Une liste vide ou à un élément est toujours triée
	if n <= 1: return liste 
	# Choix du pivot au hasard dans la liste
	i = randint(0, n - 1) 
	pivot = liste[i]
	# Séparation de la liste en deux sur le pivot
	(petit, grand) = separation(liste, pivot, i) 
	# Appel récursif sur chacune des listes et regroupement des résultats
	return quicksort(petit) + [pivot] + quicksort(grand)
# quicksort()

Un algorithme de Las Vegas est un algorithme probabiliste (utilisant le hasard) qui fournit toujours un résultat juste. Ainsi, l'algorithme renverra toujours une solution au problème posé mais sa complexité temporelle n'est pas prévisible. Par des bons choix lors des points clés de l'exécution de l'algorithme, on doit pouvoir montrer que cette complexité est faible.

Ces algorithmes ont été ainsi nommés par Laszlo Babai en 1979 par métonymie avec les algorithmes de Monte-Carlo. On nommera par la suite une troisième famille d'algorithmes probabilistes les algorithmes d'Atlantic City, en référence aux nombreux jeux d'argent se déroulant dans ces trois villes.

Les algorithmes de Monte-Carlo sont des algorithmes probabilistes qui utilisent le hasard pour renvoyer la meilleure réponse possible en un temps fixé. La complexité temporelle est donc fixé pour ces algorithmes. Cependant, la justesse du résultat est soumise à une incertitude.

Les algorithmes d'Atlantic City essayent de tirer le meilleur des deux méthodes précédentes. Ce type d'algorithme renverra presque toujours un résultat juste en un temps presque toujours fixé. L'incertitude se situe donc sur la complexité temporelle et sur la justesse du résultat.

Exprimé autrement :

• un algorithme de Las Vegas s'arrête quand il a trouvé une réponse exacte ;
• un algorithme de Monte-Carlo répond dans un temps prévisible et court sans pour autant garantir une réponse exacte (voir tests de primalité probabilistes) ;
• un algorithme d'Atlantic City est relativement rapide et donne une réponse exacte avec une bonne garantie de l'exactitude.