9
votes

Quel est le vrai nom de la sorte médian et / ou où puis-je trouver plus de matériel dessus

Je lis, je lis le livre algorithmes en bref Publié par O'Reilly Media et je lisais la section sur le tri des algorithmes et j'ai trouvé un appelé type médian. Depuis que je n'en avais jamais entendu parler avant et mon manuel de CS3 (quels algorithmes couverts) ne l'avaient pas répertorié, je le googla et j'ai essayé de regarder sur Wikipedia et n'a rien trouvé. J'apprécierais grandement que si quelqu'un puisse fournir le nom, je pouvais facilement regarder l'algorithme sous ou me diriger vers d'autres ressources à ce sujet. Merci.

Aussi, d'après ce que je peux dire à propos de l'algorithme, c'est essentiellement QuicksTort, sauf qu'il utilise toujours la valeur médiane comme pivot. Par la valeur médiane, je veux dire qu'il semble scanner la matrice d'articles et choisir la valeur moyenne en tant que pivot, ne cueille pas l'élément du milieu dans la matrice en tant que pivot. En outre, le livre mentionne un Blum-Floyd-Pratt-Rivest-Tarjan (BFPRT) par rapport au type «Médian».


0 commentaires

4 Réponses :


2
votes

La plupart des versions de Quicksort Pick (par exemple) la médiane de trois éléments (typiquement les premier, moyen et dernier), donnant ce qu'on appelle normalement une médiane de 3 Quicksort. En commençant par l'élément moyen, car le pivot ne se qualifie généralement pas pour aucun nom autre que Just Quicksort.

Modifier ( beaucoup plus tard, après avoir vu la modification dans la question): Il apparaît que ce dont vous parlez consiste à utiliser l'algorithme "Médian des médianes" pour choisir l'élément de pivotement pour un tour rapide . L'algorithme médian des médianes est mieux connu pour être utilisé de manière indépendante comme alternative à (ou raffinement de, en fonction de votre point de vue) Sélection de l'algorithme de Hoare. Ceci est connu pour trouver la médiane (ou un autre rang, mais dans ce cas, nous ne nous soucions que de la médiane) en temps linéaire.

La dernière ligne est que le Trier est vraiment un atout. La description de Hoare du choix de l'élément de pivot ne nécessite ni n'interdit un support de sélection des médias:

La première étape du processus de partition consiste à choisir une valeur de clé particulière connue pour être dans la plage des touches des éléments du segment qui doit être triée. Une méthode simple permettant de garantir qu'il s'agisse de choisir la valeur clé réelle de l'un des éléments du segment. La valeur de la clé choisie sera appelée le lié ​​.

Bien sûr, presque tout le monde appelle maintenant le "pivot" au lieu de "lié", mais c'est surtout sans importance. La méthode utilisée pour choisir le pivot / lié est laissée ouverte.


4 commentaires

QuickSort est essentiellement une sorte médiane plus simple afin que vous soyez partiellement correct. Cependant, ce sont des algorithmes différents.


@ROBERTD.: Oui, avec le Modifier, il a fait une heure après avoir écrit la réponse, il est clair qu'il ne parle pas simplement d'un atout - mais quand j'ai écrit la réponse, ce n'était pas clair du tout. Descendre la réponse pour un défaut de la question. Hourra!


Comme je n'ai pas actuellement de superpuissance, je ne pouvais pas éventuellement savoir que je suis "en train de voter la réponse pour un défaut de la question". Cependant, j'ai corrigé l'erreur.


@ROBERTD.: Si vous regardez au bas de la question où il est indiqué "édité le 23 août à 5:12", la date / heure de celui-ci est un lien hypertexte qui vous permettra de voir l'historique d'édition de la question. Si vous regardez la date / heure de ma réponse d'origine, vous pouvez voir qu'il précède la modification.




0
votes

Oui, vous avez raison, il est similaire à Quicksort, mais il vaut mieux que QuicksTort de la manière dont il évite ces cas où vos matrices sont divisées très disportées (pas dans des moitiés égales). Parce que dans Quicksortort, nous ne pouvons pas être sûrs que chaque fois que notre tableau soit divisé en deux moitiés égales ou presque égales de moitié. En Tri médian, nous assurons cela en payant le prix de la recherche de médiane, mais cela pourrait être digne de faire un tri rapide semblable à la fusion et Avantages d'avoir le tri en place.


0 commentaires

0
votes

Je ne possède pas le livre mais je vais deviner. L'algorithme que le livre fait référence à l'algorithme FLOYD-RIVEST est le . Blum-Floyd-Pratt-Rivest-Tarjan (BFPRT) fait référence à ce document où ils discutent de leur précédent Pick (maintenant connu sous le nom de Médiane de médiane des médianes ) Algorithme de sélection:

m. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, R. E. TARJAN, «Time Bounds for Selection», Journal. Comp. et. SYS. Sci., Vol. 7, ISS. 4, pp. 448-461, 1973.

Ce document établit la compréhension rapide du problème de sélection en informatique.


0 commentaires