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)))); }
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>
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!