C++의 정렬 함수는 어떻게 작동합니까?

Question

다음 코드에서 sort() 기능은 어떻게 작동합니까? 우리가 배열이있는 경우 예를 들어, :

a [5] = {1,2,3,4,5}; 

을 나는 일종의 그것을 내 bool cmp() 기능, 를 사용하여 내림차순으로 내가 알고 싶은 : 작동합니까 방법 int a하는 요소이며 int b 인합니다 (매개 변수는 bool cmp() 함수), 언제 정렬합니까? bool cmp()은 언제 반환합니까? 0은 언제 반환합니까?

#include <iostream> 
#include <algorithm> 

using namespace std; 
bool cmp (int a , int b) 
{ 
    return (a > b); 
} 

int main() 
{ 
    int a[100]; 
    int n; 
    cin >> n; 
    for (int i=0 ; i<n ;i++) 
     cin >> a[i]; 

    sort(a,a+n,cmp); 
    cout << endl << endl; 
    for (int i=0 ; i<n ;i++) 
     cout << a[i] << " "; 



    return 0; 
} 

Answer 1

구현 방법은 표준 라이브러리의 구현에 달려 있습니다. 복잡성은 O(Nlog(N))입니다. 일반적인 구현은 quicksort 또는 introsort을 사용합니다.

비교 함수는 첫 번째 인수가 2보다 엄격하게보다 작 으면 true을 반환해야하는 이진 함수입니다. 구현에서는이 함수를 사용하여 컨테이너의 두 요소를 비교하여 어떤 컨테이너를 선행해야하는지 판단합니다. 따라서 a 및 b은 컨테이너의 두 요소가 될 수 있습니다. 이 함수는 요소에 대해 엄격한 약한 순서를 지정해야합니다. 즉 :

이

• 요소가 자체
• x < y 것보다 작을 수는 없습니다, y < x
• x < z

다음, x < y 경우와 y < z 것은 당신이 돈 '하면하는 경우가 아니다 비교 기능을 제공하려면 operator<이 사용됩니다. 마찬가지로, 비교 함수로 std::less을 전달할 수 있습니다.

Answer 2

확인 여기 정렬 방법의 참조 : http://en.cppreference.com/w/cpp/algorithm/sort

첫 번째 매개 변수는 시작 포인터이다. 두 번째 매개 변수는 끝 포인터입니다. 세 번째 매개 변수는 선택 사항입니다. 정렬 방법을 정의하는 비교 함수입니다.