Существует ли такая сортировка? (3 стр)

Читаю статью http://habrahabr.ru/post/205290/
Я тупой наверное. Ощущение, будто инглиш читаю.

> Два состояния массива будем называть эквивалентными, если элементы с одинаковыми ключами в них находятся в одинаковом порядке.

Например? Чтобы я не тратил на осмысление 5 секунд.

> Главная проблема устойчивых in-place сортировок — не потерять эту эквивалентность, или всегда уметь её восстановить.

Вот тут я подвис. Проблема - это значит, что устойчивые in-place сортировки так и норовят потерять эквивалентность и это вообще слабое место таких сортировок. Тогда значит, я неверно понял понятие "эквивалентность".
Ааааа, автор перепутал слова "цель" и "проблема"!

Ну итд.

TarasB
> Проблема
Скорее автор статьи имеет в виду problem.

9К720
вот я и говорю - автор нерусский

TarasB
Там они хотят не потерять свойство stable (стабильность или устойчивость). Stable - это когда элементы с одинаковыми ключами в отсортированном массиве будут идти в том же порядке, что и в изначальном. Например, есть массив строчек { "bc", "bb", "ab", "ca", "aa" } и ключ - первый символ (т.е. мы сравниваем строчки только по первому символу). Тогда стабильная сортировка всегда вернет { "ab", "aa", "bc", "bb", "ca" }, тогда как нестабильная может поменять местами "ab" и "aa", а так же "bc" и "bb" как ей захочется.

У них эквивалентность двух массивов - это когда элементы с одинаковыми ключами идут в них в одинаковом порядке. Например, эквивалентны любые два:
{ "bc", "bb", "ab", "ca", "aa" }, { "bc", "ab", "aa", "ca", "bb" }, { "ca", "ab", "bc", "aa", "bb" }, { "ab", "aa", "bc", "bb", "ca" }

Если в конце мы получим посорченный массив, эквивалентный исходному - значит сортировка стабильная.

UPD. "Проблема" там - это потому, что эквивалентность (для обеспечения стабильности) так просто не сохранить. Ученые несколько десятков лет рвали ж*пу чтобы найти решение, и вот типа оно найдено - и это разбор тех дохрена случаев, что указано в статье. Но если стабильность не нужна - тупо пользуемся обычным мержом на месте, описание которого 10 строчек в статье, на которую я привел ссылку чуть раньше.

R.I.P.
Я знаю, что такое "стабильная", но слово "проблема" меня повесило. Было бы там "задача" или "цель" - было бы понятнее. Такой текст читать не сильно легче, чем английский, так же запинаешься через слово.

Читаю дальше.

> Поскольку NKeys у нас порядка 2*sqrt(N),

почему?

FordPerfect
BFPRT крутой алгоритм, не знал о нем раньше.
Сначала подумал, что в первом сообщении имелся ввиду Quickselect, но потом разобрался подробнее.

Кстати, поздравляю, ваш select_pivot (который BFPRT) работает за O(n^2).
UPD. А не, разобрался чуть подробнее, вроде O(n) все-таки.

TarasB
> > Поскольку NKeys у нас порядка 2*sqrt(N),
>
> почему?
NKeys = K+S

А вообще да, статья довольно сумбурно написана, я сам не до конца в ней разобрался.
Потому я и написал чуть выше, что там "пипец":)

Читаю википедию
https://ru.wikipedia.org/wiki/Алгоритм_выбора

Что, почему? Я могу привести пример массива из 125 элементов, в котором алгоритм находит 27й.
По крайней мере, в понимании функции select_pivot из http://www.everfall.com/paste/id.php?b5dpp4i8zrlv

local_e не инициализируется до while

TarasB
На английской вики картинка лучше http://en.wikipedia.org/wiki/Median_of_medians
Там гарантируется, что те 30%, что выше-левее - <= пивота.
И те 30%, что ниже-правее - >= пивота.
Т.е. сам пивот где-то в 40% посередине.
На самом деле, чтобы этот пивот получить, надо честно рекурсивно запустить алгоритм для n/5 элементов, что в средней полосе.
Но если продолжить делать втупую (делить на группы по 5, брать в них серединки, остальное выкидывать и так пока не останется 1 элемент),
то получившийся в итоге пивот тоже будет гарантированно в какой-то середине (пока хз какой, надо на листочке посчитать).
Но если даже пивот будет обладать свойством, что 1% других элементов гарантированно <= него, и еще 1% >= него - quicksort будет работать за nlogn.
С бешеной константой, но nlogn.
В данном же случае, наверно, будет порядка 10-20% <= и 10-20% >= (сколько точно - хз, опять же, надо на листочке посчитать).

R.I.P.
я посчитал
для массива из 5^n элементов гарантируется что 3^n меньше
это соотношение можно сделать сколь угодно поганым и будет скорее квадрат логарифма

Я так скажу, есть сортировки работающие даже за O(n) на почти отсортированных коллекциях

Рекомендую Sleep Sort. Ее скорость зависит от наибольшего числа, а не от количества всех чисел.

TarasB
Значит оно таки к 0 с ростом n сходится...
Значит текущая реализация не nlogn
Значит надо написать честный Median of Medians) И еще без рекурсии. И еще на итераторах...