Algorithme de classement basé sur la comparaison

Je voudrais classer ou trier une collection d'éléments (avec une taille potentiellement supérieure à 100 000) où les éléments de la collection n'ont pas de valeur intrinsèque (comparable), à la place Tout ce que j'ai est les comparaisons entre deux éléments qui ont été fournis par les utilisateurs de manière subjective.

Exemple: Considérons une collection avec des éléments de [a, b, c, d] et les comparaisons par les utilisateurs b > a, a > d, d > c. L'ordre correct de cette collection serait [b, a, d, c].

Cet exemple est simple, mais il pourrait y avoir des cas plus compliqués:

• , Puisque les comparaisons sont subjectifs, un utilisateur pourrait aussi dire que c > b. Dans ce cas, cela provoquerait un conflit avec l'ordre ci-dessus.
• Vous ne pouvez pas non plus avoir de comparaisons qui "connectent" tous les éléments, c'est-à-dire b > a, d > c. Auquel cas la commande est ambigu. Il pourrait être [b, a, d, c] ou [d, c, b, a]. Dans ce cas, l'une ou l'autre commande est acceptable.

Si possible, il serait bon de prendre en tenez compte de plusieurs instances de la même comparaison et donnez plus de poids à celles ayant des occurrences plus élevées. Mais une solution sans cette condition serait toujours acceptable.

Une application similaire de cet algorithme a été utilisée par L'application FaceMash de Zuckerberg où il a classé les gens en fonction des comparaisons (si je l'ai bien compris), mais je n'ai pas été en mesure de trouver ce que cet algorithme était réellement.

Est-il un algorithme qui existe déjà et peut résoudre le problème ci-dessus? Je ne voudrais pas dépenser des efforts pour essayer d'en trouver un si tel est le cas. Si il n'y a pas d'algorithme spécifique, est-il peut-être certains types d'algorithmes ou les techniques que vous pouvez m'indiquer?