Quicksort : Choisir le pivot

Question

Lors de la mise en œuvre de Quicksort, l'une des choses à faire est de choisir un pivot. Mais lorsque je regarde un pseudo-code comme celui ci-dessous, la façon dont je dois choisir le pivot n'est pas claire. Le 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 choix d'un pivot et à savoir si différents scénarios appellent ou non des stratégies différentes.

Answer 1

Le choix d'un pivot aléatoire minimise les chances de rencontrer dans le pire des cas O(n 2 ) (le fait de toujours choisir le premier ou le dernier entraînerait les pires performances pour les données presque triées ou presque triées en sens inverse). Le choix de l'élément du milieu serait également acceptable dans la majorité des cas.

En outre, si vous mettez en œuvre cet algorithme vous-même, il existe des versions de cet algorithme qui fonctionnent sur place (c'est-à-dire sans créer deux nouvelles listes et les concaténer).

Answer 2

Cela dépend de vos besoins. En choisissant un pivot au hasard, il est plus difficile de créer un ensemble de données qui génère des performances O(N^2). La "médiane de trois" (premier, dernier, milieu) est également un moyen d'éviter les problèmes. Attention à la performance relative des comparaisons, cependant ; si vos comparaisons sont coûteuses, alors Mo3 fait plus de comparaisons que de choisir (une seule valeur pivot) au hasard. Les enregistrements de bases de données peuvent être coûteux à comparer.

---

Mise à jour : mise en place des commentaires dans la réponse.

mdkess a affirmé :

La "médiane de 3" n'est PAS la première, la dernière et la moyenne. Choisissez trois indices au hasard, et prenez la valeur médiane de ceux-ci. Le but est de s'assurer que votre choix de pivots n'est pas déterministe - s'il l'est, les pires données peuvent être générées assez facilement.

Ce à quoi j'ai répondu :

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

• Il y a un article décrit à portail.acm.org qui concerne "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 : J'ai obtenu le texte pour le article . La section 2, intitulée "L'algorithme", commence ainsi : " En utilisant la médiane des premiers, moyens et derniers éléments de A[L:R], des partitions efficaces en parties de tailles relativement égales peuvent être réalisées dans la plupart des situations pratiques. Ainsi, il discute de l'approche première-moyenne-dernière Mo3].

• Un autre court article intéressant est celui de M. D. McIlroy, "Un adversaire mortel pour Quicksort" publié dans Software-Practice and Experience, Vol. 29(0), 1-4 (0 1999). Il explique comment faire en sorte que presque tout Quicksort se comporte de manière quadratique.

• AT&T Bell Labs Tech Journal, Oct 1984 "Theory and Practice in the Construction of a Working Sort Routine" déclare "Hoare a suggéré de partitionner autour de la médiane de plusieurs lignes sélectionnées au hasard. Sedgewick [...] recommandait de choisir la médiane de la première [...], de la dernière [...] et du milieu". Cela indique que les deux techniques de " médiane de trois " sont connues dans la littérature. (Mise à jour 2014-11-23 : L'article semble être disponible à l'adresse suivante IEEE Xplore ou de Wiley - si vous êtes membre ou prêt à payer une cotisation).

• Ingénierie d'une fonction de tri de J L Bentley et M D McIlroy, publié dans Software Practice and Experience, Vol 23(11), novembre 1993, examine en détail ces questions et choisit un algorithme de partitionnement adaptatif basé en partie sur la taille de l'ensemble de données. Il y a beaucoup de discussions sur les compromis pour les différentes approches.

• Une recherche Google pour "médiane de trois" fonctionne très bien pour un suivi plus approfondi.

Merci pour ces informations ; je n'avais rencontré que la "médiane de trois" déterministe auparavant.

Answer 3

Heh, je viens d'enseigner cette classe.

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. (meilleur sur une entrée partiellement triée)

Cependant, en choisissant n'importe quel élément arbitraire, on 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 quicksort risque de devenir O(n^2).

Une amélioration que j'ai constatée consiste à choisir la médiane (première, dernière, moyenne) ; Dans le pire des cas, cela peut toujours aller jusqu'à O(n^2), mais d'un point de vue probabiliste, c'est un cas rare.

Pour la plupart des données, il suffit de choisir la première ou la dernière. Mais si vous trouvez que vous rencontrez souvent les pires scénarios (données partiellement triées), la première option serait de choisir la valeur centrale (qui est un pivot statistiquement bon pour les données partiellement triées).

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

Answer 4

Ne choisissez jamais un pivot fixe - il peut être attaqué pour exploiter le pire cas O(n) de votre algorithme. 2 ), ce qui ne fait qu'attirer les ennuis. Le pire temps 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 fournit à votre algorithme un tableau qui est dans l'ordre décroissant, votre premier pivot sera le plus grand, donc tout le reste du tableau se déplacera à sa gauche. Puis, lors de la récurrence, le premier élément sera à nouveau le plus grand, de sorte qu'une fois de plus, vous placerez tout à sa gauche, et ainsi de suite.

Une meilleure technique est le méthode de la médiane de 3 où vous prenez 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, par le théorème de la limite centrale, que la distribution de l'élément du milieu sera normale, ce qui signifie que vous aurez tendance à vous diriger vers le milieu (et donc vers un temps nlog(n)).

Si vous voulez absolument garantir un temps d'exécution de l'algorithme de O(nlog(n)), l'option 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 quicksort dans le pire des cas sera :

T(n) = O(n) (find the median) + O(n) (partition) + 2T(n/2) (recurse left and right)

Par le théorème du maître, c'est O(nlog(n)). Cependant, le facteur constant sera énorme, et si la performance dans le pire des cas est votre principale préoccupation, utilisez un tri par fusion à la place, qui est seulement un peu plus lent que le quicksort en moyenne, et garantit un temps O(nlog(n)) (et sera beaucoup plus rapide que ce quicksort médian boiteux).

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

Answer 5

N'essayez pas d'être trop malin et de combiner les 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 d'un indice aléatoire au milieu, vous serez toujours vulnérable à de nombreuses distributions qui rendent la médiane de 3 quadratique (donc pire que le pivot aléatoire).

Par exemple, une distribution d'orgue de Barbarie (1,2,3...N/2..3,2,1), le premier et le dernier seront tous deux égaux à 1 et l'indice aléatoire sera un nombre supérieur à 1. En prenant la médiane, on obtient 1 (soit le premier, soit le dernier) et on obtient un partitionnement extrêmement déséquilibré.