Tri rapide Affaire la plus défavorable

Question

Je suis en train de travailler sur le programme dont j'ai besoin pour le comprendre.

Quel est le pire temps de fonctionnement pour Quicksort et qu'est-ce qui peut causer cette pire performance? Comment pouvons-nous modifier le programme quicksort pour atténuer ce problème?

Je sais qu'il a le pire des cas O(n^2) et je sais qu'il se produit lorsque l'élément pivot unique minimum ou maximum. Ma question est comment puis-je modifier le programme pour atténuer ce problème.

Un bon algorithme sera bon.

Answer 1

Cela fait un moment, mais je pense que le pire des cas pour quicksort était lorsque les données étaient déjà triées. Une vérification rapide pour voir si les données sont déjà triées pourrait aider à résoudre ce problème.

Answer 2

Une modification facile consiste à choisir le pivot au hasard. Cela donne de bons résultats with high probability.

Answer 3

Les performances de Quicksort dépendent de votre algorithme de sélection de pivot. L'algorithme de sélection de pivot le plus naïf consiste simplement à choisir le premier élément comme pivot. Il est facile de voir que cela entraîne le pire des cas si vos données sont déjà triées (le premier élément sera toujours le min).

Il existe deux algorithmes courants pour résoudre ce problème: choisissez au hasard un pivot ou choisissez la médiane de trois. Aléatoire est évident, donc je ne vais pas entrer dans les détails. Médiane de trois implique la sélection de trois éléments (généralement le premier, le milieu et le dernier) et en choisissant la médiane de ceux-ci comme le pivot. Puisque les générateurs de nombres aléatoires sont typiquement pseudo-aléatoires (donc déterministes) et qu'une médiane non-aléatoire de trois algorithmes est déterministe, il est possible de construire des données qui aboutissent au pire des cas, mais il est rare qu'il apparaisse usage normal.

Vous devez également tenir compte de l'impact sur les performances. Le temps de fonctionnement de votre générateur de nombres aléatoires affectera la durée de votre quicksort. Avec une médiane de trois, vous augmentez le nombre de comparaisons.

Answer 4

plus Mauvaise performance Condition:

Lorsque chaque pivot de temps choisi est 'le plus grand' ou 'petit' et ce motif se répète

Donc, pour 1 3 5 4 2

Si pivots sont choisis dans l'ordre 1,2,3,4,5 ou 5,4,3,2,1

alors le pire temps est O (n * n)

Comment éviter le pire des cas:

(1) Diviser le tableau en cinq sets.So si 1..100 les ensembles sont (1..20) (21..40) (41. 60) (61 .. 80) (81 ..100)

(2) Choisir médiane des cinq premiers éléments dans chacun de régler de façon (3) (23) (43) (63) (83)

(3) maintenant choisir la valeur médiane parmi les comme le pivot donc ici son (43)

Answer 5

Le temps d'exécution le plus défavorable dépend de la méthode de partition dans le tri rapide. Cela a deux aspects:

• sélection du pivot
• comment partitionner autour du pivot

De bonnes stratégies pour sélectionner le pivot ont été outlinied dans les postes précédents (médiane des valeurs médianes ou médiane de trois ou randomisation). Mais même si le pivot est judicieusement sélectionné, à l'extrême, si un tableau a tous les éléments égaux, il conduira au pire cas d'exécution si seulement deux partitions sont construites, car on portera les éléments égaux, c'est tous les éléments:

• cela provoque déstiné à appeler n fois, chacun de celui-ci prenant n/2 dans la conduite moyenne O (n²)
• ce n'est pas bon, parce que ce n'est pas un pire scénario théorique mais assez commun un
• notez qu'il n'est pas résolu en détectant la partition vide, car le pivot pourrait avoir la valeur d'élément la plus élevée ou la plus basse (par exemple, median est 5, qui est aussi la valeur la plus élevée, mais il peut y avoir quelques erreurs < 5 valeurs)

Un moyen de contourner ce problème consiste à diviser en trois partitions, une partie inférieure (éléments < pivotement), égal (= éléments pivotants) et une cloison supérieure. Les "éléments pivots" sont dans leur position finale. Les partitions inférieure et supérieure doivent encore être triées si elles ne sont pas vides. Avec la randomisation, la médiane des médianes ou une combinaison pour sélectionner un pivot, le pire des scénarios est assez rare mais pas impossible, ce qui laisse à l'algorithme une borne supérieure de O (n²).