Existe-t-il un moyen de mesurer le tri d'une liste?
Je veux dire, il ne s'agit pas de savoir si une liste est triée ou non (booléen), mais quelque chose comme un rapport de «tri», quelque chose comme le coefficient de corrélation dans les statistiques.
Par exemple,
Si les éléments d'une liste sont dans l'ordre croissant, son taux serait de 1,0
Si la liste est triée par ordre décroissant, son taux serait de -1,0
Si la liste est presque triée par ordre croissant, son taux serait de 0,9 ou une valeur proche de 1.
Si la liste n'est pas triée du tout (aléatoire), son taux serait proche de 0
J'écris une petite bibliothèque à Scala pour m'entraîner. Je pense qu'un taux de tri serait utile, mais je ne trouve aucune information sur quelque chose comme ça. Peut-être que je ne connais pas les termes adéquats pour le concept.
Réponses:
Vous pouvez simplement compter le nombre d'inversions dans la liste.
Inversion
Une inversion dans une séquence d'éléments de type
T
est une paire d'éléments de séquence qui apparaissent dans le désordre selon un ordre<
sur l'ensemble desT
's.De Wikipedia :
Pour rendre ces définitions plus claires, considérez l'exemple de séquence
9, 5, 7, 6
. Cette séquence a les inversions(0,1), (0,2), (0,3), (2,3)
et le numéro d'inversion4
.Si vous voulez une valeur entre
0
et1
, vous pouvez diviser le nombre d'inversion parN choose 2
.Pour créer réellement un algorithme pour calculer ce score en fonction du tri d'une liste, vous avez deux approches:
Approche 1 (déterministe)
Modifiez votre algorithme de tri préféré pour garder une trace du nombre d'inversions qu'il corrige pendant son exécution. Bien que cela ne soit pas trivial et ait des implémentations variables en fonction de l'algorithme de tri que vous choisissez, vous vous retrouverez avec un algorithme qui n'est pas plus cher (en termes de complexité) que l'algorithme de tri avec lequel vous avez commencé.
Si vous empruntez cette voie, sachez que ce n'est pas aussi simple que de compter les «swaps». Mergesort, par exemple, est le pire des cas
O(N log N)
, mais s'il est exécuté sur une liste triée par ordre décroissant, il corrigera toutes lesN choose 2
inversions. Ce sont desO(N^2)
inversions corrigées dans lesO(N log N)
opérations. Ainsi, certaines opérations doivent inévitablement corriger plus d'une inversion à la fois. Vous devez être prudent avec votre mise en œuvre. Remarque: vous pouvez le faire avecO(N log N)
complexité, c'est juste délicat.En relation: calcul du nombre «d'inversions» dans une permutation
Approche 2 (stochastique)
(i,j)
, oùi != j
list[min(i,j)] < list[max(i,j)]
(0 ou 1)N choose 2
Personnellement, j'opterais pour l'approche stochastique à moins que vous n'ayez une exigence d'exactitude - ne serait-ce que parce qu'elle est si facile à mettre en œuvre.
Si vous voulez vraiment une valeur (
z'
) entre-1
(triée par ordre décroissant) et1
(triée par ordre croissant), vous pouvez simplement mapper la valeur ci-dessus (z
), qui se situe entre0
(triée par ordre croissant) et1
(triée par ordre décroissant), à cette plage en utilisant cette formule :la source
La mesure traditionnelle du tri d'une liste (ou d'une autre structure séquentielle) est le nombre d'inversions.
Le nombre d'inversions est le nombre de paires (a, b) st indice de a <b ET b
<<
a. À ces fins,<<
représente la relation de commande que vous choisissez pour votre tri particulier.Une liste entièrement triée n'a pas d'inversions, et une liste complètement inversée a le nombre maximum d'inversions.
la source
5 4 3 2 1
est entièrement trié car l'ordre n'est pas spécifié, mais je suis pédant :-)<
.n choose 2
.Vous pouvez utiliser la corrélation réelle.
Supposons qu'à chaque élément de la liste triée, vous attribuez un rang entier à partir de zéro. Notez qu'un graphique de l'indice de position des éléments en fonction du rang ressemblera à des points en ligne droite (corrélation de 1,0 entre la position et le rang).
Vous pouvez calculer une corrélation sur ces données. Pour un tri inversé, vous obtiendrez -1 et ainsi de suite.
la source
Il y a eu d'excellentes réponses, et j'aimerais ajouter un aspect mathématique pour être complet:
Vous pouvez mesurer le degré de tri d'une liste en mesurant dans quelle mesure elle est corrélée à une liste triée. Pour ce faire, vous pouvez utiliser la corrélation de rang (la plus connue étant celle de Spearman ), qui est exactement la même que la corrélation habituelle, mais elle utilise le rang des éléments dans une liste au lieu des valeurs analogiques de ses éléments.
De nombreuses extensions existent, comme un coefficient de corrélation (+1 pour le tri exact, -1 pour l'inversion exacte)
Cela vous permet d'avoir des propriétés statistiques pour cette mesure, comme le théorème de limite centrale permutationnelle, qui vous permet de connaître la distribution de cette mesure pour les listes aléatoires.
la source
En dehors du nombre d'inversion, pour les listes numériques, la distance quadratique moyenne de l'état trié est imaginable:
la source
Je ne suis pas sûr de la "meilleure" méthode, mais une méthode simple serait de comparer chaque élément avec celui qui le suit, en incrémentant un compteur si élément2> élément 1 (ou ce que vous voulez tester), puis divisez par le nombre total d'éléments. Cela devrait vous donner un pourcentage.
la source
Je compterais les comparaisons et les diviserais par le nombre total de comparaisons. Voici un exemple simple de Python .
la source
Que diriez-vous quelque chose comme ça?
la source
Si vous prenez votre liste, calculez les rangs des valeurs dans cette liste et appelez la liste des rangs
Y
et une autre liste,X
qui contient les entiers de1
àlength(Y)
, vous pouvez obtenir exactement la mesure de tri que vous recherchez en calculant le coefficient de corrélation ,,r
entre les deux listes.Pour une liste entièrement triée ,,
r = 1.0
pour une liste triée inversementr=-1.0
, et ler
varie entre ces limites pour différents degrés de tri.Un problème possible avec cette approche, en fonction de l'application, est que le calcul du rang de chaque élément de la liste équivaut à le trier, il s'agit donc d'une opération O (n log n).
la source