Сортировка и разделение (серия «114 алгоритмов C++»)

Добро пожаловать во вторую статью цикла. Стандартная библиотека C++ предлагает набор высокопроизводительных алгоритмов сортировки, частичной сортировки, разделения и выбора.

Сегодня мы начнем с std::sort, обсудим лексикографическое сравнение и оператор spaceship (космический корабль) из C++20. Затем мы пройдемся по всем вариантам сортировок, частичным сортировкам и алгоритмам разделения, предлагаемым в стандартной библиотеке.

sort

Неудивительно, что основным алгоритмом сортировки является std::sort.

Хотя фактическая реализация std::sort может отличаться (обычно это интроспективная сортировка (introsort)), она гарантированно будет выполнять O(n*logn) сравнений (начиная с C++11). В результате она работает только с диапазонами произвольного доступа. Это означает, что мы не можем использовать std::sort с std::list, который предоставляет метод sort со сложностью O(n*logn).

{
    std::vector<int> data = {9, 1, 8, 2, 7, 3, 6, 4, 5};
    std::sort(data.begin(), data.end());
    // 1, 2, 3, 4, 5, 6, 7, 8, 9
}
{
    std::list<int> data = {9, 1, 8, 2, 7, 3, 6, 4, 5};
    //std::sort(data.begin(), data.end()); // не компилируется
    data.sort();
    // 1, 2, 3, 4, 5, 6, 7, 8, 9
}

В C++20 мы можем использовать проекции для сортировки по методу или члену данных:

struct Account {
    double value();
};

std::vector<Account> fetch_accounts();

int main() {
    std::vector<Account> data = fetch_accounts();
    std::ranges::sort(data, std::greater<>(), &Account::value);
}

Здесь мы сортируем счета по их вычисленной стоимости в порядке убывания (технически в порядке невозрастания). std::greater<> – это специализация std::greater в C++14, основанная на выводе типа для определения типов параметров. До C++14 вам нужно было указать тип (в данном случае std::greater<double>()).

Делаем ваш тип сравнимым

В примерах выше мы использовали std::sort для типов, которые изначально сравнимы в базовом языке, или использовали проекцию, чтобы сузить пользовательский тип до double. Однако иногда вы можете захотеть сделать сравнимым свой пользовательский тип.

Во-первых, вернемся к требованиям std::sort. Он ожидает strict_weak_ordering, что означает, что функтор сравнения (или оператор «меньше») должен быть

• антирефлексивным: f(a,a) = false,
• антисимметричным: f(a,b) = true => f(b, а) = false,
• и транзитивным: f(a,b) = true && f(b,c) = true => f(a,c) = true.

Если у вас нет специфичного для предметной области порядка для вашего конкретного типа данных, по умолчанию используется лексикографический порядок. Лексикографический порядок – это порядок, также обеспечиваемый стандартными контейнерами.

В C++20 с введением оператора космического корабля реализация сравнения для вашего типа стала намного проще:

struct Point {
    int x;
    int y;

    // лексикографическое «меньше чем», до C++20
    friend bool operator<(const Point& left, const Point& right) {
        if (left.x != right.x)
            return left.x < right.x;
        return left.y < right.y;
    }

    // версия лексикографического сравнения с космическим кораблем,
    // стандартная в C++20
    friend auto operator<=>(const Point&, const Point&) = default;

    // ручная реализация версии лексикографического сравнения
    // с космическим кораблем в C++20
    friend auto operator<=>(const Point& left, const Point& right) {
        if (left.x != right.x)
            return left.x <=> right.x;
        return left.y <=> right.y;
    }
};

Лексикографический порядок по умолчанию (строка 14) работает рекурсивно. Сначала он начинается с баз объектов, слева направо, сначала в глубину, а затем до нестатических членов в порядке объявления (обработка массивов поэлементно, слева направо).

Тип, возвращаемый оператором космического корабля, является общим типом категории сравнения для баз и элементов: strong_ordering, weak_ordering или partial_ordering.

lexicographical_compare, lexicographical_compare_three_way

Обсуждая лексикографическое сравнение, мы должны упомянуть о двух алгоритмах, предлагающих эту функциональность для диапазонов.

std::vector<int> range1{1, 2, 3}, range2{1, 3}, range3{1, 3, 1};

assert(std::lexicographical_compare(range1.begin(), range1.end(), 
                                    range2.begin(), range2.end()));
assert(std::lexicographical_compare(range2.begin(), range2.end(), 
                                    range3.begin(), range3.end()));

