Тёмная тема
- 1 frag / 2 deaths
- Участник
TarasB
А что за сортировка слиянием без доп памяти, которая подходит под 2 и 3 и не подходит под 1?
А то я только знаю такую, что подходит под 1 и 2 и не подходит под 3.
Та, что я знаю, описана здесь: http://habrahabr.ru/post/138146/
R.I.P.
Я про неё же.
Чтобы порезать на куски размером sqrt(N) , итерировать можно и по единичке.
А вот из-за вставки последнего куска алгоритмическая сложность ухудшается до n*logn*logn. По крайней мере, в английской вики в статье про сортировки сказано про квадрат: http://en.wikipedia.org/wiki/Sorting_algorithm
TarasB
> трата памяти на стек не считается вообще
Чего это вдруг? Насколько я помню любой цикл можно заменить рекурсией, иными словами можно переписать алгоритм выделяющий дополнительный массив в рекурсивный вид. От этого алгоритм работать за константную память не станет.
9К720
> Насколько я помню любой цикл можно заменить рекурсией, иными словами можно
> переписать алгоритм выделяющий дополнительный массив в рекурсивный вид.
Это с возвратом списка? Нет, желательно без такой фигни.
TarasB
> Это с возвратом списка? Нет, желательно без такой фигни.
Ну суть в том, что стек считается за доп память. В этом легко убедиться, если зайти в рекурсивном вызове слишком глубоко и получить его переполнение.
TarasB
> А вот из-за вставки последнего куска алгоритмическая сложность ухудшается до n*logn*logn.
Если соблюдать (3), то и (2) автоматически нарушается (не считая того, что оно до этого нарушилось за счёт рекурсии). Ты уже не имеешь случайного доступа к коллекции и поэтому как минимум должен загнать в массив указатели на начало каждого блока, то есть это уже sqrt(n) по памяти как минимум.
9К720
Тогда как все эти рекурсивные алгоритмы, которые якобы O(1) доп памяти, выглядят? Рекурсия не хвостовая, циклом так просто не заменится.
TarasB
> Тогда как все эти рекурсивные алгоритмы, которые якобы O(1) доп памяти,
> выглядят?
Пример?
9К720
Кусорт, например. Тут привели какой-то код, но тут очень нетривиальная переделка. Слияние-без-дополнительной-памяти, например, как рекурсивную сортировку половин сделать без рекурсии?
TarasB
Где это ты прочитал что у квиксорта константная сложность по памяти? Википедия в помощь:
Quicksort with in-place and unstable partitioning uses only constant additional space before making any recursive call. Quicksort must store a constant amount of information for each nested recursive call. Since the best case makes at most O(log n) nested recursive calls, it uses O(log n) space. However, without Sedgewick's trick to limit the recursive calls, in the worst case quicksort could make O(n) nested recursive calls and need O(n) auxiliary space.
Перевод нужен?
9К720
а в натуре в таблице эн стоит
TarasB
> Слияние-без-дополнительной-памяти, например, как рекурсивную сортировку половин
> сделать без рекурсии?
Второй листинг: http://ru.wikibooks.org/wiki/Реализации_алгоритмов/Сортировка/Слиянием. Если merge заменить на in-place merge, то получится O(1) по памяти. Но я уже написал, что из-за отсутствия случайного доступа ты его даже так не получишь.
TarasB
Там же эти куски по Sqrt(n) еще надо посортить друг относительно друга. Как это сделать, итерируя по списку, я понятия не имею.
> А вот из-за вставки последнего куска алгоритмическая сложность ухудшается до n*logn*logn
Это если тебе надо, чтобы она была Stable. Для Unstable - n*logn
UPD. Впрочем, есть и стабильный мерж без доп памяти за n*logn, но там пипец http://habrahabr.ru/post/205290/
R.I.P.
> Там же эти куски по Sqrt(n) еще надо посортить друг относительно друга. Как это
> сделать, итерируя по списку, я понятия не имею.
А, точно.
Накодил реализацию алгоритма, подходящую под заданные ограничения:
http://www.everfall.com/paste/id.php?b5dpp4i8zrlv
Пользуясь случаем, выражаю благодарность автору изначальной идеи.
Коменты, естественно, на английском, чтобы TarasB было интереснее их читать.
Если кто хочет потестировать - буду благодарен.
Тема в архиве.