Move Fast

정렬 알고리즘 (Sorting Algorithm)

• sort 범위 내 원소들을 정렬.

  • 3번째 인자로 비교자 함수를 넘겨서 비교 순서를 정할 수 있음.

  • 오름차순 정렬이 디폴트

  • 시간 복잡도: O(N * log(N)), 범위의 크기 = N

#include <iostream>
#include <string>
#include <array>
#include <algorithm>
#include <functional>
using namespace std;

void print(string msg, array<int, 10> &arr) {
    cout << msg;
    for (auto a : arr) cout << a << " ";
    cout << endl;
}

int main() {
    array<int, 10> s = {5, 7, 4, 2, 8, 6, 1, 9, 0, 3};

    sort(s.begin(), s.end());
    print("Sort using the default operator<.\n", s);

    sort(s.begin(), s.end(), greater<int>());
    print("Sort using a standard library compare function object.\n", s);

    struct {
        bool operator()(int a, int b) const {
            return a < b;
        }
    } customLess;
    sort(s.begin(), s.end(), customLess);
    print("Sort using a custom function object.\n", s);

    // sort using a lambda expression
    sort(s.begin(), s.end(), [](int a, int b) {
        return a > b;
    });
    print("Sort using a lambda expression.\n", s);

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
Sort using the default operator<.
0 1 2 3 4 5 6 7 8 9
Sort using a standard library compare function object.
9 8 7 6 5 4 3 2 1 0
Sort using a custom function object.
0 1 2 3 4 5 6 7 8 9
Sort using a lambda expression.
9 8 7 6 5 4 3 2 1 0
 */

• is_sorted 범위 내 원소들이 정렬된 상태이면 true, 그렇지 않으면 false를 반환.

// since C++11 until C++20
template< class ForwardIt >
bool is_sorted( ForwardIt first, ForwardIt last );

// since C++20
template< class ForwardIt >
constexpr bool is_sorted( ForwardIt first, ForwardIt last );

// since C++17
template< class ExecutionPolicy, class ForwardIt >
bool is_sorted( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last );

// since C++11 until C++20
template< class ForwardIt, class Compare >
bool is_sorted( ForwardIt first, ForwardIt last, Compare comp );

// since C++20
template< class ForwardIt, class Compare >
constexpr bool is_sorted( ForwardIt first, ForwardIt last, Compare comp );

// since C++17
template< class ExecutionPolicy, class ForwardIt, class Compare >
bool is_sorted( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                Compare comp );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;

int main() {
    int digits[] = {3, 1, 4, 1, 5};

    for (auto i : digits) cout << i << ' ';
    cout << ": is_sorted: " << boolalpha;
    cout << is_sorted(begin(digits), end(digits)) << endl;

    sort(begin(digits), end(digits));

    for (auto i : digits) cout << i << ' ';
    cout << ": is_sorted: ";
    cout << is_sorted(begin(digits), end(digits)) << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
3 1 4 1 5 : is_sorted: false
1 1 3 4 5 : is_sorted: true
 */

• is_sorted_until 최초로 정렬되지 않은 범위의 첫번째 원소의 iterator를 반환.

// since C++11 until C++20
template< class ForwardIt >
ForwardIt is_sorted_until( ForwardIt first, ForwardIt last );

// since C++20
template< class ForwardIt >
constexpr ForwardIt is_sorted_until( ForwardIt first, ForwardIt last );

// since C++17
template< class ExecutionPolicy, class ForwardIt >
ForwardIt is_sorted_until( ExecutionPolicy&& policy,
                           ForwardIt first, ForwardIt last );

// since C++11 until C++20
template< class ForwardIt, class Compare >
ForwardIt is_sorted_until( ForwardIt first, ForwardIt last, Compare comp );

// since C++20
template< class ForwardIt, class Compare >
constexpr ForwardIt is_sorted_until( ForwardIt first, ForwardIt last, Compare comp );

// since C++17
template< class ExecutionPolicy, class ForwardIt, class Compare >
ForwardIt is_sorted_until( ExecutionPolicy&& policy,
                           ForwardIt first, ForwardIt last, Compare comp );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <algorithm>
#include <iterator>
#include <random>
using namespace std;

int main() {
    random_device rd;
    mt19937 g(rd());
    const int N = 6;
    int nums[N] = {3, 1, 4, 1, 5, 9};

    const int min_sorted_size = 4;
    int sorted_size = 0;
    do {
        shuffle(nums, nums + N, g);
        int *sorted_end = is_sorted_until(nums, nums + N);
        sorted_size = distance(nums, sorted_end);

        for (auto i : nums) cout << i << ' ';
        cout << " : " << sorted_size << " initial sorted elements" << endl;
    } while (sorted_size < min_sorted_size);

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
9 5 3 4 1 1  : 1 initial sorted elements
4 5 9 1 1 3  : 3 initial sorted elements
1 1 4 9 3 5  : 4 initial sorted elements
$ ./a.out
9 1 4 3 5 1  : 1 initial sorted elements
1 5 4 9 3 1  : 2 initial sorted elements
4 1 3 9 5 1  : 1 initial sorted elements
1 1 9 3 4 5  : 3 initial sorted elements
1 4 3 9 1 5  : 2 initial sorted elements
1 9 1 3 4 5  : 2 initial sorted elements
1 5 9 4 3 1  : 3 initial sorted elements
5 1 3 9 1 4  : 1 initial sorted elements
5 4 9 3 1 1  : 1 initial sorted elements
9 5 4 1 3 1  : 1 initial sorted elements
1 9 4 5 1 3  : 2 initial sorted elements
1 3 5 9 1 4  : 4 initial sorted elements
 */

• partial_sort 범위 내 부분 원소들만 정렬.

  • partial_sort_copy 정렬된 부분 원소들만 복사.

// until C++20
template< class RandomIt >
void partial_sort( RandomIt first, RandomIt middle, RandomIt last );

template< class RandomIt, class Compare >
void partial_sort( RandomIt first, RandomIt middle, RandomIt last,
                   Compare comp );

template< class InputIt, class RandomIt >
RandomIt partial_sort_copy( InputIt first, InputIt last,
                            RandomIt d_first, RandomIt d_last );

template< class InputIt, class RandomIt, class Compare >
RandomIt partial_sort_copy( InputIt first, InputIt last,
                            RandomIt d_first, RandomIt d_last,
                            Compare comp );

// since C++20
template< class RandomIt >
constexpr void partial_sort( RandomIt first, RandomIt middle, RandomIt last );

template< class RandomIt, class Compare >
constexpr void partial_sort( RandomIt first, RandomIt middle, RandomIt last,
                             Compare comp );

template< class InputIt, class RandomIt >
constexpr RandomIt partial_sort_copy( InputIt first, InputIt last,
                                      RandomIt d_first, RandomIt d_last );

template< class InputIt, class RandomIt, class Compare >
constexpr RandomIt partial_sort_copy( InputIt first, InputIt last,
                                      RandomIt d_first, RandomIt d_last,
                                      Compare comp );

// since C++17
template< class ExecutionPolicy, class RandomIt >
void partial_sort( ExecutionPolicy&& policy, 
                   RandomIt first, RandomIt middle, RandomIt last );

template< class ExecutionPolicy, class RandomIt, class Compare >
void partial_sort( ExecutionPolicy&& policy,
                   RandomIt first, RandomIt middle, RandomIt last,
                   Compare comp );

template< class ExecutionPolicy, class ForwardIt, class RandomIt >
RandomIt partial_sort_copy( ExecutionPolicy&& policy,
                            ForwardIt first, ForwardIt last,
                            RandomIt d_first, RandomIt d_last );

template< class ExecutionPolicy, class ForwardIt, class RandomIt, class Compare >
RandomIt partial_sort_copy( ExecutionPolicy&& policy,
                            ForwardIt first, ForwardIt last,
                            RandomIt d_first, RandomIt d_last,
                            Compare comp );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <functional>
using namespace std;

template <class T>
void print(string msg, T &s) {
    cout << msg;
    for (int a : s) cout << a << " ";
    cout << endl;
}

int main() {
    array<int, 10> s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
    print("Before partial_sort(): ", s);
    partial_sort(s.begin(), s.begin() + 3, s.end());
    print("After partial_sort(): ", s);

    vector<int> v0{4, 2, 5, 1, 3};
    vector<int> v1{10, 11, 12};
    vector<int> v2{10, 11, 12, 13, 14, 15, 16};
    cout << endl << "Before partial_sort_copy():" << endl;
    print("v0: ", v0);
    print("v1: ", v1);
    print("v2: ", v2);
    cout << "After partial_sort_copy():" << endl;
    auto it = partial_sort_copy(v0.begin(), v0.end(), v1.begin(), v1.end());
    print("Writing to the smaller vector in ascending order gives (v1): ", v1);
    if(it == v1.end())
        cout << "The return value is the end iterator" << endl;

    it = partial_sort_copy(v0.begin(), v0.end(), v2.begin(), v2.end(),
                           greater<int>());
    print("Writing to the larger vector in descending order gives (v2): ", v2);
    cout << "The return value is the iterator to " << *it << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
Before partial_sort(): 5 7 4 2 8 6 1 9 0 3
After partial_sort(): 0 1 2 7 8 6 5 9 4 3

Before partial_sort_copy():
v0: 4 2 5 1 3
v1: 10 11 12
v2: 10 11 12 13 14 15 16
After partial_sort_copy():
Writing to the smaller vector in ascending order gives (v1): 1 2 3
The return value is the end iterator
Writing to the larger vector in descending order gives (v2): 5 4 3 2 1 15 16
The return value is the iterator to 15
 */

• stable_sort 크기가 같은 원소의 상대적 순서를 유지한 상태로 정렬.

template< class RandomIt >
void stable_sort( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
void stable_sort( RandomIt first, RandomIt last, Compare comp );

// since C++17
template< class ExecutionPolicy, class RandomIt >
void stable_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last );

template< class ExecutionPolicy, class RandomIt, class Compare >
void stable_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last,
                  Compare comp );

// ----------------------------------------------------------------------------------
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct Employee {
    int age;
    string name;  // Does not participate in comparisons
};

bool operator<(const Employee & lhs, const Employee & rhs) {
    return lhs.age < rhs.age;
}

int main() {
    vector<Employee> v =
    {
        {108, "Zaphod"},
        {32, "Arthur"},
        {108, "Ford"},
    };

    stable_sort(v.begin(), v.end());
    for (const Employee & e : v)
        cout << e.age << ", " << e.name << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
32, Arthur
108, Zaphod
108, Ford
 */

• nth_element 범위 내 원소들을 오름차순 정렬.

  • n번째 원소를 찾는 것이 목적이므로 원본을 수정하며, 반환형은 void.

  • 두번째 인자인 nth는 정렬 후 위치하는 원소가 되며, 앞의 원소들은 모두 nth보다 작고, 뒤의 원소들은 모두 nth 보다 큼.

  • 다만 비교자 함수를 전달할 경우 오름차순이 아닌 내림차순 정렬을 수행할 수 있음. (다른 비교도 가능)

// until C++20
template< class RandomIt >
void nth_element( RandomIt first, RandomIt nth, RandomIt last );

// since C++20
template< class RandomIt >
constexpr void nth_element( RandomIt first, RandomIt nth, RandomIt last );

// since C++17
template< class ExecutionPolicy, class RandomIt >
void nth_element( ExecutionPolicy&& policy,
                  RandomIt first, RandomIt nth, RandomIt last )

// until C++20
template< class RandomIt, class Compare >
void nth_element( RandomIt first, RandomIt nth, RandomIt last, Compare comp );

// since C++20
template< class RandomIt, class Compare >
constexpr void nth_element( RandomIt first, RandomIt nth, RandomIt last,
                            Compare comp );

// since C++17
template< class ExecutionPolicy, class RandomIt, class Compare >
void nth_element( ExecutionPolicy&& policy, 
                  RandomIt first, RandomIt nth, RandomIt last, Compare comp );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int main() {
    vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3};

    nth_element(v.begin(), v.begin() + v.size()/2, v.end());
    cout << "The median is " << v[v.size()/2] << endl;

    nth_element(v.begin(), v.begin()+1, v.end(), greater<int>());
    cout << "The second largest element is " << v[1] << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
The median is 5
The second largest element is 7
 */

파티셔닝 알고리즘 (Partitioning Algorithm)

• partition 범위 내 원소들을 주어진 함수에 의해 두 그룹으로 나눔.

  • partition_copy 두 그룹으로 나뉘어진 원소들을 복사. (원본 유지)

// until C++11
template< class BidirIt, class UnaryPredicate >
BidirIt partition( BidirIt first, BidirIt last, UnaryPredicate p );

// since C++11 until C++20
template< class ForwardIt, class UnaryPredicate >
ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPredicate p );

template< class InputIt, class OutputIt1, class OutputIt2, class UnaryPredicate >
std::pair<OutputIt1, OutputIt2>
     partition_copy( InputIt first, InputIt last,
                     OutputIt1 d_first_true, OutputIt2 d_first_false,
                     UnaryPredicate p );

// since C++20
template< class ForwardIt, class UnaryPredicate >
constexpr ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPredicate p );

template< class InputIt, class OutputIt1, class OutputIt2, class UnaryPredicate >
constexpr std::pair<OutputIt1, OutputIt2>
               partition_copy( InputIt first, InputIt last,
                               OutputIt1 d_first_true, OutputIt2 d_first_false,
                               UnaryPredicate p );

// since C++17
template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate >
ForwardIt partition( ExecutionPolicy&& policy, 
                     ForwardIt first, ForwardIt last, UnaryPredicate p );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3,
          class UnaryPredicate >
std::pair<ForwardIt2, ForwardIt3>
     partition_copy( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
                     ForwardIt2 d_first_true, ForwardIt3 d_first_false,
                     UnaryPredicate p );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <forward_list>
#include <algorithm>
#include <iterator>
using namespace std;

template <class ForwardIt>
 void quicksort(ForwardIt first, ForwardIt last) {
    if(first == last) return;
    auto pivot = *next(first, distance(first,last)/2);
    ForwardIt middle1 = partition(
            first, last, [pivot](const auto& em){ return em < pivot; });
    ForwardIt middle2 = partition(
            middle1, last, [pivot](const auto& em){ return !(pivot < em); });
    quicksort(first, middle1);
    quicksort(middle2, last);
}

int main() {
    vector<int> v = {0,1,2,3,4,5,6,7,8,9};
    cout << "Original vector:\n    ";
    for(int elem : v) cout << elem << ' ';

    auto it = partition(v.begin(), v.end(), [](int i){return i % 2 == 0;});

    cout << endl << "Partitioned vector:\n    ";
    copy(begin(v), it, ostream_iterator<int>(cout, " "));
    cout << " * ";
    copy(it, end(v), ostream_iterator<int>(cout, " "));

    forward_list<int> fl = {1, 30, -4, 3, 5, -4, 1, 6, -8, 2, -5, 64, 1, 92};
    cout << endl << "Unsorted list:\n    ";
    for(int n : fl) cout << n << ' ';
    cout << endl;

    quicksort(begin(fl), end(fl));
    cout << "Sorted using quicksort:\n    ";
    for(int fi : fl) cout << fi << ' ';
    cout << endl;

    cout << "Call partition_copy():" << endl;

    int arr [10] = {1,2,3,4,5,6,7,8,9,10};
    int true_arr [5] = {0};
    int false_arr [5] = {0};

    cout << "Before: ";
    for (int n : arr) cout << n << " ";
    cout << endl;

    partition_copy(begin(arr), end(arr), begin(true_arr), begin(false_arr),
                   [] (int i) {return i > 5;});

    cout << "true_arr: ";
    for (int x : true_arr) cout << x << ' ';
    cout << endl;

    cout << "false_arr: ";
    for (int x : false_arr) cout << x << ' ';
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++14
$ ./a.out
Original vector:
    0 1 2 3 4 5 6 7 8 9
Partitioned vector:
    0 8 2 6 4  * 5 3 7 1 9
Unsorted list:
    1 30 -4 3 5 -4 1 6 -8 2 -5 64 1 92
Sorted using quicksort:
    -8 -5 -4 -4 1 1 1 2 3 5 6 30 64 92
Call partition_copy():
Before: 1 2 3 4 5 6 7 8 9 10
true_arr: 6 7 8 9 10
false_arr: 1 2 3 4 5
 */

• is_partition 두 그룹이 주어진 함수에 의해 나뉘어져 있으면 true, 그렇지 않으면 false 반환.

// since C++11 until C++20
template< class InputIt, class UnaryPredicate >
bool is_partitioned( InputIt first, InputIt last, UnaryPredicate p );

// since C++20
template< class InputIt, class UnaryPredicate >
constexpr bool is_partitioned( InputIt first, InputIt last, UnaryPredicate p );

// since C++17
template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate >
bool is_partitioned( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                     UnaryPredicate p );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <array>
#include <algorithm>
using namespace std;

int main() {
    array<int, 9> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    auto is_even = [](int i){ return i % 2 == 0; };
    cout.setf(ios_base::boolalpha);
    cout << is_partitioned(v.begin(), v.end(), is_even) << ' ';

    partition(v.begin(), v.end(), is_even);
    cout << is_partitioned(v.begin(), v.end(), is_even) << ' ';

    reverse(v.begin(), v.end());
    cout << is_partitioned(v.cbegin(), v.cend(), is_even) << ' ';
    cout << is_partitioned(v.crbegin(), v.crend(), is_even) << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
false true false true
 */

• stable_partition 상대적 순서를 유지한 상태로 두 그룹으로 나눔.

template< class BidirIt, class UnaryPredicate >
BidirIt stable_partition( BidirIt first, BidirIt last, UnaryPredicate p );

// since C++17
template< class ExecutionPolicy, class BidirIt, class UnaryPredicate >
BidirIt stable_partition( ExecutionPolicy&& policy, BidirIt first, BidirIt last,
                          UnaryPredicate p );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> v{0, 0, 3, 0, 2, 4, 5, 0, 7};
    stable_partition(v.begin(), v.end(), [](int n){return n>0;});
    for (int n : v) cout << n << ' ';
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
3 2 4 5 7 0 0 0 0
 */

• partition_point 두 그룹으로 나뉜 상태에서 첫번째 파티션이 끝나는 위치의 iterator를 반환.

// since C++11 until C++20
template< class ForwardIt, class UnaryPredicate >
ForwardIt partition_point( ForwardIt first, ForwardIt last, UnaryPredicate p );

// since C++20
template< class ForwardIt, class UnaryPredicate >
constexpr ForwardIt partition_point( ForwardIt first, ForwardIt last,
                                     UnaryPredicate p );

// ----------------------------------------------------------------------------------
#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>
using namespace std;

int main() {
    array<int, 9> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    auto is_even = [](int i){ return i % 2 == 0; };
    partition(v.begin(), v.end(), is_even);

    auto p = partition_point(v.begin(), v.end(), is_even);

    cout << "Before partition:\n    ";
    copy(v.begin(), p, ostream_iterator<int>(cout, " "));
    cout << endl << "After partition:\n    ";
    copy(p, v.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
Before partition:
    8 2 6 4
After partition:
    5 3 7 1 9
 */