assert(range1 < range2); // то же, что и lexicographical_compare
assert(range2 < range3); // то же, что и lexicographical_compare

Как я уже упоминал, все стандартные контейнеры предлагают лексикографическое сравнение с помощью своих операторов сравнения (до C++20) или оператора космического корабля (начиная с C++20). Основное использование ручного вызова lexicographical_compare – это использование массивов в стиле C или, когда вы хотите указать пользовательский компаратор элементов:

int x[] = {1, 2, 3}, y[] = {1, 4}; // только для демонстрации, используйте std::array

assert(std::lexicographical_compare(&x[0], &x[3], &y[0], &y[2]));

std::vector<std::string> names1{"Zod", "Celeste"}, names2{"Adam", "Maria"};

assert(std::ranges::lexicographical_compare(names1, names2, 
        [](const std::string& left, const std::string& right) {
            return left.length() < right.length();
        }));

lexicographical_compare_three_way – это оператор космического корабля, эквивалентный lexicographical_compare. Он возвращает один из типов strong_ordering, weak_ordering или partial_ordering (в зависимости от предоставленного функтора).

stable_sort

std::sort может свободно переупорядочивать эквивалентные элементы, что может быть нежелательно при повторной сортировке уже отсортированного диапазона. std::stable_sort обеспечивает дополнительную гарантию сохранения относительного порядка одинаковых элементов. Если доступна дополнительная память, то stable_sort остается O(n*logn). Однако если ему не удастся выделить память, он ухудшится до алгоритма O(n*logn*logn).

Хотя сортировка stable_sort не особенно полезна, когда мы уже сортируем по каждому аспекту типа (например, полагаясь на лексикографическое сравнение), она часто возникает, когда сортировка основана на вводе пользователя (например, повторная сортировка по столбцу в пользовательском интерфейсе).

struct Record {
    std::string label;
    int rank;
};

std::vector<Record> data {{"q", 1}, {"f", 1}, {"c", 2}, {"a", 1}, {"d", 3}};

std::ranges::stable_sort(data, {}, &Record::label);    
std::ranges::stable_sort(data, {}, &Record::rank);
// Гарантированный порядок: a-1, f-1, q-1, c-2, d-3

is_sorted, is_sorted_until

Чтобы проверить, отсортирован ли диапазон в соответствии с предоставленным предикатом, мы можем использовать is_sorted. Предикат по умолчанию – std::less.

std::vector<int> data1{1, 2, 3, 4, 5}, data2{5, 4, 3, 2, 1};

assert(std::is_sorted(data1.begin(), data1.end()));
assert(std::ranges::is_sorted(data2, std::greater<>()));

В качестве альтернативы мы можем использовать is_sorted_until, который возвращает итератор к первому неупорядоченному элементу.

std::vector<int> data{1, 5, 9, 2, 4, 6};
auto it = std::is_sorted_until(data.begin(), data.end());
// *it == 2

partial_sort, partial_sort_copy

Часто нас интересует только верхняя пара элементов в порядке сортировки, что и обеспечивают алгоритмы частичной сортировки. Преимущество использования частичной сортировки заключается в более быстром выполнении – примерно O(n*logk), где k – количество отсортированных элементов.

Поддиапазон для сортировки указывается с помощью среднего итератора с семантикой [begin, middle), представляющей отсортированную часть диапазона.

std::vector<int> data{9, 8, 7, 6, 5, 4, 3, 2, 1};
std::partial_sort(data.begin(), data.begin()+3, data.end());
// 1, 2, 3, -неопределенный порядок-

std::ranges::partial_sort(data, data.begin()+3, std::greater<>());
// 9, 8, 7, -неопределенный порядок-

Вариант partial_sort, выгодный при работе с неизменяемыми исходными данными, – partial_sort_copy.

Этот вариант требует только, чтобы диапазон назначения был изменяемым и имел произвольный доступ.

struct ScoreRecord {
    std::string display;
    uint16_t score;
};

const std::vector<ScoreRecord>& get_records();

int main() {
    std::vector<ScoreRecord> top10(10, ScoreRecord{});
    std::ranges::partial_sort_copy(get_records(), top10, 
        std::greater<>(), &ScoreRecord::score, &ScoreRecord::score);
    // обработка 10 верхних элементов
}

partition, stable_partition, partition_copy, is_partitioned

Алгоритмы разделения «разбивают» диапазон на два поддиапазона. В первый идут все элементы, удовлетворяющие заданному предикату, а во второй – все элементы, не удовлетворяющие предикату. Примечательно, что трехстороннее разделение является основным строительным блоком QuickSort.

