Comment mesurer le «tri»

Je me demande s'il existe un moyen standard de mesurer le "tri" d'un tableau? Un tableau contenant le nombre médian d'inversions possibles serait-il considéré comme non trié au maximum? J'entends par là qu'il est fondamentalement aussi loin que possible d'être trié ou inversé.

Non, cela dépend de votre application. Les mesures de tri sont souvent appelées mesures de désordre , fonctions de à , où est la collection de toutes les séquences finies d'entiers non négatifs distincts. L’enquête d’Estivill-Castro et Wood [1] recense et analyse 11 mesures différentes du désordre dans le contexte des algorithmes de tri adaptatif.$N^{<N}$$\mathbb{R}$$N^{<N}$

Le nombre d'inversions peut fonctionner dans certains cas, mais est parfois insuffisant. Un exemple donné dans [1] est la séquence

qui a un nombre quadratique d'inversions, mais seulement constitué de deux courses ascendantes. Il est presque trié, mais ceci n'est pas capturé par des inversions.

[1] Estivill-Castro, Vladmir et Derick Wood. "Une enquête sur les algorithmes de tri adaptatif." ACM Computing Surveys (CSUR) 24.4 (1992): 441-476.

Mannila [1] axiomatise le pré-tri (en mettant l’accent sur des algorithmes de comparaison) comme suit (paraphrasant).

Soit un ensemble totalement ordonné. Ensuite, une correspondance de (les séquences d'éléments distincts de ) aux éléments naturels est une mesure de la présélection si elle satisfait aux conditions ci-dessous.$\Sigma$$m$$\Sigma^{\star}$$\Sigma$

1. Si est trié, alors .$X \in \Sigma^{\star}$$m(X) = 0$

2. Si avec , et pour tout , alors .$X,Y \in \Sigma^{\star}$$X = x_1 \dots x_n$$Y = y_1 \dots y_n$$x_i < x_i \iff y_i < y_j$$i,j \in [1..n]$$m(X) = m(Y)$

3. Si est une sous-séquence de , alors .$X$$Y \in \Sigma^{\star}$$m(X) \leq m(Y)$

4. Si pour tout et pour un certain , alors .$x_i < y_j$$i \in [1..|X|]$$j \in [1..|Y|]$$X,Y \in \Sigma^{\star}$$m(X \cdot Y) \leq m(X) + m(Y)$

5. $m(a \cdot X) \leq |X| + m(X)$ pour tous et .$X \in \Sigma^{\star}$$a \in E \setminus X$

Des exemples de telles mesures sont les

• nombre d'inversions,
• nombre de swaps,
• le nombre d'éléments qui ne sont pas des maxima de gauche à droite, et
• la longueur d'une sous-séquence croissante la plus longue (soustraite de la longueur entrée).

Notez que des distributions aléatoires utilisant ces mesures ont été définies, c'est-à-dire telles que des séquences plus / moins triées sont plus ou moins probables. Celles-ci sont appelées distributions de type Ewens [2, Ch. 4-5; 3, exemple 12; 4], dont un cas particulier est la distribution dite de Mallows . Les poids sont paramétriques dans une constante et remplissent$\theta > 0$

$\qquad\displaystyle \operatorname{Pr}(X) = \frac{\theta^{\,m(X)}}{\sum_{Y \in \Sigma^{\star} \cap \Sigma^{|X|}} \theta^{\,m(Y)}}$ .

Notez comment définit la distribution uniforme (pour tout ).$\theta = 1$$m$

Puisqu'il est possible d'échantillonner efficacement les permutations de ces mesures, ce travail peut être utile en pratique lors de l'analyse comparative des algorithmes de tri.

1. Mesures de tri sélectif et algorithmes de tri optimaux par H. Mannila (1985)
2. Structures combinatoires logarithmiques: une approche probabiliste de R. Arratia, AD Barbour et S. Tavaré (2003)
3. Sur l'ajout d'une liste de nombres (et d'autres processus déterminants à une dépendance) de A. Borodin, P. Diaconis et J. Fulman (2010)
4. Distributions de type Ewens et analyse d'algorithmes par N. Auger et al. (2016)

J'ai ma propre définition du "tri" d'une séquence.

Quelle que soit la séquence [a, b, c,…], nous la comparons à la séquence triée contenant les mêmes éléments, comptons le nombre de correspondances et la divisons par le nombre d'éléments de la séquence.

Par exemple, séquence donnée, [5,1,2,3,4]nous procédons comme suit:

1) trier la séquence: [1,2,3,4,5]

2) comparez la séquence triée avec l'original en la déplaçant d'une position à la fois et en comptant le nombre maximal de correspondances:

        [5,1,2,3,4]
[1,2,3,4,5]                            one match

        [5,1,2,3,4]
  [1,2,3,4,5]                          no matches

        [5,1,2,3,4]
    [1,2,3,4,5]                        no matches

        [5,1,2,3,4]
      [1,2,3,4,5]                      no matches

        [5,1,2,3,4]
        [1,2,3,4,5]                    no matches

        [5,1,2,3,4]
          [1,2,3,4,5]                  4 matches

        [5,1,2,3,4]
            [1,2,3,4,5]                no matches

                ...

         [5,1,2,3,4]
                 [1,2,3,4,5]            no matches

3) Le nombre maximal de correspondances est 4, nous pouvons calculer le "sort" comme 4/5 = 0.8.

Le tri d'une séquence triée serait 1 et le tri d'une séquence avec des éléments placés dans l'ordre inverse serait 1 / n.

L'idée sous-jacente à cette définition est d'estimer la quantité minimale de travail nécessaire pour convertir une séquence en une séquence triée. Dans l'exemple ci-dessus, nous ne devons déplacer qu'un élément, le 5 (il y a plusieurs façons, mais le déplacement de 5 est le plus efficace). Lorsque les éléments seraient placés dans l'ordre inverse, nous aurions besoin de déplacer 4 éléments. Et lorsque la séquence a été triée, aucun travail n'est nécessaire.

J'espère que ma définition a du sens.

Si vous avez besoin de quelque chose de rapide et de sale (les signes de sommation me font peur), j'ai écrit une fonction de désordre super facile en C ++ pour une classe appelée Array qui génère des tableaux int contenant des nombres générés aléatoirement:

void Array::disorder() {
    double disorderValue = 0;
    int counter = this->arraySize;
    for (int n = 0; n < this->arraySize; n++) {
        disorderValue += abs(((n + 1) - array[n]));
//      cout << "disorderValue variable test value = " << disorderValue << endl;
        counter++;
    }
    cout << "Disorder Value = " << (disorderValue / this->arraySize) / (this->arraySize / 2) << "\n" << endl;
}

Function compare simplement la valeur de chaque élément à l'index de l'élément + 1, de sorte qu'un tableau inversé a une valeur de désordre de 1 et qu'un tableau trié possède une valeur de désordre de 0. Pas sophistiqué, mais fonctionnel.

Michael