J'essaie de comprendre pourquoi le tri rapide utilisant la partition Lomuto et un pivot fixe fonctionne de manière irrégulière, mais globalement médiocre, sur des entrées générées de manière aléatoire. Je pense que même si les entrées sont générées de manière aléatoire, il peut y avoir beaucoup d'ordre dans les séquences, mais je ne sais pas comment mesurer le niveau de désordre dans les séquences. J'ai pensé à utiliser le nombre d'inversions, mais j'ai vu à partir de cette autre question que j'ai demandé que ce n'était pas vraiment une bonne mesure dans ce cas.
La raison pour laquelle je soupçonne que mes séquences aléatoires ont beaucoup d '«ordre» est que la randomisation du pivot résout le problème de performances. Mais théoriquement, il ne devrait pas y avoir de problème de performances sur ces séquences d'entrée soi-disant "aléatoires".
la source
Réponses:
La partition Lomuto vs Hoare
Lomuto souffre lors du tri de clés égales, contrairement à la partition Hoare.
Les deux schémas de partition souffrent également lors de l'utilisation d'un pivot éloigné de la médiane.
Mesure du désordre
La mesure du désordre à choisir à des fins de tri rapide est simple.
R: À quelle distance de la médiane le pivot fixe est-il comparé aux données aléatoires?
Si vous insistez sur l'utilisation de la partition Lomuto et si vous supposez que les valeurs en double sont autorisées, vous devez ajouter le test suivant contre le caractère aléatoire:
B: combien d'éléments en double sont là, par rapport à aléatoire.
Bien sûr, il est plutôt stupide de supposer que les valeurs en double sont autorisées dans votre ensemble de données et d'évaluer toujours la partition Lomuto, vous devriez donc probablement éliminer les doublons à l'avance ou passer à la partition Hoare ou supposer que les doublons sont rares.
Les deux mesures sont triviales à quantifier à l'aide de statistiques.
Nous pouvons exclure les données pathologiques.
Tout autre écart par rapport au hasard n'aura pas d'importance aux fins de l'analyse de tri rapide. Tant que le pivot est proche de la médiane, il fonctionnera bien sur toutes les données qui ne sont pas pathologiques.
La distance par rapport au hasard devrait en effet être grande pour être rapide-pathologique, afin que nous puissions l'exclure.
N'utilisez jamais de pivot (s) fixe (s) dans du code réel.
Notez que si vous écrivez du code réel avec un pivot fixe *) (quel que soit ce pivot), vous vous exposez à une attaque par déni de service, car un attaquant peut insérer un valeur pathologique juste à ce point et donc vous devez toujours choisir un élément aléatoire comme pivot.
*) ou plusieurs pivots si vous choisissez le meilleur des x pivots.
la source