QuickSort et Hoare Partition

Pour répondre à la question "Pourquoi ne Hoare partitionnement de travail?":

Simplifions les valeurs dans le tableau de trois sortes: L valeurs (celles de moins que le pivot de la valeur), E valeurs (celles égale à la valeur pivot), et G valeur (ceux plus grands que le pivot de la valeur).

Nous allons aussi donner un nom spécial à un seul endroit dans le tableau; nous l'appellerons cet emplacement set c'est l'endroit où l' j pointeur est lorsque la procédure se termine. - Nous savoir à l'avance à quel endroit s est? Non, mais nous savons que certains emplacement de répondre à cette description.

Avec ces conditions, nous pouvons exprimer l'objectif de la procédure de partitionnement dans des termes légèrement différents: il consiste à diviser un groupe en deux sous-ensembles qui sont pas mal triés à l'égard les uns des autres. Que "pas mal triés" exigence est satisfaite si les conditions suivantes sont remplies:

1. Le "bas" de la sous-matrice, qui va de l'extrémité gauche du tableau et comprend sne contient pas de G valeurs.
2. Le "haut" de la sous-matrice, qui commence immédiatement après s et continue à l'extrémité droite, ne contient pas de L valeurs.

C'est vraiment tout ce que nous devons faire. Nous n'avons même pas besoin de s'inquiéter lorsque le E valeurs de liquidation sur tout passer. Tant que chaque laissez-passer de la sous-matrices de droit à l'égard les uns des autres, plus tard, passe va prendre soin de tout le désordre qui existe à l'intérieur d'un sous-tableau.

Alors maintenant, nous allons traiter de la question de l'autre côté: comment fonctionne la procédure de partitionnement s'assurer qu'il n'y a pas G valeurs dans s ou à gauche de celle-ci, et pas de L les valeurs à droite de s?

Bien, "l'ensemble des valeurs à droite de s" est le même que "l'ensemble des cellules de la j pointeur se déplace avant qu'il n'atteigne s". Et "l'ensemble des valeurs de la gauche et notamment s" est le même que "l'ensemble des valeurs que la je pointeur se déplace avant j atteint s".

Qui signifie que toutes les valeurs qui sont mal placée, sur une itération de la boucle, dans l'une de nos deux pointeurs. (Pour plus de commodité, disons que c'est le j pointeur pointant sur un L valeur, si elle fonctionne exactement de même pour le je pointeur pointant sur un G valeur.) D'où l' je pointeur, lorsque le j pointeur est sur un égaré de la valeur? Nous savons qu'il sera:

1. à un emplacement dans le "faible" subarray, où la L valeur peut aller sans problèmes;
2. pointant à une valeur qui est soit un E ou un G valeur, qui peut facilement remplacer le L valeur sous la j pointeur. (Si il n'était pas sur un E ou un G valeur, il n'aurait pas arrêté là.)

Noter que, parfois, la je et j pointeur de la réalité à la fois s'arrêter sur E valeurs. Lorsque cela se produit, les valeurs seront allumés, même si il n'est pas nécessaire pour cela. Ce n'est pas plus mal, bien que nous l'avons dit avant que le placement de la E valeurs ne peuvent pas causer de mal le tri entre les sous-tableaux.

Donc, pour résumer, Hoare partitionnement fonctionne parce que:

1. Il se sépare d'un tableau en plus petits sous-ensembles qui ne sont pas mal triés les uns par rapport aux autres;
2. Si vous continuez à faire cela et de tri de manière récursive, le sous-tableaux, finalement il n'y aura rien à gauche du tableau non trié.

Vous dernier C un code qui fonctionne. Mais ce n'est pas intuitive.
Et maintenant, je suis étudiant en CLRS heureusement.
À mon avis, Le pseudo-code de PLC est mauvais.(2e)
Enfin, je trouve que ce serait bon si la modification d'un lieu.

 Hoare-Partition (A, p, r)
 x ← A[p]
     i ← p − 1
     j ← r + 1
 while  TRUE
        repeat   j ←  j − 1
            until     A[j] ≤ x
    repeat   i ←  i + 1
            until     A[i] ≥ x
    if  i < j
              exchange  A[i] ↔ A[j]
    else  
              exchnage  A[r] ↔ A[i]  
              return   i

Oui, Ajoutez un échange d'Un[r] ↔ A[i] peut faire cela fonctionne.
Pourquoi?
Parce que A[i] est maintenant plus grand que Un[r] OU i == r.
Nous Nous devons donc d'échange afin de garantir la fonctionnalité d'une partition.

Tout d'abord u mal compris la Hoare partition de l'algorithme,qui peut être voir à partir de la traduction du code en c,
Depuis u considéré comme pivot le plus à gauche de l'élément de subarray.

Mal expliquer u compte tenu de la plus à gauche de l'élément de pivot.

int HoarePartition (int a[],int p, int r) 

Ici p et r représente la partie inférieure et la limite supérieure de la matrice qui peut être partie d'un ensemble plus grand aussi(subarray) être partitionné.

nous commençons donc avec les pointeurs(marqueur) au départ de pointage avant et après les points de fin de tableau(simplement bcoz à l'aide de boucle do while).Par conséquent,

i=p-1,

j=r+1;    //here u made mistake

Maintenant que par le partitionnement nous voulons que chaque élément à gauche du pivot être inférieure ou égale à pivot et plus grand que sur le côté droit de pivot.

Donc, nous allons aller de l' " je " marqueur jusqu'à ce que nous obtenir l'élément qui est greaterthan ou égale à pivot. Et, de même, 'j' marqueur jusqu'à ce que nous trouver l'élément inférieur ou égal à pivot.

Maintenant, si i < j on échange les éléments bcoz à la fois les éléments sont dans la mauvaise partie du tableau. Donc le code sera

do  j--; while (a[j] <= x);                 //look at inequality sign
do  i++; while (a[i] >= x);
if  (i < j) 
    swap(&a[i],&a[j]);

Maintenant, si " je " n'est pas inférieur à 'j',ce qui veut dire que il n'y a aucun élément dans entre de swap si nous revenons 'j' position.

Donc maintenant le tableau après avoir partitionné moitié inférieure est de "commencer à j'

moitié supérieure est à partir de j+1 à la fin"

donc le code ressemblera à

void QuickSort(int a[],int start,int end) {
    int q=HoarePartition(a,start,end);
    if (end<=start) return;
    QuickSort(a,start,q);
    QuickSort(a,q+1,end);
}