Если нас интересует просто группировка элементов по определенному свойству, std::partition будет подходящим решением.

struct ExamResult {
    std::string student_name;
    uint16_t score;
};

std::vector<ExamResult> get_results();

int main() {
    std::vector<ExamResult> results = get_results();
  
    auto pp = std::partition(results.begin(), results.end(), 
        [limit = 49](const ExamResult& result) {
            return result.score >= limit;
        });
 
    for (auto it = results.begin(); it != pp; it++) {
        // обработка студентов с хорошей отметкой
    }
    for (auto it = pp; it != results.end(); it++) {
        // обработка студентов с неудовлетворительной отметкой
     }
}

Здесь мы делим результаты экзамена на сдавших и не сдавших студентов. Алгоритм разбиения возвращает точку разбиения (строка 11). Мы можем использовать эту точку раздела для обработки двух частей диапазона (строки 16 и 19).

По аналогии с is_sorted, мы можем проверить, разделен ли диапазон (в соответствии с заданным предикатом), используя is_partitioned.

std::vector<int> data{2, 4, 6, 1, 3, 5};
auto is_even = [](int v) { return v % 2 == 0; };
assert(std::ranges::is_partitioned(data, is_even));

Стабильное разделение гарантирует, что оно не изменит относительный порядок элементов.

struct Item {
    std::string label;
    bool is_selected() const;
};

std::vector<Item> widget = get_widget();
std::ranges::stable_partition(widget, std::identity{}, &Item::is_selected);
// выбранные элементы перемещаются в начало диапазона

Этот код может сбивать с толку, потому что мы используем std::identity вместо предиката. Однако обратите внимание, что результатом проекции является логическое значение. Следовательно, всё, что мы требуем от предиката, – это передать это значение.

Наконец, partition_copy не будет переупорядочивать входной диапазон, а вместо этого скопирует два раздела в предоставленные выходные диапазоны.

std::vector<int> data{2, 4, 6, 1, 3, 5};
auto is_even = [](int v) { return v % 2 == 0; };

std::vector<int> even, odd;
std::partition_copy(data.begin(), data.end(),
    std::back_inserter(even),
    std::back_inserter(odd),
    is_even);

// even == {2, 4, 6}
// odd == {1, 3, 5}

Мы используем адаптер back_inserter для заполнения двух векторов без необходимости предварительного выделения достаточной емкости (адаптер внутри вызывает push_back).

nth_element

Иногда нам нужно выбрать из диапазона только один конкретный элемент (например, при выборе медианы). Сортировка (даже частичная) может оказаться излишней из-за сложности O(n*logn). Для сложности O(n) нам нужно использовать алгоритм выбора, и nth_element – один из таких алгоритмов.

Выбранный элемент указывается с помощью среднего итератора. Алгоритм переупорядочивает диапазон так, чтобы этот элемент был в отсортированной позиции. Более того, алгоритм слабо разбивает диапазон (каждый элемент до середины ≤ каждого элемента после середины).

std::vector<int> data{9, 1, 8, 2, 7, 3, 6, 4, 5};
std::nth_element(data.begin(), data.begin()+4, data.end());
// data[4] == 5

std::nth_element(data.begin(), data.begin()+7, data.end(), std::greater<>());
// data[7] == 2

В зависимости от вашего варианта использования, partial_sort иногда может быть быстрее, чем nth_element, несмотря на худшую теоретическую сложность.

Стандартная библиотека C: qsort

Поскольку стандартная библиотека C является частью стандартной библиотеки C++, у нас также есть доступ к qsort.

int data[] = {2, 1, 9, -1, 7, -8};
int size = sizeof data / sizeof(int);

qsort(data, size, sizeof(int), [](const void* left, const void* right){
    int vl = *(const int*)left;
    int vr = *(const int*)right;

    if (vl < vr) return -1;
    if (vl > vr) return 1;
    return 0;
});

// -8, -1, 1, 2, 7, 9

Я бы настоятельно рекомендовал избегать qsort, так как std::sort и std::ranges::sort должны лучше подходить в любой ситуации. Более того, qsort допустим только для тривиально копируемых типов, и они будут правильно оптимизированы для операций memcpy даже при использовании std::sort (при желании).

int data[] = {2, 1, 9, -1, 7, -8};
int size = sizeof data / sizeof(int);

std::sort(&data[0], &data[size], std::less<>());
// -8, -1, 1, 2, 7, 9

Спасибо за чтение

Следующая статья будет посвящена алгоритмам, работающим с отсортированными или секционированными диапазонами.

Теги