introduction
Le tri d'un tableau est l'un des premiers problèmes sérieux étudiés dans le cours classique «Algorithmes et structures de données» de la discipline informatique. A cet égard, les tâches de tri des écritures et les questions correspondantes sont souvent rencontrées dans les entretiens pour le poste de stagiaire ou développeur junior.
Formulation du problème
Traditionnellement, il vaut la peine de commencer la présentation des solutions au problème avec son énoncé. Habituellement, la tâche de tri consiste à classer un tableau d'entiers dans l'ordre croissant. Mais en fait, c'est un peu une simplification excessive. Les algorithmes décrits dans cette section peuvent être utilisés pour ordonner un tableau de tous les objets entre lesquels une relation de classement est établie (c'est-à-dire que pour deux éléments quelconques, nous pouvons dire: le premier est supérieur au second, le second est supérieur au premier, ou ils sont égaux). Vous pouvez trier dans l'ordre croissant et décroissant. Nous utiliserons la simplification standard.
Tri rapide
La dernière fois, nous avons parlé d'un tri un peu plus complexe - tri par insertion. Aujourd'hui, nous allons nous concentrer sur un algorithme beaucoup plus complexe - le tri rapide (également appelé tri Hoare).
Description de l'algorithme
L'algorithme de tri rapide est récursif, par conséquent, pour plus de simplicité, la procédure prendra en entrée les limites du segment de tableau de l inclus à r non inclus. Il est clair que pour trier le tableau entier, vous devez passer 0 comme paramètre l, et n comme r, où, par tradition, n désigne la longueur du tableau.
L'algorithme de tri rapide est basé sur la procédure de partition. La partition sélectionne un élément du tableau et réorganise les éléments de la section du tableau de sorte que le tableau soit divisé en 2 parties: la partie gauche contient des éléments inférieurs à cet élément et la partie droite contient des éléments supérieurs ou égaux à cet élément. Cet élément de séparation est appelé un pivot .
Mise en œuvre du Partiion:
partition(l, r):
pivot = a[random(l ... r - 1)]
m = l
for i = l ... r - 1:
if a[i] < pivot:
swap(a[i], a[m])
m++
return m
Le pivot dans notre cas est choisi au hasard. Cet algorithme est appelé randomisé . En fait, le pivot peut être sélectionné de différentes manières: soit prendre un élément aléatoire, soit prendre le premier / dernier élément de la section, soit le sélectionner de manière «intelligente». Le choix du pivot est très important pour la complexité finale de l'algorithme de tri, mais nous y reviendrons plus tard. La complexité de la procédure de partition est O (n), où n = r - l est la longueur de la section.
Maintenant, nous utilisons la partition pour implémenter le tri:
Implémentation de Partiion:
sort(l, r):
if r - l = 1:
return
m = partition(l, r)
sort(l, m)
sort(m, r)
Un cas extrême - un tableau d'un élément a la propriété d'être ordonné. Si le tableau est long, alors nous utilisons la partition et appelons la procédure de manière récursive sur les deux moitiés du tableau.
Si vous exécutez le tri écrit sur l'exemple du tableau 1 2 2, vous remarquerez qu'il ne se terminera jamais. Pourquoi est-ce arrivé?
Lors de l'écriture de la partition, nous avons fait une hypothèse - tous les éléments du tableau doivent être uniques. Sinon, la valeur de retour de m sera l et la récursion ne se terminera jamais, car sort (l, m) appellera sort (l, l) et sort (l, m). Pour résoudre ce problème, vous devez diviser le tableau non pas en 2 parties (<pivot et> = pivot), mais en 3 parties (<pivot, = pivot,> pivot) et appeler le tri récursif pour les 1ère et 3ème parties.
Une analyse
Je propose d'analyser cet algorithme.
La complexité temporelle de l'algorithme est exprimée à travers lui par la formule: T (n) = n + T (a * n) + T ((1 - a) * n). Ainsi, lorsque l'on appelle le tri d'un tableau de n éléments, il faut environ n opérations pour exécuter la partition et pour s'exécuter 2 fois avec les paramètres a * n et (1 - a) * n, car le pivot a divisé l'élément en fractions.
Dans le meilleur des cas, a = 1/2, c'est-à-dire que le pivot divise la zone en deux parties égales à chaque fois. Dans ce cas: T (n) = n + 2 * T (n / 2) = n + 2 * (n / 2 + 2 * T (n / 4)) = n + n + 4 * T (n / 4 ) = n + n + 4 * (n / 4 + 2 * T (n / 8)) = n + n + n + 8 * T (n / 8) =…. Le total sera des termes log (n), car les termes apparaissent jusqu'à ce que l'argument diminue à 1. Par conséquent, T (n) = O (n * log (n)).
Dans le pire des cas, a = 1 / n, c'est-à-dire que le pivot coupe exactement un élément. La première partie du tableau contient 1 élément et la seconde contient n - 1. Soit: T (n) = n + T (1) + T (n - 1) = n + O (1) + T (n - 1) = n + O (1) + (n - 1 + O (1) + T (n - 2)) = O (n ^ 2). Le carré apparaît du fait qu'il apparaît dans la formule pour la somme d'une progression arithmétique qui apparaît dans le processus de griffonnage de la formule.
En moyenne, idéalement, l'attente mathématique de diverses options devrait être prise en compte. On peut montrer que si le pivot divise le tableau dans un rapport de 1: 9, les asymptotiques résultantes seront toujours O (n * log (n)).
Le tri est appelé rapide, car la constante cachée sous le signe O se révèle assez petite en pratique, ce qui a conduit à une utilisation généralisée de l'algorithme dans la pratique.
Lire la suite
