Quicksort: choisir le pivot

Lors de la mise en œuvre de Quicksort, l'une des choses que vous devez faire est de choisir un pivot. Mais quand je regarde un pseudocode comme celui ci-dessous, je ne sais pas comment choisir le pivot. Premier élément de la liste? Autre chose?

 function quicksort(array)
     var list less, greater
     if length(array) ≤ 1  
         return array  
     select and remove a pivot value pivot from array
     for each x in array
         if x ≤ pivot then append x to less
         else append x to greater
     return concatenate(quicksort(less), pivot, quicksort(greater))

Quelqu'un peut-il m'aider à comprendre le concept de choix d'un pivot et si différents scénarios appellent ou non des stratégies différentes.

Le choix d'un pivot aléatoire minimise le risque que vous rencontriez les pires performances O (n ² ) (toujours choisir le premier ou le dernier entraînerait des performances pires pour les données presque triées ou triées presque inversement). Le choix de l'élément intermédiaire serait également acceptable dans la majorité des cas.

De plus, si vous implémentez cela vous-même, il existe des versions de l'algorithme qui fonctionnent en place (c'est-à-dire sans créer deux nouvelles listes puis les concaténer).

Cela dépend de vos besoins. Le choix d'un pivot au hasard rend plus difficile la création d'un ensemble de données qui génère des performances O (N ^ 2). La «médiane sur trois» (premier, dernier, milieu) est également un moyen d'éviter les problèmes. Méfiez-vous des performances relatives des comparaisons, cependant; si vos comparaisons sont coûteuses, Mo3 fait plus de comparaisons que de choisir (une seule valeur pivot) au hasard. Les enregistrements de base de données peuvent être coûteux à comparer.

Mise à jour: mise à jour des commentaires.

mdkess a affirmé:

«La médiane de 3» n'est PAS le premier dernier milieu. Choisissez trois index aléatoires et prenez la valeur moyenne de ceci. Le but est de vous assurer que votre choix de pivots n'est pas déterministe - si c'est le cas, les données du pire des cas peuvent être assez facilement générées.

À quoi j'ai répondu:

• Analyse de l'algorithme de recherche de Hoare avec la partition médiane de trois (1997) par P Kirschenhofer, H Prodinger, C Martínez soutient votre affirmation (que la «médiane de trois» correspond à trois éléments aléatoires).

