D'où la randomisation dans Randomized Quicksort

Question

Cormen parle brièvement des avantages de choisir un pivot aléatoire dans quicksort. Cependant, comme indiqué (4 au dernier paragraphe):

L'utilisation d'un générateur de nombres aléatoires pour choisir les positions est relativement cher

Alors, comment est le choix d'un pivot aléatoire effectivement mis en œuvre dans la pratique, et comment est-il au hasard? Il ne peut pas être trop cher, puisque d'après ce que je comprends l'un des principaux avantages de tri rapide par rapport aux autres $ \ cal {O} (n \ logn) $ sortes sont les petits facteurs constants, et les dépenses allot des cycles de cueillette pivots saperait que avantage.

EDIT

À titre d'exemple, le code C de " Trois ravissantes Quicksorts " appelle en fait la fonction bibliothèque C de rand:

int randint(int l, int u) {
    return rand()%(u-l+1)+l;
}

void quicksort(int l, int u) {
    int i, m;
    if (l >= u) return;
    swap(l, randint(l, u));
    m = l;
    for (i = l+1; i <= u; i++)
        if (x[i] < x[l])
            swap(++m, i);
    swap(l, m);
    quicksort(l, m-1);
    quicksort(m+1, u);
}

Alors que le pivot picking code ici est clairement $ \ cal {O} (1) $, il semblerait que l'ici caché $ c $ est relativement élevé.

Answer 1

Jetez un oeil à McIllroy et Douglas' "Un tueur pour Adversaire Quicksort" (logiciel - Pratique et expérience 29 (4): 341-344 (1999)) ou de Crosby et Wallach "déni de service via la complexité des attaques" algorithmique pour le < em> raison derrière randomiser. QuickSort se comporte très mal si vous choisissez (presque) le plus grand / plus petit comme pivot à chaque fois. Pour randomisation au sens de faire, il doit être au hasard (si je sais comment vous choisissez pivots déterministe , je peux concocter un tableau qui vous oblige à aller dans O $ ( n ^ 2) $ comportement, voir le document mentionné pour plus de détails). Mais une fantaisie RNG est plus coûteux que, par exemple, en 3 ou un autre nombre impair d'éléments assez petit, et choisir la médiane de ceux comme pivot, ce qui est une autre façon de lutter contre le mauvais comportement. Donc, si vous choisissez la randomisation, utilisez un rapide RNG tête de série appropiately (probablement un linéaire congruence système sera suffisant).

Les algorithmes peuvent (et doivent) être comparé par $ O (\ cdot) $, mais si vous parlez de différentes implémentations du même algorithme doit passer à une analyse plus détaillée. En fait, Sedgewick et Flajolet « Une introduction à l'analyse des algorithmes » font valoir que l'un shouldn « t utilisation $ T (n) = O (f (n)) $ du tout, mais devrait s'efforcer d'obtenir T $ (n) \ sim f (n) $ asymptotiques de type.

Answer 2

Alors après avoir pris le temps de vous asseoir et regarder en fait la conférence de Google Bentley, Trois belles Quicksorts , il se trouve que son pivot aléatoire ne sont pas plus vite que d'autres méthodes. Plus précisément, selon Bently - qui, avec McIlroy - la récrit bibliothèque standard C fonction qsort , nous avons les éléments suivants de leur papier, Ingénierie d'une fonction de tri :

• 1,386 $ \; \ cdot n \ lg n $ comparaisons moyenne à l'aide de premier, au milieu ou à un pivot randomisé
• 1,188 $ \; \ cdot n \ lg n $ comparaisons moyenne au moyen d'un pivot médian de 3
• 1,094 $ \; \ cdot n \ lg n $ comparaisons moyenne en utilisant une moyenne de 3 médianes pivot

Selon le document ci-dessus:

Notre code final choisit donc l'élément central des réseaux plus petits, la médiane des premiers, moyen et dernier éléments d'une taille moyenne tableau, et le pseudo-médian de neuf éléments régulièrement espacés d'un grand matrice.

Je lis ce qui suit dans Structures de données utilisant C , par Tenenbaum, Langsam et Augenstein :

Il est possible d'accélérer le tri rapide pour les fichiers triés en choisissant un aléatoire élément de chaque sous-fichier en tant que valeur de pivotement. Si un fichier est connu pour être presque triés, cela pourrait être une bonne stratégie (bien que, dans ce cas, le choix de l'élément central comme pivot serait encore meilleur ). Cependant, si on ne sait rien sur le fichier, un tel stratégie ne s'améliore pas le pire comportement de cas , car il est possible (bien improbable) que l'élément aléatoire choisi par le temps pourrait toujours être le plus petit élément de chaque sous-fichier. Comme un pratique, les fichiers classés sont plus fréquents qu'un bon aléatoire générateur de nombres qui se passe à choisir à plusieurs reprises l'élément le plus petit.

Dans leur livre, ils utilisent le schéma de partition Hoare. Plus bas, ils disent:

On peut montrer, cependant, que la moyenne (sur tous les fichiers de taille $ N $), le quicksort fait environ 1,386 $ n \ n comparaisons $ lg même dans sa version non modifiée.

Il parle ici de choisir le premier élément comme le pivot.

EDIT

Je crois que je viens sur la réponse trébuché à la façon dont une sélection déterministe de pivot surclasse une répartition aléatoire.

Question à Cormen est de 9,3 à 3, " Montrez comment quicksort peut être fait pour fonctionner dans O $ (n \ logn) $ temps dans le pire des cas. "

La réponse consiste à utiliser la sélection déterministe pour sélectionner l'élément médian chaque fois. Depuis des pistes de sélection déterministe dans O $ (n) $ temps pire des cas, vous obtenez le pire des cas récursion $$ T (n) = 2T (n / 2) + T (n) = T (n \ n lg) $$ pour ce quicksort déterministe, il est vrai avec un facteur constant caché là-dedans.

Je pense que ce Bentely fait est une extension de cette idée en utilisant une médiane pseudo. Les références de papier de Bentely un autre papier qui quantifie la qualité de ces valeurs médianes pseudo.

Le coût du calcul de la médiane pseudo est $ \ theta (1) $ alors trouver la médiane réelle est O $ (n) $. Ceci est probablement une grande partie de où son facteur constant très faible vient. Je suppose que les références papier Bentely prouve en quelque sorte que la médiane pseudo est « assez bon » pour garantir un pourcentage assez élevé de bonnes divisions par la fonction de partition pour donner les temps d'exécution ci-dessus.