Quicksort: Choisir le pivot

Question

Lorsque vous implémentez Quicksort, vous devez notamment choisir un pivot. Mais lorsque je regarde un pseudo-code comme celui ci-dessous, on ne voit pas comment je devrais choisir le pivot. Premier élément de la liste? Quelque chose d'autre?

 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 pivot et à déterminer si des scénarios différents appellent des stratégies différentes?

Answer 1

Le choix d'un pivot aléatoire réduit les chances que vous rencontriez des performances O (n ² ) dans le cas le plus défavorable (le fait de choisir toujours le premier ou le dernier choix entraînerait des performances dans le pire des cas pour les tâches presque triées ou presque inversées. données triées). Le choix de l'élément central serait également acceptable dans la majorité des cas.

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

Answer 2

Cela dépend de vos besoins. Le choix aléatoire d'un pivot rend plus difficile la création d'un ensemble de données générant des performances O (N ^ 2). La «médiane de 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 de pivot) au hasard. Les enregistrements de base de données peuvent être coûteux à comparer.

Mise à jour: intégrer les commentaires dans la réponse.

mdkess a déclaré:

  

"Médiane de 3" n'est PAS le premier dernier milieu. Choisissez trois index aléatoires et prenez la valeur moyenne. L’essentiel est de vous assurer que votre choix de pivots n’est pas déterministe. Si tel est le cas, les données concernant le pire des cas peuvent être assez facilement générées.

À laquelle j'ai répondu:

• Analyse de l'algorithme de recherche de Hoare avec médian -Trois Partition (1997) par P Kirschenhofer, H Prodinger, C Mart & 237; Nez soutient votre affirmation (la "médiane de trois" est composée de trois éléments aléatoires).

• Un article décrit à l'adresse portail. .acm.org à propos de 'La permutation du pire cas pour la médiane de trois Quicksort' par Hannu Erki & # 246; publié dans The Computer Journal, Vol 27, No 3, 1984. [Mise à jour 2012-02 -26: Obtention du texte de l’article . La section 2 'L'algorithme' commence: ' En utilisant la médiane des premier, deuxième et dernier éléments de A [L: R], des partitions efficaces en parties de tailles sensiblement égales peuvent être obtenues dans la plupart des situations pratiques. 'Ainsi, il discute de la première, de la dernière et du dernier moyen de Mo3.]

• 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 & # 8211; 4 (0 1999). Il explique comment faire en sorte que presque chaque Quicksort se comporte de manière quadratique.

