Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
soican
49 / 23 / 1
Регистрация: 16.11.2011
Сообщений: 329
Записей в блоге: 5
#1

sort и stable_sort - C++

28.07.2013, 22:44. Просмотров 1526. Ответов 2
Метки нет (Все метки)

читаю: stable_sort sorts the elements in the range [first,last) into ascending order, like sort, but stable_sort preserves the relative order of the elements with equivalent values.
непонятно: preserves the relative order of the elements with equivalent values. - относительный порядок эквивалентных значений - что это,как это?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.07.2013, 22:44
Здравствуйте! Я подобрал для вас темы с ответами на вопрос sort и stable_sort (C++):

Stable_sort и vector - C++
Есть вектор заполненый некоторыми словами. После использования stable_sort он сортируется по алфавиту. А как сделать чтобы он ещё и...

Не работает stable_sort - C++
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<vector> #include <iomanip> #include <algorithm> #include<string> ...

Stable_sort сортировка вектора по последнему символу - C++
Доброе время суток! Очень срочно помогите плз! void setText() { string number; FILE *file; char* file_name = "file.txt"; ...

sort() - C++
пожалуйста напишите несколько примеров,с перегруженными версиями sort? vector<int> vec; vec.push_back(100); vec.push_back(10); ...

Sort() - C++
Страуструп в своей книге вызывает эту функцию без всяких дополнительных библиотек. У меня же такая функция в стандартной библиотека...

list sort() - C++
Подскажите пожалуйста. Есть упрощенный класс class NOTE { public: char name; char surname; char phoneNumber; ...

2
Croessmah
Эксперт CЭксперт С++
13412 / 7563 / 855
Регистрация: 27.09.2012
Сообщений: 18,614
Записей в блоге: 3
Завершенные тесты: 1
28.07.2013, 22:52 #2
Цитата Сообщение от soican Посмотреть сообщение
относительный порядок эквивалентных значений - что это,как это?
Устойчивость.
То есть, например есть
4 1 2 1 3
после сортировки будет
1 1 2 3 4
вопрос, какая из двух единичек где теперь находится?
Устойчивые сортировки сохраняют порядок в котором идут эквивалентные элементы

Добавлено через 4 минуты
Википедия: Устойчивая сортировка
1
silent_1991
Эксперт С++
4984 / 3041 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
02.08.2013, 11:43 #3
На случай, если возникнет вопрос "а зачем это нужно, ведь элементы и так одинаковые?" С числами, символами, и другими данными, которые мы привыкли сравнивать, это действительно не нужно. Но возьмём ситуацию, когда сортируется массив элементов такого типа:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Foo
{
public:
    Foo(int a, int b):
    m_a(a), m_b(b)
    { }
    
    int get_a() const
    {
        return a;
    }
    
    int get_b() const
    {
        return b;
    }
private:
    int m_a;
    int m_b;
};
При этом оператор сравнения написан так:
C++
1
2
3
4
bool operator<(const Foo&x, const Foo& y)
{
    return x.get_a() < y.get_a();
}
Т.е. сравнение происходит только по одному из полей. Тогда при обычной сортировке в общем случае мы не можем предсказать, в каком порядке будут идти объекты в контейнере, можно только сказать, что они наверняка будут идти в порядке невозрастания (неубывания) поля m_a. Стабильная же сортировка гарантирует и то, что объекты будут упорядочены по полю m_a, и то, что их порядок по полю m_b не изменится относительно друг друга.
Поясню на примере. пусть есть такой контейнер:
[{4, 2}, {7, 1}, {4, 8}, {3, 3}, {7, 5}, {4, 4}, {3, 0}, {7, 2}]
Сравнение происходит по первому полю. В результате обычной сортировки мы можем получить как результат
[{3, 3}, {3, 0}, {4, 2}, {4, 8}, {4, 4}, {7, 1}, {7, 5}, {7, 2}]
так и результат
[{3, 0}, {3, 3}, {4, 2}, {4, 4}, {4, 8}, {7, 2}, {7, 5}, {7, 1}]
или даже
[{3, 0}, {3, 3}, {4, 4}, {4, 8}, {4, 2}, {7, 2}, {7, 5}, {7, 1}]
Т.е. контейнер действительно упорядочен, но только по первому полю. По второму полю он может быть перемешан как угодно, в зависимости от алгоритма сортировки.
Стабильная же сортировка всегда выдаст один и тот же результат:
[{3, 3}, {3, 0}, {4, 2}, {4, 8}, {4, 4}, {7, 1}, {7, 5}, {7, 2}]
Контейнер снова упорядочен по первому полю, но по второму полю элементы друг относительно друга расположены в том же порядке, в котором они находились друг относительно друга до сортировки.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.08.2013, 11:43
Привет! Вот еще темы с ответами:

Bubble sort - C++
Учу сортировки массивов, но не знаю, как обращаться к ним через процедуру! Процедура: int sort(int *A, int col){ int temp; for(...

std::sort - C++
Достоинства и недостатки делаю таблицу, достоинств и недостатков std::Sort. собственно, не нащёл нечего про это в википедии

Функция sort() - C++
Непонятно как работает функция из STL sort(). В нее третьим аргументом можно передавать некую функцию, предикату, которая возвращает...

Merge Sort - C++
написал реализацию Merge Sort но что то не так получилось))) помогите найти ошибку ) using namespace std; void Merge(int ,int ,int...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru