Comment mesurer le «tri»

34

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é.

Robert S. Barnes
la source

Réponses:

31

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<NRN<N

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

n/2+1,n/2+2,,n,1,,n/2

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.

Juho
la source
2
Le contexte tente de comprendre pourquoi quicksort fonctionne relativement mal avec des permutations aléatoires de n éléments où le nombre d'inversions est proche de la médiane.
Robert S. Barnes
1
Excellent exemple, c'est exactement l'info que je cherchais.
Robert S. Barnes
1
Estivill-Castro et du bois est LA référence pour cette certitude.
Pedro Dusso
10

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.ΣmΣΣ

  1. Si est trié, alors .XΣm(X)=0

  2. Si avec , et pour tout , alors .X,YΣX=x1xnY=y1ynxi<xiyi<yji,j[1..n]m(X)=m(Y)

  3. Si est une sous-séquence de , alors .XYΣm(X)m(Y)

  4. Si pour tout et pour un certain , alors .xi<yji[1..|X|]j[1..|Y|]X,YΣm(XY)m(X)+m(Y)

  5. m(aX)|X|+m(X) pour tous et .XΣaEX

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θ>0

Pr(X)=θm(X)YΣΣ|X|θm(Y) .

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

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)
Raphaël
la source
3

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.

Andrushenko Alexander
la source
Bonne idée. Une définition similaire est Exc, la troisième définition du désordre dans le document mentionné dans la réponse de Juho . Exc est le nombre d'opérations nécessaires pour réorganiser une séquence en ordre de tri.
Apass.Jack
Eh bien, peut-être, je viens d'appliquer ma compréhension de l'entropie et du désordre à la séquence des éléments :-)
Andrushenko Alexander
-2

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

Michael Sneberger
la source
Ce n'est pas un site de programmation. Il aurait suffi de définir la notion de désordre et de mentionner qu'elle peut être calculée en temps linéaire.
Yuval Filmus