Какая часть стандартной библиотеки STL наиболее употребима программистами C++? Скорее всего - это контейнеры.

Контейнеры имеют много специализированных методов, которым отдается предпочтение перед алгоритмами из STL. Эти методы "знают" внутреннее устройство контейнера и поэтому работают более эффективно, чем алгоритмы. 

Но как часто мы прибегаем к алгоритмам из стандартной библиотеки STL? Для решения какой-либо задачи многие из нас, не задумываясь, напишут нетривиальный вложенный цикл в стиле C, чем попробуют подыскать алгоритм, который сделает всё тоже самое. 

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

В данной статье мы попытаемся применить некоторые алгоритмы из STL для решения задачи сортировки. При этом будем стараться как можно меньше использовать циклы. Да и вообще, постараемся как можно меньше писать кода. Сами алгоритмы сортировки подробно рассматриваться не будут. Нам нужна лишь интересная постановка задачи, чтобы продемонстрировать её решение с помощью алгоритмов STL. К тому же, Вы всегда сможете найти альтернативные решения (без алгоритмов из STL), и сравнить их с предложенными в статье.

С чего начать...?

Нам предстоит сортировать элементы контейнеров, а значит понадобится функция, которая будет выводить элементы на экран. По идее обычного цикла было бы достаточно, но мы твердо решили по-возможности использовать алгоритмы. Поэтому запишем функцию print так:

Данный способ вывода содержимого контейнера часто можно встретить в книгах по C++. Я нахожу его более удобным, чем аналогичный вариант с циклом. Хотя, возможно, это субъективное восприятие. Вот здесь (cppreference.com), в примерах, также очень часто используют такой вариант вывода. Код простой, поэтому не станем его подробно разъяснять. Главная роль здесь у алгоритма std::copy и особого итератора std::ostream_iterator, который записывает присвоенные значения в поток вывода.

Сортировка пузырьком, классика жанра

Данный алгоритм сортировки очень популярен. Его знает каждый студент, как пример неэффективного варианта сортировки. Алгоритм сортировки пузырьком Вам наверняка знаком, поэтому сразу предложим реализацию:

Очень простая и понятная реализация. Это тот случай, когда использование циклов оказывается наиболее удобным вариантом. Обратите внимание на std::iter_swap - это простая функция, предназначенная для обмена значений, на которые ссылаются два итератора. Кстати, итераторы, передаваемые в std::iter_swap, не обязаны иметь одинаковый тип.

Этот пример нам нужен, чтобы "разогреться". Переходим к сортировке выбором.

Сортировка выбором, что может быть проще

Принцип алгоритма прост: находим элемент с минимальным значением на интервале от 1-го элемента до n-го (последнего) элемента и меняем его местами с первым элементом. На втором шаге находим элемент с минимальным значением на интервале от 2-го до n-го элемента и меняем его местами со вторым элементом. И так далее для всех элементов до n-1-го.

Этот алгоритм сортировки может быть основан на использовании вложенных циклов, как в предыдущем примере с "пузырьком". Но пришло время задействовать алгоритмы. Вот пример очень простой реализации сортировки выбором:

Алгоритм std::min_element возвращает позицию минимального элемента из указанного диапазона. Этот алгоритм избавляет нас от необходимости писать второй цикл и, как следствие, упрощает реализацию. Также мы применили уже известный нам std::iter_swap.

Посмотрите в интернете другие варианты реализации сортировки выбором, и Вы увидете, на сколько грустно живется тем, кто забывает про алгоритмы из STL. 

В данном примере мы комбинируем несколько алгоритмов, чтобы добиться нужной функциональности. Рассмотрим более интересный случай объединения алгоритмов.

Сортировка вставками, третья и последняя из простых

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

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

Две строчки кода... Этот замечательный пример я нашел в этой статье. В ней же подробно и с картинками рассказывается, как это работает. Не стану повторять текст той статьи, а только быстро опишу каждый из примененных алгоритмов:

Алгоритм std::upper_bound(begin, end, value) возвращает позицию последнего элемента, который превышает значение value. Это последняя позиция, в которую можно вставить элемент со значением value без нарушения порядка элементов в диапазоне [begin, end). std::upper_bound помогает нам определить куда же нужно поместить очередной элемент в уже отсортированной части контейнера. 

