Pourquoi ce Quicksort fonctionne-t-il?

Question

Je trouve cette approche de partitionnement Quicksort confuse et erronée, mais elle semble fonctionner. Je fais référence à this pseudocode. Note: ils ont aussi une implémentation C à la fin de l'article, mais c'est très différent de leur pseudo-code, donc ça m'est égal.

J'ai aussi écrit en C comme celui-ci, en essayant de rester fidèle à la pseudocode autant que possible, même si cela signifie faire des choses C bizarre:

#include <stdio.h> 

int partition(int a[], int p, int r) 
{ 
    int x = a[p]; 

    int i = p - 1; 
    int j = r + 1; 

    while (1) 
    { 
     do 
      j = j - 1; 
     while (!(a[j] <= x)); 

     do 
      i = i + 1; 
     while (!(a[i] >= x)); 

     if (i < j) 
     { 
      int t = a[i]; 
      a[i] = a[j]; 
      a[j] = t; 
     } 
     else 
     { 
      for (i = 1; i <= a[0]; ++i) 
       printf("%d ", a[i]); 
      printf("- %d\n", j); 

      return j; 
     } 
    } 
} 


int main() 
{ 
    int a[100] = //{8, 6,10,13,15,8,3,2,12}; 
       {7, 7, 6, 2, 3, 8, 4, 1}; 

    partition(a, 1, a[0]); 
    return 0; 
} 

Si vous exécutez, vous » ll obtenir la sortie suivante:

1 6 2 3 4 8 7 - 5

Cependant, cela est faux, non? Clairement, a[5] n'a pas toutes les valeurs avant qu'il ne soit plus bas que lui, puisque a[2] = 6 > a[5] = 4. Sans compter que 7 est censé être le pivot (le a[p] initial) et pourtant sa position est à la fois incorrecte et perdue.

L'algorithme de partition suivant est extrait de wikipedia:

int partition2(int a[], int p, int r) 
{ 
    int x = a[r]; 
    int store = p; 

    for (int i = p; i < r; ++i) 
    { 
     if (a[i] <= x) 
     { 
      int t = a[i]; 
      a[i] = a[store]; 
      a[store] = t; 

      ++store; 
     } 
    } 

    int t = a[r]; 
    a[r] = a[store]; 
    a[store] = t; 

    for (int i = 1; i <= a[0]; ++i) 
     printf("%d ", a[i]); 
    printf("- %d\n", store); 

    return store; 
} 

et produit cette sortie:

1 6 2 3 8 4 7 - 1

qui est un bon résultat dans mon avis: le pivot (a[r] = a[7]) a atteint sa position finale.

Cependant, si j'utilise la fonction de partitionnement initial dans l'algorithme suivant:

void Quicksort(int a[], int p, int r) 
{ 
    if (p < r) 
    { 
     int q = partition(a, p, r); // initial partitioning function 

     Quicksort(a, p, q); 
     Quicksort(a, q + 1, r); // I'm pretty sure q + r was a typo, it doesn't work with q + r. 
    } 
} 

... il semble être un algorithme de tri correct. J'ai testé sur beaucoup d'entrées aléatoires, y compris tous les tableaux 0-1 de longueur 20.

J'ai également essayé d'utiliser cette fonction de partition pour un algorithme de sélection, dans lequel il n'a pas réussi à produire des résultats corrects. Cela semble fonctionner et c'est même très rapide dans le cadre de l'algorithme quicksort.

Mes questions sont les suivantes:

1. Quelqu'un peut-il afficher un exemple sur lequel l'algorithme ne fonctionne pas?
2. Si non, pourquoi cela fonctionne-t-il, puisque la partition semble être incorrecte? Est-ce une autre approche de partitionnement que je ne connais pas?

Answer 1

Je pense que le partitionnement est correct. 7 est le pivot. Le tableau original est partitionné en un sous-tableau de longueur 5 contenant des éléments inférieurs ou égaux à 7 et un sous-tableau de longueur 2, contenant des éléments supérieurs ou égaux à 7.

