Quicksort: choisir le pivot

cela dépend de vos besoins. Choisir un pivot au hasard rend plus difficile de créer un ensemble de données qui génère des performances O(N^2). La "médiane de trois" (première, dernière, moyenne) est également un moyen d'éviter les problèmes. Méfiez-vous de la performance relative des comparaisons, cependant; si vos comparaisons sont coûteuses, alors Mo3 fait plus de comparaisons que de choisir (une seule valeur de pivot) au hasard. Il peut être coûteux de comparer les enregistrements de la base de données.

mise à Jour: Tirer des commentaires dans la réponse.

mdkess , a affirmé:

"Médian de 3' n'est PAS le prénom du milieu. Choisissez trois indices aléatoires, et prenez la valeur moyenne de ceci. L'essentiel est de s'assurer que votre choix de pivots n'est pas déterministe - si c'est le cas, les données du pire cas peuvent être assez facilement générées.

à laquelle j'ai répondu:

• Analyse De Hoare de Trouver l'Algorithme Avec une Médiane De Trois Partition (1997) par P Kirschenhofer, H Prodinger, C Martínez soutient votre affirmation (que la "médiane de trois" est constituée de trois éléments aléatoires).

• il y a un article décrit à portal.acm.org , c'est-à-dire "The Worst Case Permutation for Median-of-Three Quicksort" de Hannu Erkiö, publié dans The Computer Journal, Vol 27, no 3, 1984. [Mise à jour 2012-02-26: vous avez le texte de la article . Section 2 'L'algorithme' commence: ' en utilisant la médiane du premier, du milieu et du dernier élément d'un[L:R], on peut obtenir des partitions efficaces dans des parties de tailles assez égales dans la plupart des situations pratiques. ' ainsi, il est question de la première-middle-last approche Mo3.]

• un autre court article intéressant est de M. D. McIlroy, "Un Tueur Adversaire pour le Quicksort" , publié dans le Logiciel-la Pratique et l'Expérience, Vol. 29(0), 1-4 (0 1999). Il explique comment faire presque n'importe quel Quicksort se comporter quadratiquement.

• AT&T Bell Labs Tech Journal, Oct 1984" Theory and Practice in the Construction of a Working Sort Routine "states" Hoare suggested partitioning around the median of several randomly selected lines. Sedgewick [...] recommandé de choisir le médiane de la première [...] Dernière.[ ..] et du milieu". Cela indique que les deux techniques 'médiane de trois" sont connus dans la littérature. (Mise à jour 2014-11-23: l'article semble être disponible à IEEE Xplore ou de Wiley - si vous avez l'adhésion ou êtes prêt à payer des frais.)

• ' par J L Bentley et M D McIlroy, publié dans Software Practice and Experience, vol. 23(11), novembre 1993, fait l'objet d'une discussion approfondie sur les enjeux, et ils ont choisi un algorithme de partitionnement adaptatif fondé en partie sur la taille de l'ensemble de données. Il y a beaucoup de discussions sur les compromis pour diverses approches.

• une recherche sur Google pour 'median-of-three' fonctionne assez bien pour un suivi plus poussé.

Merci pour l'information; je n'avais rencontré la "médiane de trois" déterministe avant.

Heh, je viens d'enseigner cette classe.

il y a plusieurs options.

Simple: Choisissez le premier ou le dernier élément de la gamme. (mauvais sur les entrées partiellement triées) Mieux: choisissez l'article au milieu de la gamme. (amélioration sur les entrées partiellement triées)

cependant, choisir n'importe quel élément arbitraire risque de mal diviser le tableau de la taille n en deux tableaux de la taille 1 et n-1. Si vous le faites assez souvent, votre quicksort court le risque de devenir O(n^2).

une amélioration que j'ai vu est de choisir la médiane(premier, dernier, mid); Dans le pire des cas, elle peut encore aller à O(N^2), mais probablement, c'est un cas rare.

pour la plupart des données, choisir la première ou la dernière est suffisant. Mais, si vous constatez que vous êtes souvent dans le pire des scénarios (entrées partiellement triées), la première option serait de choisir la valeur centrale( qui est un pivot statistiquement bon pour les données triées).

si vous rencontrez toujours des problèmes, suivez la route médiane.

