C++
정렬

비고

지정된 순서에 따라 시퀀스 컨테이너 정렬

컨테이너의 값에 특정 연산자가 이미 오버로드 된 경우 std::sort 를 특수 펑크와 함께 사용하여 오름차순 또는 내림차순으로 std::sort 할 수 있습니다.

#include <vector>
#include <algorithm>
#include <functional>

std::vector<int> v = {5,1,2,4,3};

//sort in ascending order (1,2,3,4,5)
std::sort(v.begin(), v.end(), std::less<int>());

// Or just:
std::sort(v.begin(), v.end());

//sort in descending order (5,4,3,2,1)
std::sort(v.begin(), v.end(), std::greater<int>());

//Or just:
std::sort(v.rbegin(), v.rend());

std::sort(v.begin(), v.end(), std::less<>());     // ascending order
std::sort(v.begin(), v.end(), std::greater<>());  // descending order

과부하가 적은 연산자로 시퀀스 컨테이너 정렬

순서 지정 함수가 전달되지 않으면 std::sort 는 bool (또는 bool )로 컨텍스트로 변환 할 수있는 유형을 반환해야하는 요소 쌍에서 operator< 를 호출하여 요소를 std::sort 합니다. 기본 유형 (정수, 부동 소수점, 포인터 등)은 이미 비교 연산자로 작성되어 있습니다.

이 연산자를 오버로드하여 기본 sort 호출이 사용자 정의 유형에서 작동하도록 할 수 있습니다.

// Include sequence containers
#include <vector>
#include <deque>
#include <list>

// Insert sorting algorithm
#include <algorithm>    

class Base {
 public:

    // Constructor that set variable to the value of v
    Base(int v): variable(v) {
    }
    
    // Use variable to provide total order operator less
    //`this` always represents the left-hand side of the compare.
    bool operator<(const Base &b) const { 
        return this->variable < b.variable;
    }
    
    int variable;
};

int main() {
    std::vector <Base> vector;
    std::deque <Base> deque;
    std::list <Base> list;
    
    // Create 2 elements to sort
    Base a(10);
    Base b(5);
    
    // Insert them into backs of containers
    vector.push_back(a);
    vector.push_back(b);
    
    deque.push_back(a);
    deque.push_back(b);
    
    list.push_back(a);
    list.push_back(b);
    
    // Now sort data using operator<(const Base &b) function
    std::sort(vector.begin(), vector.end());
    std::sort(deque.begin(), deque.end());
    // List must be sorted differently due to its design
    list.sort();

    return 0;
}

compare 함수를 사용하여 시퀀스 컨테이너 정렬

// Include sequence containers
#include <vector>
#include <deque>
#include <list>

// Insert sorting algorithm
#include <algorithm>

class Base {
 public:

    // Constructor that set variable to the value of v
    Base(int v): variable(v) {
    }
       
    int variable;
};

bool compare(const Base &a, const Base &b) {
    return a.variable < b.variable;
}

int main() {
    std::vector <Base> vector;
    std::deque <Base> deque;
    std::list <Base> list;
    
    // Create 2 elements to sort
    Base a(10);
    Base b(5);
    
    // Insert them into backs of containers
    vector.push_back(a);
    vector.push_back(b);
    
    deque.push_back(a);
    deque.push_back(b);
    
    list.push_back(a);
    list.push_back(b);
    
    // Now sort data using comparing function
    std::sort(vector.begin(), vector.end(), compare);
    std::sort(deque.begin(), deque.end(), compare);
    list.sort(compare);

    return 0;
}

람다 식을 사용하여 시퀀스 컨테이너 정렬 (C ++ 11)

// Include sequence containers
#include <vector>
#include <deque>
#include <list>
#include <array>
#include <forward_list>

// Include sorting algorithm
#include <algorithm>

class Base {
 public:

    // Constructor that set variable to the value of v
    Base(int v): variable(v) {
    }
    
    int variable;
};


int main() {
    // Create 2 elements to sort
    Base a(10);
    Base b(5);
    
    // We're using C++11, so let's use initializer lists to insert items.
    std::vector <Base> vector = {a, b};
    std::deque <Base> deque = {a, b};
    std::list <Base> list = {a, b};
    std::array <Base, 2> array = {a, b};
    std::forward_list<Base> flist = {a, b};
    
    // We can sort data using an inline lambda expression
    std::sort(std::begin(vector), std::end(vector),
      [](const Base &a, const Base &b) { return a.variable < b.variable;});

    // We can also pass a lambda object as the comparator
    // and reuse the lambda multiple times
    auto compare = [](const Base &a, const Base &b) {
                     return a.variable < b.variable;};
    std::sort(std::begin(deque), std::end(deque), compare);
    std::sort(std::begin(array), std::end(array), compare);
    list.sort(compare);
    flist.sort(compare);

    return 0;
}

컨테이너 정렬 및 정렬

표준 라이브러리 헤더 algorithm 에있는 std::sort 는 일련의 반복자에 의해 정의 된 값 범위를 정렬하기위한 표준 라이브러리 알고리즘입니다. std::sort 는 마지막 매개 변수로 두 값을 비교하는 데 사용되는 Functor를 사용합니다. 이것이 순서를 결정하는 방법입니다. std::sort 는 안정적 이지 않습니다.