Answer 2

De Wikipedia (je l'ai souligné la partie que je pense adresse directement à votre question):

Ceci est l'algorithme de partition en place. Elle divise la partie de la matrice entre les index gauche et droite , inclusivement, en déplaçant tous les éléments inférieure ou égale à matrice [pivotIndex] au début de la sous-matrice , en laissant tous les éléments plus grands les suivants. Dans le processus , il trouve également la position finale pour l'élément de pivot, ce qui renvoie . Il déplace temporairement l'élément de pivot à la fin du sous-jeu , de sorte qu'il n'obtient pas le chemin. Parce qu'il n'utilise que des échanges , la liste finale a les mêmes éléments que la liste d'origine. Notez qu'un élément peut être échangé plusieurs fois avant d'atteindre son lieu final. Il convient également de noter que dans le cas de duplication de pivot dans le tableau d'entrée, ils peuvent être répartis à travers la sous-matrice gauche, éventuellement dans ordre aléatoire. Cela ne représente pas un échec de partitionnement , car un tri plus poussé va se repositionner et finalement les "coller" ensemble.

Pourriez-vous être ce que vous manquiez?

Answer 3

Vous se confondre entre l'index de l'élément et la valeur Iten

Regardez votre tête

int partition(int a[], int p, int r) ; 

Maintenant, si nous avons changé le type de données sur le tableau a vous tapez des données étranges verra le problème

int partition(Otherdatatype a[], int p, int r) ; 

Vous appelez la fonction à partir de votre principale avec

partition(a, 1, a[0]); 

Voir le problème a [0] est la valeur de l'entrée dans un [0] pas une valeur d'index. Imaginez un [0] ayant la valeur 200 dans votre code changez simplement la valeur du premier élément à 200 et vous obtiendrez une erreur d'exécution "tentative d'accès à la mémoire hors de portée" car si vous suivez à travers [0] = 200 qui est passé dans la partition en tant que valeur r, puis suivez ce qui se passe à l'intérieur de la partition. La chose à retenir est qu'il s'agit d'une routine de tri dans votre en-tête de partition. La liste dans le tableau a peut ne pas être du même type que les index. P et r de votre en-tête sont clairement indexés sur une position d'index a est la liste à trier.

Ainsi votre départ principal une sorte est

partition(a, 0, items_in_array-1); 

Voyez-vous pourquoi? Array a fonctionne depuis un [0] ...un [items_in_array-1]

Donc, dans votre exemple ci-dessus, vous avez préchargé 8 valeurs dans votre tableau de sorte que votre appel partition de la principale devrait être

partition(a, 0, 7); 

Answer 4

L'extension par le haut, voici ce qu'il devrait ressembler

void swap(int *a, int *b) 
{ 
    int x; 

    x = *a; 
    *a = *b; 
    *b = x; 
} 

int partition(int s[], int l, int h) 
{ 
    int i; 
    int p;/* pivot element index */ 
    int firsthigh;/* divider position for pivot element */ 

    p = h; 
    firsthigh = l; 
    for (i = l; i < h; i++) 
     if(s[i] < s[p]) { 
      swap(&s[i], &s[firsthigh]); 
      firsthigh++; 
     } 
    swap(&s[p], &s[firsthigh]); 

    return(firsthigh); 
} 

void quicksort(int s[], int l, int h) 
{ 
    int p;/* index of partition */ 
    if ((h - l) > 0) { 
     p = partition(s, l, h); 
     quicksort(s, l, p - 1); 
     quicksort(s, p + 1, h); 
    } 
} 

int main()  
{   
    int a[100] = //{8, 6,10,13,15,8,3,2,12}; 
        {7, 7, 6, 2, 3, 8, 4, 1};    
    quicksort(a, 0, 7); 
    return 0; 
}