• Revue technique AT & T Bell Labs, octobre 1984 "Théorie et pratique de la construction d’une routine de tri active" Etats "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 du premier [...] [...] et du milieu ". Cela indique que les deux techniques de «médiane sur trois» sont connues dans la littérature. (Mise à jour du 26/11/2014: l'article semble être disponible à l'adresse IEEE Xplore ou à partir de Wiley & # 8212; si vous êtes membre ou êtes prêt à payer des frais.)

• 'Ingénierie d'une fonction de tri' de JL Bentley et MD McIlroy, publiés dans Software Practice and Experience, vol 23 (11), novembre 1993, entame une longue discussion des problèmes et choisit un algorithme de partitionnement adaptatif basé en partie sur la taille des données ensemble. Il y a beaucoup de discussions sur les compromis entre différentes approches.

• Une recherche Google sur "la médiane de trois" fonctionne plutôt bien pour un suivi ultérieur.

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

Answer 3

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’article au milieu de la gamme. (mieux sur une entrée partiellement triée)

Cependant, le choix d’un élément quelconque risque de mal partitionner le tableau de taille n en deux tableaux de taille 1 et n-1. Si vous le faites assez souvent, votre tri rapide risque de devenir O (n ^ 2).

Une amélioration que j'ai constatée est la médiane de sélection (premier, dernier, moyen); Dans le pire des cas, il peut toujours aller à O (n ^ 2), mais il s'agit probablement d'un cas rare.

Pour la plupart des données, choisir le premier ou le dernier est suffisant. Toutefois, si vous rencontrez souvent les pires scénarios (entrée partiellement triée), la première option consiste à choisir la valeur centrale (qui est un pivot statistique correct pour les données partiellement triées).

Si vous rencontrez toujours des problèmes, choisissez la route médiane.

Answer 4

Ne choisissez jamais un pivot fixe - il peut être attaqué pour exploiter la pire exécution de votre algorithme, O (n ^ 2), qui ne fait que poser problème. Le pire scénario 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 votre algorithme par un ordre décroissant, votre premier pivot sera le plus grand, de sorte que tout le reste du tableau se déplacera à gauche. Ensuite, lorsque vous récidiverez, le premier élément sera à nouveau le plus important. Une fois de plus, vous mettez tout à gauche, 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 ni le premier ni le dernier, mais aussi, selon 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 milieu (et donc , n lg n time).

Si vous voulez absolument garantir le temps d’exécution de O (nlgn) pour l’algorithme, la méthode colonnes-sur-5 permettant de trouver la médiane d’un tableau s’exécute en temps O (n), ce qui signifie que l’équation de récurrence de quicksort dans le pire des cas sera T (n) = O (n) (trouver la médiane) + O (n) (partition) + 2T (n / 2) (récidive gauche et droite.) Par le théorème principal, il s'agit de O (n lg n). Cependant, le facteur constant sera énorme, et si la pire des performances est votre principale préoccupation, utilisez plutôt un type de fusion, qui est un peu plus lent que le tri rapide en moyenne, et garantit un temps O (nlgn) (et sera beaucoup plus rapide que ce triplé médian).

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

Answer 5

N'essayez pas d'être trop intelligent et combinez des stratégies de pivotement. Si vous combinez la médiane de 3 avec un pivot aléatoire en choisissant la médiane de la première, de la dernière et un indice aléatoire au milieu, vous serez toujours vulnérable à de nombreuses distributions qui envoient une médiane de 3 quadratique (elle est donc pire que pivot aléatoire simple)

Par exemple, une distribution d'organes de tuyaux (1,2,3 ... N / 2..3,2,1) sera première et dernière sera 1 et l'indice aléatoire sera un nombre supérieur à 1, la médiane donnant 1 ( premier ou dernier) et vous obtenez un partitionnement extrêmement déséquilibré.

Answer 6

Tout dépend de la manière dont vos données sont triées. Si vous pensez que ce sera pseudo-aléatoire, votre meilleure option est de choisir une sélection aléatoire ou de choisir le milieu.

Answer 7

Si vous triez une collection accessible au hasard (comme un tableau), il est généralement préférable de choisir l'élément du milieu physique. Avec cela, si le tableau est tout prêt (ou presque), 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 chaînée), il est préférable de choisir le premier élément, car il est le plus rapide à accéder. Ici, cependant, si la liste est déjà triée, vous êtes foutu - une partition sera toujours nulle, et l’autre a tout, produisant le pire temps.

Cependant, pour une liste chaînée, choisir autre chose que la première ne fera qu'empirer les choses. Il choisit l'élément du milieu dans une liste, vous devrez l'exécuter à chaque étape de la partition - en ajoutant une opération O (N / 2) effectuée en consignant plusieurs fois le temps total O (1,5 N * log N). et c’est-à-dire si nous savons combien de temps la liste est longue avant de commencer - en général nous ne le faisons pas, nous devons donc parcourir tout le chemin pour les compter, puis faire un demi-chemin pour trouver le milieu, puis parcourir troisième fois pour faire la partition réelle: O (2.5N * log N)

Answer 8

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

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

Elle n’est que légèrement plus inefficace qu’une longue fonction, mais elle 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
  };
};

Answer 9

Idéalement, le pivot devrait être la valeur centrale de l’ensemble du tableau. Cela réduira les chances d'obtenir les meilleures performances.

Answer 10

La complexité du tri rapide varie considérablement en fonction de la sélection de la valeur de pivot. Par exemple, si vous choisissez toujours le premier élément comme pivot, la complexité de l'algorithme est aussi mauvaise que O (n ^ 2). Voici une méthode intelligente pour choisir un é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 inférieur aux autres, c'est-à-dire la médiane. 3. faire de cet élément un élément pivot.

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

Answer 11

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

Plus l’échantillonnage est élevé, meilleur est l’augmentation de n, mais l’amélioration ralentit considérablement à mesure que vous augmentez le nombre d’échantillons. Et vous induisez des frais généraux d'échantillonnage et de tri des échantillons.

Answer 12

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

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

Answer 13

Dans une implémentation vraiment optimisée, la méthode de choix de 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 procéder à une analyse complète, je suppose que "le milieu de O (log (n)) éléments" C’est un bon début, qui présente également l’avantage supplémentaire de ne pas nécessiter de mémoire supplémentaire: en utilisant l’appel de queue sur la partition plus grande et le partitionnement sur place, nous utilisons la même mémoire supplémentaire O (log (n)) à presque chaque étape de la configuration. l'algorithme.