비교 함수 는 요소에 Strict, Weak Ordering 을 부과 해야합니다 . 간단하지 않은 (또는보다 큼) 비교만으로 충분할 것입니다.

랜덤 액세스 반복자가있는 컨테이너는 std::sort 알고리즘을 사용하여 정렬 할 수 있습니다.

#include <vector>
#include <algorithm>

std::vector<int> MyVector = {3, 1, 2}

//Default comparison of <
std::sort(MyVector.begin(), MyVector.end());

std::sort 는 iterators가 무작위 접근 iterator임을 요구한다. 시퀀스 컨테이너 std::list 및 std::forward_list (C ++ 11 필요)는 임의 액세스 반복기를 제공하지 않으므로 std::sort 와 함께 사용할 수 없습니다. 그러나, 그들은해야 할 sort 자신의 반복자 유형에서 작동하는 정렬 알고리즘을 구현하는 멤버 함수를.

#include <list>
#include <algorithm>

std::list<int> MyList = {3, 1, 2}

//Default comparison of <
//Whole list only.
MyList.sort();

멤버 sort 함수는 항상 전체 목록을 정렬하므로 하위 범위의 요소를 정렬 할 수 없습니다. 그러나 list 와 forward_list 는 빠른 스플 라이스 작업을하기 때문에 목록에서 정렬 할 요소를 추출하고 정렬 한 다음 매우 효율적으로 다시 정렬 할 수 있습니다.

void sort_sublist(std::list<int>& mylist, std::list<int>::const_iterator start, std::list<int>::const_iterator end) {
    //extract and sort half-open sub range denoted by start and end iterator 
    std::list<int> tmp;
    tmp.splice(tmp.begin(), list, start, end);
    tmp.sort();
    //re-insert range at the point we extracted it from
    list.splice(end, tmp);
}

std :: map (오름차순 및 내림차순) 정렬

이 예제는 맵을 사용하여 키 의 오름차순으로 요소를 정렬합니다. 아래 예제에서 std::string 대신 class를 포함한 모든 유형을 사용할 수 있습니다.

#include <iostream>
#include <utility>
#include <map>

int main()
{
    std::map<double, std::string> sorted_map;
    // Sort the names of the planets according to their size
    sorted_map.insert(std::make_pair(0.3829, "Mercury"));
    sorted_map.insert(std::make_pair(0.9499, "Venus"));
    sorted_map.insert(std::make_pair(1,      "Earth"));
    sorted_map.insert(std::make_pair(0.532,  "Mars"));
    sorted_map.insert(std::make_pair(10.97,  "Jupiter"));
    sorted_map.insert(std::make_pair(9.14,   "Saturn"));
    sorted_map.insert(std::make_pair(3.981,  "Uranus"));
    sorted_map.insert(std::make_pair(3.865,  "Neptune"));

    for (auto const& entry: sorted_map)
    {
        std::cout << entry.second << " (" << entry.first << " of Earth's radius)" << '\n';
    }
}

산출:

Mercury (0.3829 of Earth's radius)
Mars (0.532 of Earth's radius)
Venus (0.9499 of Earth's radius)
Earth (1 of Earth's radius)
Neptune (3.865 of Earth's radius)
Uranus (3.981 of Earth's radius)
Saturn (9.14 of Earth's radius)
Jupiter (10.97 of Earth's radius)

동일한 키 항목이 가능한 경우, 사용 multimap 대신 map (다음 예 등).

내림차순 으로 요소를 정렬하려면 적절한 비교 함수 ( std::greater<> )를 사용하여지도를 선언하십시오.

#include <iostream>
#include <utility>
#include <map>

int main()
{
    std::multimap<int, std::string, std::greater<int>> sorted_map;
    // Sort the names of animals in descending order of the number of legs
    sorted_map.insert(std::make_pair(6,   "bug"));
    sorted_map.insert(std::make_pair(4,   "cat"));
    sorted_map.insert(std::make_pair(100, "centipede"));
    sorted_map.insert(std::make_pair(2,   "chicken"));
    sorted_map.insert(std::make_pair(0,   "fish"));
    sorted_map.insert(std::make_pair(4,   "horse"));
    sorted_map.insert(std::make_pair(8,   "spider"));

    for (auto const& entry: sorted_map)
    {
        std::cout << entry.second << " (has " << entry.first << " legs)" << '\n';
    }
}

산출

centipede (has 100 legs)
spider (has 8 legs)
bug (has 6 legs)
cat (has 4 legs)
horse (has 4 legs)
chicken (has 2 legs)
fish (has 0 legs)

내장 배열 정렬하기

sort 알고리즘은 두 개의 반복기로 정의 된시 v 스를 sort 합니다. 이렇게하면 내장 (또는 C 스타일이라고도 함) 배열을 정렬 할 수 있습니다.

int arr1[] = {36, 24, 42, 60, 59};

// sort numbers in ascending order
sort(std::begin(arr1), std::end(arr1));

// sort numbers in descending order
sort(std::begin(arr1), std::end(arr1), std::greater<int>());

C ++ 11 이전에는 배열의 끝을 배열의 크기를 사용하여 "계산"해야했습니다.

// Use a hard-coded number for array size
sort(arr1, arr1 + 5);

// Alternatively, use an expression
const size_t arr1_size = sizeof(arr1) / sizeof(*arr1);
sort(arr1, arr1 + arr1_size);