Comment trier efficacement les tableaux multicolonnes en C ?

Tri de tableaux multi-colonnes en C

Le tri de tableaux multi-colonnes présente un défi en C par rapport aux capacités intégrées de Java. Une méthode efficace consiste à utiliser la fonction classique std::qsort, qui excelle dans le tri des tableaux fixes.

Implémentation du comparateur

Pour réaliser le tri, nous définissons un comparateur comme une expression de chaîne ternaire dans la fonction qsort. Ce comparateur effectue un tri multicolonne en comparant les valeurs séquentiellement. Ci-dessous l'extrait de code :

<code class="cpp">[](const void *arg1, const void *arg2) -> int
{
    int const *lhs = static_cast<int const *>(arg1);
    int const *rhs = static_cast<int const *>(arg2);
    return (lhs[0] < rhs[0]) ? -1
        : ((rhs[0] < lhs[0]) ? 1
        : (lhs[1] < rhs[1] ? -1
        : ((rhs[1] < lhs[1] ? 1 : 0))));
}

Dans l'expression ternaire, nous comparons d'abord les valeurs de la première colonne (lhs[0] et rhs[0]). S'ils sont égaux, nous procédons à la comparaison des valeurs de la deuxième colonne (lhs[1] et rhs[1]). Le résultat est négatif, zéro ou positif, indiquant si le premier tableau doit être placé avant, à la même position ou après le deuxième tableau, respectivement.

Exemple de mise en œuvre

Considérons un tableau 2D ar de taille 10x2, rempli de données aléatoires. Nous pouvons utiliser std::qsort et le comparateur personnalisé pour trier le tableau selon les valeurs de la première colonne :

<code class="cpp">int ar[10][2];

// Populate array with random data
...

// Sort the array using qsort
std::qsort(ar, 10, sizeof(*ar),
    [](const void *arg1, const void *arg2) -> int
    {
        int const *lhs = static_cast<int const *>(arg1);
        int const *rhs = static_cast<int const *>(arg2);
        return (lhs[0] < rhs[0]) ? -1
            : ((rhs[0] < lhs[0]) ? 1
            : (lhs[1] < rhs[1] ? -1
            : ((rhs[1] < lhs[1] ? 1 : 0))));
    });</code>

Analyse de complexité

La complexité temporelle dans le pire des cas de std::qsort et le comparateur personnalisé est O(n log n), où n est le nombre de lignes dans le tableau 2D. Cependant, pour des scénarios spécifiques, comme lorsque le tableau est presque trié, la complexité temporelle moyenne peut être considérablement inférieure.

Conclusion

En utilisant std::qsort et un comparateur personnalisé, nous pouvons trier efficacement des tableaux 2D multi-colonnes en C . Bien qu'elle ne soit pas aussi pratique que les capacités de tri intégrées de Java, cette méthode fournit une solution robuste et performante pour les applications de classement de données.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!