Алгоритм std::rotate(begin, middle, end), выполняет циклическую перестановку элементов в диапазоне [beg, end) так, что после вызова *middle становится первым элементом. Этот алгоритм обеспечивает смещение уже отсортированных элементов во время вставки нового элемента на свою позицию.

Вам всё это может показаться сложным, но всё дело в том, что к алгоритмам STL просто нужно привыкнуть и понять, что они делают. Поверьте, сложно записать этот алгоритм сортировки еще более короче и понятнее, какой бы язык программирования Вы не выбрали.

Сортировка Шелла

Процитируем Википедию: алгоритм сортировки Шелла, является усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными "грубыми" проходами.

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

Вот и всё! Удивительно то, что дополнительный цикл на практике, не ухудшает, а наоборот, улучшает эффективность данного алгоритма по сравнению с обычной сортировкой вставками!

Пора уже перейти к алгоритмам сортировки, основанным на принципе "разделяй и властвуй". Мы будем и дальше активно применять алгоритмы из STL. И первой на очереди у нас сортировка слиянием.

Сортировка слиянием

Краткое описание: последовательность элементов разделяется на равные или практически равные части, до тех пор, пока их размер не станет достаточно мал. Затем, каждая из таких частей сортируется отдельно. После чего уже упорядоченные части сливаются воедино, и получается решение исходной задачи.

Этот прекрасный алгоритм сортировки, как и предыдущие, реализован фактически в две строки. На этот раз авторство принадлежит мне. Сначала, как и положено, мы рекурсивно делим последовательность на несколько более мелких частей. Когда выполнится условие:

start != middle, мы перейдем к "сливанию воедино" всех полученных частей. Самой мелкой подзадачей, в нашем случае будет "слияние" двух элементов в одну отсортированную последовательность. Затем эту последовательность из двух упорядоченных элементов, мы объединим с другой такой же упорядоченной последовательностью, состоящей также из двух других соседних элементов. И так далее, пока не объединим все части воедино.

Вот картинка для наглядности:

Слияние смежных упорядоченных диапазонов (частей) за нас делает алгоритм std::inplace_merge. И это "львиная доля" всей работы. Нам, фактически, остается только правильно организовать рекурсивное разбиение диапазона на более мелкие составляющие. Здесь мы хитро задействовали возвращаемое значение. Но, главное, конечно, это std::inplace_merge.

Надеюсь, что мне уже удалось убедить Вас, освежить в памяти "арсенал" алгоритмов из STL.

Итак, мы подошли к последнему примеру в этой статье - это Быстрая сортировка.

И наконец... Быстрая сортировка

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

Я не стану описывать сам алгоритм, а перейду сразу к реализации. Сочиняя её (реализацию), я хотел записать весь алгоритм практически одним выражением. Другими словами - чтобы это была одна длинная строка кода. Это очень не практично и трудно для понимания, но то и дело я встречаю такие попытки в интернете на других языках. Например, здесь для Python, или здесь для Haskell. Видел еще примеры для языков Javascript и Lisp.

Справиться с задачей мне помог алгоритм std::partition, который используется для разделения элементов на две части по критерию сортировки. А дальше рекурсивные вызовы и снова хитрость с возвращаемым значением. Получилось довольно сложно, в духе примеров на функциональных языках. Но мы показали, что quicksort в одну строку возможен и на C++.

Вывод

Любой из примеров Вы сможете проверить примерно так:

Что хотелось бы сказать в итоге: многие жалуются, что стандартная библиотека C++ очень скудна, и в ней многого не хватает. Я с этим согласен, и разработчики стандарта согласны, так как планируют расширять библиотеку и дальше. Но, стоит задуматься чего мы хотим, чего нам не хватает? У нас есть отличный инструмент - алгоритмы STL, но из своей практики могу сказать, что ими часто пренебрегают. Я видел много кода, который можно было существенно упростить, если бы он был переписан с использованием алгоритмов из STL.


Р.S.: я, конечно, не забыл про алгоритм std::sort, который сейчас обычно основан на алгоритме сортировки Introsort, а не на быстрой сортировке. Но, сортировка была взята лишь как пример задачи, которую мы решали с помощью алгоритмов из STL. Вместо сортировки можно было бы взять другие интересные задачи. А про std::sort все и так знают. Поэтому я старался уделить внимание более "редким" алгоритмам STL.

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