Функция stable_sort

Функция stable_sort сортирует элементы диапазона в порядке возрастания, но в отличие от обычной sort сохраняет относительный порядок элементов, которые считаются равными. В первый параметр мы передаем итератор на начало диапазона, а во второй - итератор на конец диапазона. Третьим необязательным параметром можно передать функцию сравнения, которая задает критерий сортировки. Устойчивость особенно важна при сортировке составных объектов, когда нужно сохранить исходный порядок элементов с одинаковым ключом.

Функция доступна после подключения заголовочного файла <algorithm>.

Синтаксис

stable_sort(first, last)
stable_sort(first, last, comp)

Пример

Давайте отсортируем вектор чисел по возрастанию:

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

int main()
{
	vector<int> vec = {5, 2, 4, 1, 3};
	stable_sort(vec.begin(), vec.end());
	
	for (int num : vec) {
		cout << num << " ";
	}
	cout << endl;
	return 0;
}

Результат выполнения кода:

1 2 3 4 5

Пример

Давайте отсортируем вектор чисел по убыванию, передав функцию сравнения:

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

int main()
{
	vector<int> vec = {5, 2, 4, 1, 3};
	stable_sort(vec.begin(), vec.end(), greater<int>());
	
	for (int num : vec) {
		cout << num << " ";
	}
	cout << endl;
	return 0;
}

Результат выполнения кода:

5 4 3 2 1

Пример

Давайте покажем главное отличие stable_sort от sort. Отсортируем вектор пар по первому элементу, где у нескольких пар первый элемент одинаков:

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

int main()
{
	vector<pair<int, string>> vec = {
		{2, "abcde"},
		{1, "12345"},
		{2, "hello"},
		{1, "world"}
	};
	
	stable_sort(vec.begin(), vec.end(),
		[](const pair<int, string>& a, const pair<int, string>& b) {
			return a.first < b.first;
		});
	
	for (const auto& p : vec) {
		cout << p.first << ":" << p.second << " ";
	}
	cout << endl;
	return 0;
}

Результат выполнения кода:

"1:12345 1:world 2:abcde 2:hello"

Как видно, пары с одинаковым первым элементом сохранили свой исходный относительный порядок: "12345" осталась перед "world", а "abcde" - перед "hello".

Смотрите также

функция sort,
которая сортирует диапазон без сохранения порядка
функция partial_sort,
которая сортирует только часть диапазона
функция stable_partition,
которая устойчиво разделяет элементы по условию
функция is_sorted,
которая проверяет, отсортирован ли диапазон