Etape 5: Mise en œuvre de qs_partition
Arrière-plan
Avant de se déplacer à la mise en œuvre de la fonction quick_sort, nous devons comprendre que quick_sort ne fait pas beaucoup de travail en soi. Notre fonction qs_partition accomplit l’essentiel du travail. qs_partition accepte comme paramètres un tableau d’entiers, une limite gauche dans ce tableau et une limite droite dans ce tableau et retourne un entier, tout comme la principale.
* Note : parce qu’une bibliothèque que nous utilisons (algorithm.h) déjà a une fonction appelée partition, nous appellerons notre fonction de partition qs_partition.
Objectif
Le travail de qs_partition est de choisir un nombre dans le tableau comme un pivot et diviser tous les nombres dans le tableau en deux groupes : celles qui sont inférieures ou égales à pivot et ceux qui sont plus importants. Il place tous les numéros de moindre ou égales avant le pivot et tous les numéros de plus après. Voici une façon qui peut être accomplie.
Mesures
1) qs_partition tout d’abord la première chose qu’il est autorisé à toucher (la question à la limite de gauche) et il appelle un pivot. Il n’y a rien de spécial se passe ici. La fonction tout d’abord se déclarer qu’une valeur appelée pivot est égale au premier élément pour lequel la fonction est autorisée à accéder.
2) de la même manière, nous appeler une variable interchangeables et affecter l' index du pivot.
3) nous traversent ensuite le tableau, en regardant chaque élément de la deuxième valeur à la limite droite. Nous ne comparons la première valeur à la valeur du pivot car la première valeur est la valeur pivot.
4) à chaque endroit, nous comparons la valeur à cet endroit pour notre pivot. Si cette valeur est inférieure ou égale à la pivot, nous voulons passer cette valeur aussi loin vers le début du tableau que possible. C’est là qu’intervient interchangeables. Nous allons permuter les valeurs à interchangeables (car interchangeables est un index) et la valeur actuelle, nous assistons, puis nous augmenterons interchangeables par l’un, donc nous ne sommes pas ceux permutation des valeurs de retour dans le milieu du tableau.
5) une fois que nous avons parcouru tous les nombres, notre indice d’interchangeables représentera l’endroit où l'on veut placer notre pivot. Donc nous allons échanger la valeur à interchangeables et le pivot. Enfin, nous allons retourner ou transmettre à la fonction qui a appelé qs_partition, l’index d’où nous mettons le pivot. Vous verrez pourquoi bientôt.
Examen
J’espère que vous pouvez voir que par la permutation dans l’ordre nombres inférieurs à la pivot dans le premier spot après notre dernier échange, nous avons créé l’effet désiré : tous les chiffres avant le pivot sont inférieures ou égales à la pivot et tous les numéros après lui sont supérieures.