Ne jamais jamais choisir un pivot fixe - cela peut être attaqué pour exploiter le pire cas de votre algorithme O(N^2) runtime, qui demande juste des problèmes. Le pire des scénarios d'exécution de Quicksort se produit lorsque le partitionnement produit un tableau d'éléments 1 et un tableau d'éléments n-1. Supposons que vous choisissiez le premier élément comme partition. Si quelqu'un alimente un tableau à votre algorithme qui est en ordre décroissant, votre premier pivot sera le plus grand, donc tout le reste dans le tableau se déplacera vers le gauche de celui-ci. Ensuite, lorsque vous revenez, le premier élément sera à nouveau le plus grand, donc une fois de plus vous mettez tout à gauche de lui, et ainsi de suite.

une meilleure technique est la méthode de la médiane de 3, où vous choisissez trois éléments au hasard, et choisissez le milieu. Vous savez que l'élément que vous choisissez ne sera pas le premier ou le dernier, mais aussi, par le théorème de la limite centrale, la distribution de l'élément central sera normale, ce qui signifie que vous tendrez vers le moyen (et donc, n lg N temps).

si vous voulez absolument garantir O(nlgn) runtime pour l'algorithme, la méthode colonnes-of-5 pour trouver la médiane d'un tableau s'exécute en O(n) temps, ce qui signifie que l'équation de récurrence pour quicksort dans le pire des cas sera T(n) = O(N) (trouver la médiane) + O(n) (partition) + 2T(n/2) (recurse gauche et droite.) Par le Maître Théorème, c'est O(n lg n). Cependant, le facteur constant sera énorme, et si la pire performance est votre préoccupation principale, utilisez une sorte de fusion à la place, qui est seulement un peu plus lent que quicksort en moyenne, et garantit O(nlgn) le temps (et sera beaucoup plus rapide que cette médiane boiteuse quicksort).

explication de la médiane de L'algorithme de Medians

N'essayez pas d'être trop intelligent et de combiner des stratégies pivotantes. Si vous avez combiné la médiane de 3 avec pivot aléatoire en choisissant la médiane du premier, dernier et un index aléatoire dans le milieu, alors vous serez encore vulnérable à beaucoup des distributions qui envoient la médiane de 3 quadratiques (donc son en fait pire que simple pivot aléatoire)

Distribution d'organes tubulaires (1,2,3...N / 2..3,2,1) le premier et le dernier seront tous les deux 1 et l'indice aléatoire sera un nombre supérieur plus 1, en prenant la médiane donne 1 (soit Premier ou dernier) et vous obtenez un partitionnement extermely déséquilibré.

Il dépend entièrement de la façon dont vos données sont triées pour commencer. Si vous pensez qu'il va être pseudo-aléatoire, alors votre meilleur pari est de choisir une sélection aléatoire ou 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és (ou presque trié), les deux partitions seront près de même, et vous obtiendrez la meilleure vitesse.

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

Cependant, pour une liste liée, choisir autre chose que la première, ne fera qu'empirer les choses. Il choisit l'élément du milieu dans une liste listée, vous devez passer à travers elle sur chaque étape de partition -- ajoutant une opération O(N/2) qui est fait logN temps faisant le temps total O (1,5 n * log n) et c'est si nous savons combien de temps la liste est avant de commencer -- Habituellement nous il ne faut donc pas faire un pas à travers pour les Compter, puis un pas à mi-chemin pour trouver le milieu, puis un pas à travers une troisième fois pour faire la partition actuelle: O (2.5 N * log n)

il est plus facile de briser le quicksort en trois sections faisant ceci

1. Échange de données de l'élément de la fonction
2. la fonction de partition
3. traitement des partitions

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

Code:

/* 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
  };
};

idéalement, le pivot devrait être la valeur moyenne dans l'ensemble du tableau. Cela réduira les chances d'obtenir la pire performance.

la complexité de Quick sort varie considérablement avec le choix de la valeur de pivot. par exemple, si vous choisissez toujours le premier élément comme pivot, la complexité de l'algorithme devient aussi mauvaise que O(N^2). voici une méthode intelligente pour choisir l'élément pivot- 1. choisissez la première, mi, 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.-à-d. médian. 3. faites de cet élément un élément pivot.

choisir le pivot par cette méthode, le tableau est divisé en deux moitiés et donc la complexité réduit à O(nlog (n)).

on the average, Median of 3 is good for small N. Médiane de 5 est un peu mieux pour plus grand N. Le ninther, qui est la "médiane de trois médianes de trois" est encore mieux pour très grand N.

plus vous allez avec l'échantillonnage plus vous obtenez que n augmente, mais l'amélioration ralentit considérablement que vous augmentez les échantillons. Et vous avez la charge de l'échantillonnage et du tri des échantillons.

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

vous pouvez le calculer en arrondissant (tableau.longueur / 2).

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