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

sort и stable_sort - C++

Восстановить пароль Регистрация
 
soican
49 / 23 / 1
Регистрация: 16.11.2011
Сообщений: 329
Записей в блоге: 5
28.07.2013, 22:44     sort и stable_sort #1
читаю: 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. - относительный порядок эквивалентных значений - что это,как это?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.07.2013, 22:44     sort и stable_sort
Посмотрите здесь:

C++ Алгоритм sort
C++ Stable_sort сортировка вектора по последнему символу
Strand Sort C++
C++ sort()
C++ Merge sort
C++ Sort()
C++ Stable_sort и vector
Не работает stable_sort C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11850 / 6829 / 773
Регистрация: 27.09.2012
Сообщений: 16,931
Записей в блоге: 2
Завершенные тесты: 1
28.07.2013, 22:52     sort и stable_sort #2
Цитата Сообщение от soican Посмотреть сообщение
относительный порядок эквивалентных значений - что это,как это?
Устойчивость.
То есть, например есть
4 1 2 1 3
после сортировки будет
1 1 2 3 4
вопрос, какая из двух единичек где теперь находится?
Устойчивые сортировки сохраняют порядок в котором идут эквивалентные элементы

Добавлено через 4 минуты
Википедия: Устойчивая сортировка
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
02.08.2013, 11:43     sort и stable_sort #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}]
Контейнер снова упорядочен по первому полю, но по второму полю элементы друг относительно друга расположены в том же порядке, в котором они находились друг относительно друга до сортировки.
Yandex
Объявления
02.08.2013, 11:43     sort и stable_sort
Ответ Создать тему
Опции темы

Текущее время: 17:47. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru