Бредятинка родилась в ходе трёпа-охаивания разных алгоритмов сортировки.
Насчёт того, что свойства стабильности и упорядоченности ортогональны.
Если это так, то почему бы не сделать алгоритм, обратный сортировке (т.е. random_shuffle), но при этом стабильный.
То есть, чтоб выполнялось stable_sort(stable_shuffle(xs)) == stable_sort(xs)
Ещё одно требование — это равномерность, т.е. чтобы генерируемые перестановки были равновероятны.
Навскидку, я знаю тупой алгоритм с квадратной сложностью. Кто лучше?
Здравствуйте, Кодт, Вы писали:
К>Лучше сделать по-другому. К>1) стабильно сортируем — точнее, стабильно группируем одинаковые элементы вместе (это более слабое требование, чем сортировка) К>2) каждой серии одинаковых элементов навешиваем возрастающую случайную последовательность чисел из диапазона [0..M), где M — достаточно большое число К>(как минимум, оно должно быть не меньше мощности самой большой серии одинаковых элементов; но можно взять за M размер всего массива или даже INT_MAX) К>3) сортируем по этому ключу (нестабильно)
К>Основная сложность тут состоит в том, чтобы обеспечить (доказать) равномерность перемешивания.
Если уж делать (1), а потом развешивать тэги, то есть иметь по доп. int'у на ячейку, то проще сделать по-другому!
Просто раздаём случайные тэги ВСЕМ элементам массива, а потом на тэгах, соответствующим плато (отрезкам одинаковых исходных объектов) проводим сортировку тэгов. Ну и потом сортируем уже весь массив по тэгам...
По асимптоте получим те же O( N lnN ), в расходе памяти те же int на элемент, а перестановка гарантированно такая, какую хотим сгенерить...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Т.е. тебе нужен random_shuffle который бы сохранял порядок элементов с одинаковыми значеними? Чем плохо собрать их в ведра (бакеты), а потом каждое ведро раскидать равномерно по массиву?
К>Если это так, то почему бы не сделать алгоритм, обратный сортировке (т.е. random_shuffle), но при этом стабильный. К>То есть, чтоб выполнялось stable_sort(stable_shuffle(xs)) == stable_sort(xs) К>Ещё одно требование — это равномерность, т.е. чтобы генерируемые перестановки были равновероятны. К>Навскидку, я знаю тупой алгоритм с квадратной сложностью. Кто лучше?
вешаем на каждый объект два тега:
(1) рандомный тег (64 или 128-битный).
(2) исходный индекс объекта в массиве.
Достаточно очевидно, что полученные тройки <Object, RandomTag, IndexTag> можно легко упорядочит таким образом, чтобы при сортировке сохранялась "стабильность", при этом остальные элементы перетасовывались рандомно.
Здравствуйте, ·, Вы писали:
·>А если тупо подобрать какой-нибудь алгоритм стабильной сортировки и подсунуть ему функцию сравнения: ·>compare(x, y) { x == y ? 0 : randomMinusOneOrPlusOne() }
Если сортировка удовлетворяет очевидному требованию, что в упорядоченном массиве одинаковые элементы идут подряд, а этот компаратор утверждает, что одинаковые по значению элементы одинаковы, — то в результате, в лучшем случае, мы получим случайную перестановку серий одинаковых элементов.
Это очень узкое подмножество случайных перестановок
Кроме того, "не падает" != "работает". Нарушение транзитивности обрушивает много чего в свойствах алгоритма.
Возьмём то же слияние. Допустим, у нас массив [a0 a1 a2 b3 b4 c5 c6 c7] (буква — значение, цифра — порядковый номер).\
Разбили пополам, [a0 a1 a2 b3], [b4 c5 c6 c7]
Случайно перетасовали каждую половинку, — допустим, что перетасовка оказалась тривиальной.
Теперь выполняем слияние.
1) a0 против b4 — поскольку randomMinusOneOrPlusOne(), то выбрали b4.
2) продолжаем слияние дальше... но увы, порядок уже нарушен, потому что b3 заведомо окажется позади.
Здравствуйте, С3141566=Z, Вы писали:
СZ>Т.е. тебе нужен random_shuffle который бы сохранял порядок элементов с одинаковыми значеними? Чем плохо собрать их в ведра (бакеты), а потом каждое ведро раскидать равномерно по массиву?
Здравствуйте, watchyourinfo, Вы писали:
W>Достаточно очевидно, что полученные тройки <Object, RandomTag, IndexTag> можно легко упорядочит таким образом, чтобы при сортировке сохранялась "стабильность", при этом остальные элементы перетасовывались рандомно.
Вообще неочевидно.
Поле Index уникально, поле Random — может быть уникально (ничего нельзя сказать).
Поэтому лексикографическое сравнение по ключу
— <Index,...> — эквивалентно сравнению по <Index>, сортировка приведёт к тривиальной перестановке
— <Random,...> — с большой вероятностью (если не налетим на коллизии случайного ключа) даст нестабильное random_shuffle
— <Object,Index,...> — стабильная сортировка в чистом виде
— <Object,Random,...> — нестабильная (я бы сказал, дестабилизирующая) сортировка
К>1. Дополнительная память.
Так вроде не было ничего про нее? К>2. Какое время?
В бакеты собрать O(N*log(N)), раскидать считать надо. cкорее всего будет O(M * log(M) ).
Время, если рандомные теги не проблема, то O(N*lgN) очевидно.
Если быть педантичными, то нужно учитывать вероятность коллизий рандомных тегов (и что-то предпринимать в этом случае). А тогда worst case убегает далеко. То есть тут среднюю сложность нужно считать, а не worst case.
К>Вообще неочевидно.
К>Поле Index уникально, поле Random — может быть уникально (ничего нельзя сказать). К>Поэтому лексикографическое сравнение по ключу К>- <Index,...> — эквивалентно сравнению по <Index>, сортировка приведёт к тривиальной перестановке К>- <Random,...> — с большой вероятностью (если не налетим на коллизии случайного ключа) даст нестабильное random_shuffle К>- <Object,Index,...> — стабильная сортировка в чистом виде К>- <Object,Random,...> — нестабильная (я бы сказал, дестабилизирующая) сортировка
рандомные теги мы считаем уникальными. Что очевидно достигается на практике, битность тега увеличиваем, если что.
Лексикографическое сравнение, конечно, здест не годится.
Здравствуйте, watchyourinfo, Вы писали:
W>Если быть педантичными, то нужно учитывать вероятность коллизий рандомных тегов (и что-то предпринимать в этом случае). А тогда worst case убегает далеко. То есть тут среднюю сложность нужно считать, а не worst case.
Можно и худший случай оценить.
Опять же, какой случай будет худшим? Набор из элементов, принимающих одно значение, или поровну два значения, или что-нибудь экзотическое — N^2 элементов, принимающих N разных значений?
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, С3141566=Z, Вы писали:
К>>>1. Дополнительная память. СZ>>Так вроде не было ничего про нее?
К>Приветствуются любые варианты. Можно с дополнительной памятью, можно без.
Ну с дополнительной памятью O(N). Записываем все свободные ячейки в массиве. Берем очередное ведро (случайно или не случайно хороший вопрос) размером m. Берем фишера за йетса (толи O(m) толи O(m) * (1- экспоненциальная шняжка), вычеркиваем m свободных ячеек. В этим m ячеек суем содержимое ведра. C остальными работаем начиная с первого шага. Если ты жулик, то посчитаешь общее время -- O(n) (т.к. хэш таблица) + O(m)*(n/m), если нет, то O(n*log(n))
К>Навскидку, я знаю тупой алгоритм с квадратной сложностью. Кто лучше?
Тупой алгоритм без доп.памяти выглядит так
vector<T> data;
int const n = data.size();
// группируем элементы, чтобы одинаковые шли подряд
stable_sort(data.begin(), data.end());
// (можно не сортировать, но это будет многословно)for(auto it = data.begin();
it != data.end();
it = stable_partition(it+1,data.end(),[it](T const& x) { return x==*it; })
)
{}
// на итераторах лень переписывать, извинитеint n = data.size();
for(int m = n; m >= 0; --m) {
// предусловие: [0..m) ещё не перемешаны, и сгруппированы
// [m..n) уже перемешаны, их трогать нельзяint i = rand() % m; // i <- [0..m)while(i+1 < m && data[i] == data[i+1]) ++i; // находим последний элемент в группе
// переносим data[i] в начало замороженной зоны
rotate(data.begin()+i, data.begin()+i+1, data.begin()+m);
}
Если сплавить фазы группировки и перетасовки, можем выбросить группировку, и получить такую схему
for(i = 0; i < n; ++i) {
// [0;i) перетасовано и заморожено, [i;n) - расходуетсяint r = i + rand() % (n-i); // r <- [i;n)
iterator q = find(data.begin()+i, data.begin()+r+1, data[r]); // находим первый элемент, равный случайно выбранному
rotate(data.begin()+i, q, q+1); // переносим его в хвост замороженной зоны
}
Она тоже квадратная (хотя бы в силу того, что делаем вставку).
Здравствуйте, Кодт, Вы писали:
К> Бредятинка родилась в ходе трёпа-охаивания разных алгоритмов сортировки.
А если тупо подобрать какой-нибудь алгоритм стабильной сортировки и подсунуть ему функцию сравнения:
compare(x, y) { x == y ? 0 : randomMinusOneOrPlusOne() }
?
Как подбирать алгоритм не знаю.. Но как минимум какой-нибудь из тех, который не падает от нетранзитивного сравнения. Merge sort вроде должен прокатить.
К>Тогда докажи, что этот порядок тотальный. В чём я лично сомневаюсь. К>Да собственно, вот тебе контрпример.
согласен, я обосрался.
Тогда так:
(1) стабильно сортируем;
(2) за один проход навешиваем на каждый элемент RandomTag, но при этом навешиваем один и тот же тэг на одинаковые элементы (это легко так как они уже сгруппированы после шага 1);
(3) стабильно сортируем по тегу
Здравствуйте, watchyourinfo, Вы писали:
W>(1) стабильно сортируем; W>(2) за один проход навешиваем на каждый элемент RandomTag, но при этом навешиваем один и тот же тэг на одинаковые элементы (это легко так как они уже сгруппированы после шага 1); W>(3) стабильно сортируем по тегу
Твоя процедура состоит в том, что ты строишь случайную биективную (биективную ли?) функцию f из множеством фактических значений исходного типа элементов на, например, подмножество целых чисел. И сортируешь по ключу f(x).
Хоть стабильно, хоть нестабильно, но одинаковые элементы получают одинаковые ключи (а разные получают разные? как это обеспечить?) и после сортировки оказываются рядом.
Лучше сделать по-другому.
1) стабильно сортируем — точнее, стабильно группируем одинаковые элементы вместе (это более слабое требование, чем сортировка)
2) каждой серии одинаковых элементов навешиваем возрастающую случайную последовательность чисел из диапазона [0..M), где M — достаточно большое число
(как минимум, оно должно быть не меньше мощности самой большой серии одинаковых элементов; но можно взять за M размер всего массива или даже INT_MAX)
3) сортируем по этому ключу (нестабильно)
Основная сложность тут состоит в том, чтобы обеспечить (доказать) равномерность перемешивания.