Войти
ФлеймФорумПрограммирование

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

Страницы: 1 2 3 48 Следующая »
#15
17:12, 25 дек. 2014

TarasB
А что за сортировка слиянием без доп памяти, которая подходит под 2 и 3 и не подходит под 1?
А то я только знаю такую, что подходит под 1 и 2 и не подходит под 3.
Та, что я знаю, описана здесь: http://habrahabr.ru/post/138146/

#16
17:25, 25 дек. 2014

R.I.P.
Я про неё же.
Чтобы порезать на куски размером sqrt(N) , итерировать можно и по единичке.

А вот из-за вставки последнего куска алгоритмическая сложность ухудшается до n*logn*logn. По крайней мере, в английской вики в статье про сортировки сказано про квадрат: http://en.wikipedia.org/wiki/Sorting_algorithm

#17
18:02, 25 дек. 2014

TarasB
> трата памяти на стек не считается вообще
Чего это вдруг? Насколько я помню любой цикл можно заменить рекурсией, иными словами можно переписать алгоритм выделяющий дополнительный массив в рекурсивный вид. От этого алгоритм работать за константную память не станет.

#18
18:13, 25 дек. 2014

9К720
> Насколько я помню любой цикл можно заменить рекурсией, иными словами можно
> переписать алгоритм выделяющий дополнительный массив в рекурсивный вид.

Это с возвратом списка? Нет, желательно без такой фигни.

#19
18:19, 25 дек. 2014

TarasB
> Это с возвратом списка? Нет, желательно без такой фигни.
Ну суть в том, что стек считается за доп память. В этом легко убедиться, если зайти в рекурсивном вызове слишком глубоко и получить его переполнение.

#20
18:22, 25 дек. 2014

TarasB
> А вот из-за вставки последнего куска алгоритмическая сложность ухудшается до n*logn*logn.
  Если соблюдать (3), то и (2) автоматически нарушается (не считая того, что оно до этого нарушилось за счёт рекурсии). Ты уже не имеешь случайного доступа к коллекции и поэтому как минимум должен загнать в массив указатели на начало каждого блока, то есть это уже sqrt(n) по памяти как минимум.

#21
18:22, 25 дек. 2014

9К720
Тогда как все эти рекурсивные алгоритмы, которые якобы O(1) доп памяти, выглядят? Рекурсия не хвостовая, циклом так просто не заменится.

#22
18:26, 25 дек. 2014

TarasB
> Тогда как все эти рекурсивные алгоритмы, которые якобы O(1) доп памяти,
> выглядят?
Пример?

#23
18:31, 25 дек. 2014

9К720
Кусорт, например. Тут привели какой-то код, но тут очень нетривиальная переделка. Слияние-без-дополнительной-памяти, например, как рекурсивную сортировку половин сделать без рекурсии?

#24
18:45, 25 дек. 2014

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.

Перевод нужен?
#25
18:59, 25 дек. 2014

9К720
а в натуре в таблице эн стоит

#26
19:02, 25 дек. 2014

TarasB
> Слияние-без-дополнительной-памяти, например, как рекурсивную сортировку половин
> сделать без рекурсии?
  Второй листинг: http://ru.wikibooks.org/wiki/Реализации_алгоритмов/Сортировка/Слиянием. Если merge заменить на in-place merge, то получится O(1) по памяти. Но я уже написал, что из-за отсутствия случайного доступа ты его даже так не получишь.

#27
19:04, 25 дек. 2014

TarasB
Там же эти куски по Sqrt(n) еще надо посортить друг относительно друга. Как это сделать, итерируя по списку, я понятия не имею.

> А вот из-за вставки последнего куска алгоритмическая сложность ухудшается до n*logn*logn
Это если тебе надо, чтобы она была Stable. Для Unstable - n*logn
UPD. Впрочем, есть и стабильный мерж без доп памяти за n*logn, но там пипец http://habrahabr.ru/post/205290/

#28
19:49, 25 дек. 2014

R.I.P.
> Там же эти куски по Sqrt(n) еще надо посортить друг относительно друга. Как это
> сделать, итерируя по списку, я понятия не имею.
А, точно.

#29
5:56, 27 дек. 2014

Накодил реализацию алгоритма, подходящую под заданные ограничения:
http://www.everfall.com/paste/id.php?b5dpp4i8zrlv
Пользуясь случаем, выражаю благодарность автору изначальной идеи.

Коменты, естественно, на английском, чтобы TarasB было интереснее их читать.
Если кто хочет потестировать - буду благодарен.

Страницы: 1 2 3 48 Следующая »
ФлеймФорумПрограммирование

Тема в архиве.