>백엔드 개발 >C++ >C에서 다중 열 배열을 효율적으로 정렬하는 방법은 무엇입니까?

C에서 다중 열 배열을 효율적으로 정렬하는 방법은 무엇입니까?

Mary-Kate Olsen
Mary-Kate Olsen원래의
2024-11-04 15:54:02344검색

How to Sort Multi-Column Arrays in C   Efficiently?

C의 다중 열 배열 정렬

C의 다중 열 배열 정렬은 Java의 내장 기능에 비해 어려운 작업입니다. 효율적인 방법 중 하나는 고정 배열 정렬에 탁월한 기존 std::qsort 함수를 활용하는 것입니다.

비교기 구현

정렬을 달성하기 위해 비교기를 다음과 같이 정의합니다. qsort 함수 내의 삼항 문자열 표현. 이 비교기는 값을 순차적으로 비교하여 다중 열 정렬을 수행합니다. 다음은 코드 조각입니다.

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

삼항 표현식에서는 먼저 첫 번째 열 값(lhs[0] 및 rhs[0])을 비교합니다. 동일하면 두 번째 열 값(lhs[1] 및 rhs[1])을 비교합니다. 결과는 음수, 0, 양수로 각각 첫 번째 배열을 두 번째 배열 앞, 같은 위치, 뒤에 배치해야 하는지 여부를 나타냅니다.

구현 예

임의의 데이터로 채워진 10x2 크기의 2D 배열 AR을 생각해 보세요. std::qsort 및 사용자 지정 비교기를 사용하여 첫 번째 열 값을 기준으로 배열을 정렬할 수 있습니다.

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

복잡성 분석

최악의 경우 시간 복잡도 std::qsort이고 사용자 정의 비교기는 O(n log n)입니다. 여기서 n은 2D 배열의 행 수입니다. 그러나 배열이 거의 정렬된 경우와 같은 특정 시나리오의 경우 평균 시간 복잡도가 크게 낮아질 수 있습니다.

결론

std::qsort 및 사용자 정의 비교기를 사용하면 C에서 다중 열 2D 배열을 효율적으로 정렬할 수 있습니다. Java에 내장된 정렬 기능만큼 편리하지는 않지만 이 방법은 데이터 정렬 애플리케이션을 위한 강력하고 성능이 뛰어난 솔루션을 제공합니다.

위 내용은 C에서 다중 열 배열을 효율적으로 정렬하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.