Dénombrer les inversions dans une liste d'entiers

Soit S = ⟨s1, s2, s3, ... ,sn⟩ une suite de n entiers distincts. On dit que les indices i < j forment une inversion si si > sj. Un problème intéressant consiste à déterminer le nombre d’inversions dans S.

Deux solutions

Une solution naïve à ce problème consiste simplement à comparer chaque élément de la liste deux à deux en incrémentant, selon le cas, un compteur d'inversions.

int inversions(const std::vector<int>& list) {

    if (list.size() < 2)
        return 0;

    int count = 0;
    std::vector<int>::size_type i;
    for (i = 0; i < list.size() - 1; ++i) {
        std::vector<int>::size_type j;
        for (j = i + 1; j < list.size(); ++j) {
            if (list[i] > list[j]) {
                count++;
            }
        }
    }
    return count;
}

La complexité de cet algorithme peut facilement être évaluée en résolvant quelques sommations:

Certes, cette solution de complexité quadratique est tout à fait convenable. Néanmoins, il est certainement possible de faire mieux. Et justement, comme quoi les choses sont bien faites, la phase de fusion du tri fusion peut facilement être modifiée pour résoudre le problème avec une complexité quasi-linéaire — n log(n).

int _inversions(std::vector<int>& list) {

    if (list.size() < 2)
        return 0;

    int count = 0;

    std::vector<int>::iterator middle = list.begin();
    std::advance(middle, list.size() / 2);

    std::vector<int> left(list.begin(), middle);
    std::vector<int> right(middle, list.end());

    count += _inversions(left);
    count += _inversions(right);

    std::vector<int>::size_type i = 0, j = 0, k = 0;
    while (i < left.size() and j < right.size()) {
        if (left[i] <= right[j]) {
            list[k] = left[i];
            i++;
        } else {
            // Elements were in reverse order.
            // Increment the inversions count.
            count += left.size() - i;
            list[k] = right[j];
            j++;
        }
        k++;
    }

    // Put the remaining elements in the original list.
    if (i == left.size()) {
        while (k != list.size())
            list[k++] = right[j++];
    } else {
        while (k != list.size())
            list[k++] = left[i++];
    }

    return count;
}

int inversions(std::vector<int> list) {
    return _inversions(list);
}

Étonnement, la complexité de ce second algorithme est la même que celle du tri fusion. En particulier, la relation de récurrence suivante permet de caractériser son comportement:

En appliquant le théorème général, on obtient sans surprise, comme temps d'exécution en pire cas, Cworst(n) ∈ Θ(n log(n)). Il s'agit donc bien d'un algorithme opérant en temps quasi-linéaire.

L'efficacité de cet algorithme est attribuable aux informations particulières qui sont disponibles lors de la phase de fusion du tri fusion. En effet, les deux listes à fusionner étant triées, il est possible de déterminer en temps constant le nombre d'inversions associées au placement de chaque élément.

Par exemple, dans la figure ci-dessous, lorsque l'élément «1» est placé en première position de la liste fusionnée, il est correct d'affirmer que les trois éléments de liste gauche constituent des inversions par rapport à ce dernier. Trois inversions peuvent dès lors être comptabilisées, soit le nombre d'éléments restants dans la liste gauche.

De même, lorsque l'élément «3» est placé en troisième position de la liste fusionnée, il est correct d'affirmer que les éléments «4» et «6» constituent des inversions par rapport à ce dernier. Deux inversions sont alors comptabilisées, soit le nombre d'éléments restants dans la liste gauche.

Finalement, lorsque l'élément «5» est placé dans la liste fusionnée en cinquième position, l'élément «6» constitue forcément une inversion par rapport à ce dernier. Une inversion est donc comptabilisée, soit le nombre d'éléments restants dans la liste gauche.

Au total, 6 inversions auront donc été comptabilisées lors de la fusion de ces deux listes.

Comparaison empirique

Comme le montre la figure ci-dessous, les résultats empiriques confirment la supériorité de l'algorithme dérivé du tri fusion.

Temps d'exécution en fonction de la taille de l'instance.

Il est tout de même intéressant de constater qu'en deçà de 150 éléments, l'algorithme quadratique supplante l'algorithme quasi-linéaire.

Temps d'exécution en fonction de la taille de l'instance.

Le code source utilisé pour générer les données de test peut être consulté en ligne. La classe Chronometer a fait l'objet d'un précédent texte.