AP
И никакое in-place тут ни при чём. Просто есть конкретный алгоритм "quicksort" и вы либо реализуете его, либо это будет другой алгоритм
Size: a a a
2021 January 04
DK
Как это не причём? In-place это требование по памяти и очень важное
DK
В хаскеле будет одна копия и та — ленивая ;) И
take 3 (sort l) вполне себе разумный минимум элементов насортирует, чтобы получить три наименьшихКакой там алгоритм под капотом?
AP
Denis Krivosheev
Как это не причём? In-place это требование по памяти и очень важное
Есть алгоритм X работающий in-place, есть алгоритм Y, работающий в отдельной памяти, вы выбмраете под ваши требования тот или другой
AP
Что ещё за "требования по памяти и очень важные"
AP
У разных алгоритмов разные свойства. Но не "разные у одного"
AP
У кого-то требования по памяти, у других — по процессору, у третьих — возможность "делить и властвовать"
AP
Denis Krivosheev
Какой там алгоритм под капотом?
Точно не помню, merge sort вроде в каком-то виде
AP
Потому что хорошо подходит для ленивости
AP
(а не потому что там требования какие-то)
DK
Точно не помню, merge sort вроде в каком-то виде
Но мерджсорт не даст «приемлемое количество сравнений» в ленивом виде
DK
Может какая-то модификация квикселекта
AP
"Функциональный мерджморт" :)
AP
Берём первый, остальные делим на "больше первого" и "меньше первого", сортируем половины рекурсивно, сливаем
DK
Да но по сути нам надо получить первые n
DK
То есть какая-то модификация порядковой статистики
AP
Ну так и будут отсортированы только левые половины и те не до конца
AP
Фильтры-то тоже ленивые :)
DK
Интересная штука
AP
Взяли голову, получили два стрима меньших и больших. Стрим меньших можно обрабатывать дальше. Берём голову, получаем два подстрима