• Il y a un article décrit sur portal.acm.org qui parle de «The Worst Case Permutation for Median-of-Three Quicksort» par Hannu Erkiö, publié dans The Computer Journal, Vol 27, No 3, 1984. [Mise à jour 2012-02- 26: Vous avez le texte de l' article . La section 2 «L'algorithme» commence: « En utilisant la médiane des premier, milieu et dernier éléments de A [L: R], des partitions efficaces en parties de tailles assez égales peuvent être réalisées dans la plupart des situations pratiques. «Ainsi, il discute de l'approche Mo3 premier-milieu-dernier.]

• Un autre court article intéressant est celui de MD McIlroy, "A Killer Adversary for Quicksort" , publié dans Software-Practice and Experience, Vol. 29 (0), 1–4 (0 1999). Il explique comment faire en sorte que presque tous les tri rapides se comportent de manière quadratique.

• AT&T Bell Labs Tech Journal, octobre 1984 "Théorie et pratique dans la construction d'une routine de tri de travail" déclare "Hoare a suggéré de partitionner autour de la médiane de plusieurs lignes choisies au hasard. Sedgewick [...] a recommandé de choisir la médiane de la première [. ..] dernier [...] et milieu ". Cela indique que les deux techniques de «médiane sur trois» sont connues dans la littérature. (Mise à jour 23/11/2014: l'article semble être disponible sur IEEE Xplore ou auprès de Wiley - si vous êtes membre ou êtes prêt à payer des frais.)

• `` Engineering a Sort Function '' de JL Bentley et MD McIlroy, publié dans Software Practice and Experience, Vol 23 (11), novembre 1993, entre dans une discussion approfondie sur les problèmes, et ils ont choisi un algorithme de partitionnement adaptatif basé en partie sur le taille de l'ensemble de données. Il y a beaucoup de discussions sur les compromis pour diverses approches.

• Une recherche Google sur «médiane sur trois» fonctionne plutôt bien pour un suivi plus poussé.

Merci pour l'information; Je n'avais rencontré que la «médiane de trois» déterministe auparavant.

Hé, je viens d'enseigner ce cours.

Il existe plusieurs options.
Simple: choisissez le premier ou le dernier élément de la plage. (mauvais sur une entrée partiellement triée) Mieux: choisissez l'élément au milieu de la plage. (mieux sur une entrée partiellement triée)

Cependant, choisir n'importe quel élément arbitraire risque de mal partitionner le tableau de taille n en deux tableaux de taille 1 et n-1. Si vous faites cela assez souvent, votre tri rapide risque de devenir O (n ^ 2).

Une amélioration que j'ai constatée est le choix de la médiane (premier, dernier, milieu); Dans le pire des cas, il peut toujours aller à O (n ^ 2), mais de manière probabiliste, c'est un cas rare.

Pour la plupart des données, choisir le premier ou le dernier est suffisant. Mais, si vous constatez que vous rencontrez souvent les pires scénarios (entrée partiellement triée), la première option serait de choisir la valeur centrale (ce qui est un bon pivot statistiquement pour les données partiellement triées).

Si vous rencontrez toujours des problèmes, suivez la voie médiane.

Ne choisissez jamais un pivot fixe - cela peut être attaqué pour exploiter le pire des cas d'exécution O (n ^ 2) de votre algorithme, ce qui ne demande que des problèmes. Le pire des cas d'exécution de Quicksort se produit lorsque le partitionnement donne un tableau de 1 élément et un tableau de n-1 éléments. Supposons que vous choisissiez le premier élément comme partition. Si quelqu'un alimente un tableau dans votre algorithme dans un ordre décroissant, votre premier pivot sera le plus grand, donc tout le reste du tableau se déplacera vers sa gauche. Ensuite, lorsque vous répétez, le premier élément sera à nouveau le plus grand, donc une fois de plus, vous mettez tout à gauche, et ainsi de suite.

Une meilleure technique est la méthode de la médiane sur 3, dans laquelle vous choisissez trois éléments au hasard et choisissez le milieu. Vous savez que l'élément que vous choisirez ne sera ni le premier ni le dernier, mais aussi, par le théorème de la limite centrale, la distribution de l'élément du milieu sera normale, ce qui signifie que vous allez tendre vers le milieu (et donc , n lg n fois).

Si vous voulez absolument garantir l'exécution O (nlgn) pour l'algorithme, la méthode des colonnes de 5 pour trouver la médiane d'un tableau s'exécute en temps O (n), ce qui signifie que l'équation de récurrence pour le tri rapide dans le pire des cas sera be T (n) = O (n) (trouver la médiane) + O (n) (partition) + 2T (n / 2) (récurer à gauche et à droite.) Par le théorème maître, c'est O (n lg n) . Cependant, le facteur constant sera énorme, et si le pire des cas est votre principale préoccupation, utilisez plutôt un tri par fusion, qui n'est qu'un peu plus lent que le tri rapide en moyenne, et garantit le temps O (nlgn) (et sera beaucoup plus rapide que ce tri rapide médian boiteux).

Explication de l'algorithme de la médiane des médianes

N'essayez pas d'être trop intelligent et combinez des stratégies pivotantes. Si vous combinez la médiane de 3 avec un pivot aléatoire en choisissant la médiane du premier, du dernier et d'un index aléatoire au milieu, vous serez toujours vulnérable à de nombreuses distributions qui envoient une médiane de 3 quadratiques (donc c'est en fait pire que pivot aléatoire simple)

Par exemple, une distribution d'orgue à tuyaux (1,2,3 ... N / 2..3,2,1) premier et dernier sera à la fois 1 et l'indice aléatoire sera un nombre supérieur à 1, en prenant la médiane donne 1 ( premier ou dernier) et vous obtenez un partitionnement extrêmement déséquilibré.

Il est plus facile de diviser le tri rapide en trois sections.

1. Fonction d'échange ou d'échange d'élément de données
2. La fonction de partition
3. Traitement des partitions

Ce n'est que légèrement plus inefficace qu'une seule fonction longue mais est beaucoup plus facile à comprendre.

Le code suit:

/* This selects what the data type in the array to be sorted is */

#define DATATYPE long

/* This is the swap function .. your job is to swap data in x & y .. how depends on
data type .. the example works for normal numerical data types .. like long I chose
above */

void swap (DATATYPE *x, DATATYPE *y){  
  DATATYPE Temp;

  Temp = *x;        // Hold current x value
  *x = *y;          // Transfer y to x
  *y = Temp;        // Set y to the held old x value
};


/* This is the partition code */

int partition (DATATYPE list[], int l, int h){

  int i;
  int p;          // pivot element index
  int firsthigh;  // divider position for pivot element

  // Random pivot example shown for median   p = (l+h)/2 would be used
  p = l + (short)(rand() % (int)(h - l + 1)); // Random partition point

  swap(&list[p], &list[h]);                   // Swap the values
  firsthigh = l;                                  // Hold first high value
  for (i = l; i < h; i++)
    if(list[i] < list[h]) {                 // Value at i is less than h
      swap(&list[i], &list[firsthigh]);   // So swap the value
      firsthigh++;                        // Incement first high
    }
  swap(&list[h], &list[firsthigh]);           // Swap h and first high values
  return(firsthigh);                          // Return first high
};



/* Finally the body sort */

void quicksort(DATATYPE list[], int l, int h){

  int p;                                      // index of partition 
  if ((h - l) > 0) {
    p = partition(list, l, h);              // Partition list 
    quicksort(list, l, p - 1);        // Sort lower partion
    quicksort(list, p + 1, h);              // Sort upper partition
  };
};

Cela dépend entièrement de la façon dont vos données sont triées au départ. Si vous pensez que ce sera pseudo-aléatoire, votre meilleur pari est de choisir une sélection aléatoire ou de choisir le milieu.

Si vous triez une collection accessible au hasard (comme un tableau), il est généralement préférable de choisir l'élément physique du milieu. Avec cela, si le tableau est tout prêt trié (ou presque trié), les deux partitions seront presque égales et vous obtiendrez la meilleure vitesse.

Si vous triez quelque chose avec uniquement un accès linéaire (comme une liste liée), il est préférable de choisir le premier élément, car c'est l'élément le plus rapide auquel accéder. Ici, cependant, si la liste est déjà triée, vous êtes foutu - une partition sera toujours nulle, et l'autre aura tout, produisant le pire moment.

Cependant, pour une liste chaînée, choisir autre chose que le premier ne fera qu'empirer les choses. Il choisit l'élément du milieu dans une liste, vous devrez le parcourir à chaque étape de la partition - en ajoutant une opération O (N / 2) qui est effectuée logN fois pour un temps total O (1,5 N * log N) et c'est si nous savons combien de temps dure la liste avant de commencer - généralement nous ne le faisons pas, nous devrons donc faire un pas en avant pour les compter, puis passer à mi-chemin pour trouver le milieu, puis parcourir un troisième fois pour faire la partition réelle: O (2,5 N * log N)

Idéalement, le pivot doit être la valeur du milieu dans l'ensemble du tableau. Cela réduira les chances d'obtenir les pires performances.

La complexité du tri rapide varie considérablement avec la sélection de la valeur du pivot. par exemple, si vous choisissez toujours le premier élément comme pivot, la complexité de l'algorithme devient aussi pire que O (n ^ 2). voici une méthode intelligente pour choisir l'élément pivot: 1. choisissez le premier, le milieu, le dernier élément du tableau. 2. Comparez ces trois nombres et trouvez le nombre qui est supérieur à un et plus petit que l'autre, c'est-à-dire la médiane. 3. faites de cet élément un élément pivot.

le choix du pivot par cette méthode divise le tableau en près de deux et donc la complexité se réduit à O (nlog (n)).

En moyenne, la médiane de 3 est bonne pour un petit n. La médiane de 5 est un peu meilleure pour un n plus grand. Le ninther, qui est la «médiane de trois médianes sur trois», est encore meilleur pour les n très grands.

Plus vous allez avec l'échantillonnage, meilleur vous obtenez à mesure que n augmente, mais l'amélioration ralentit considérablement à mesure que vous augmentez les échantillons. Et vous engagez les frais généraux d'échantillonnage et de tri des échantillons.

Je recommande d'utiliser l'index du milieu, car il peut être calculé facilement.

Vous pouvez le calculer en arrondissant (array.length / 2).

Dans une implémentation vraiment optimisée, la méthode de choix du pivot doit dépendre de la taille du tableau - pour un grand tableau, il est avantageux de passer plus de temps à choisir un bon pivot. Sans faire une analyse complète, je suppose que "le milieu des éléments O (log (n))" est un bon début, et cela a l'avantage supplémentaire de ne pas nécessiter de mémoire supplémentaire: en utilisant un appel de queue sur la plus grande partition et en place le partitionnement, nous utilisons la même mémoire supplémentaire O (log (n)) à presque toutes les étapes de l'algorithme.