Home > Backend Development > C++ > body text

How to Sort Multi-Column Arrays in C Efficiently?

Mary-Kate Olsen
Release: 2024-11-04 15:54:02
Original
279 people have browsed it

How to Sort Multi-Column Arrays in C   Efficiently?

Multi-Column Array Sorting in C

Sorting multi-column arrays presents a challenge in C compared to Java's built-in capabilities. One efficient method involves utilizing the classic std::qsort function, which excels in sorting fixed arrays.

Comparator Implementation

To achieve the sorting, we define a comparator as a ternary string expression within the qsort function. This comparator conducts a multi-column sort by comparing the values sequentially. Below is the code snippet:

<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))));
}
Copy after login

In the ternary expression, we first compare the first column values (lhs[0] and rhs[0]). If they are equal, we proceed to compare the second column values (lhs[1] and rhs[1]). The result is negative, zero, or positive, indicating whether the first array should be placed before, at the same position, or after the second array, respectively.

Example Implementation

Consider a 2D array ar of size 10x2, filled with random data. We can use std::qsort and the custom comparator to sort the array by the first column values:

<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>
Copy after login

Complexity Analysis

The worst-case time complexity of std::qsort and the custom comparator is O(n log n), where n is the number of rows in the 2D array. However, for specific scenarios, such as when the array is nearly sorted, the average time complexity can be significantly lower.

Conclusion

By utilizing std::qsort and a custom comparator, we can efficiently sort multi-column 2D arrays in C . While not as convenient as Java's built-in sorting capabilities, this method provides a robust and performant solution for data ordering applications.

The above is the detailed content of How to Sort Multi-Column Arrays in C Efficiently?. For more information, please follow other related articles on the PHP Chinese website!

source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Latest Articles by Author
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template
About us Disclaimer Sitemap
php.cn:Public welfare online PHP training,Help PHP learners grow quickly!