к
Size: a a a
2021 February 14
AA
ну это не то чтоб из лиспов - нормальная емельная фича local
[
Я же правильно понимаю, если мне хочется не O(n^2) в пограничных случаях, понадобится убить константу алгоритма?
Это вообще законная реализация квиксорта? А то я чёт сомневаюсь в её валидности....
Это вообще законная реализация квиксорта? А то я чёт сомневаюсь в её валидности....
AA
Я же правильно понимаю, если мне хочется не O(n^2) в пограничных случаях, понадобится убить константу алгоритма?
Это вообще законная реализация квиксорта? А то я чёт сомневаюсь в её валидности....
Это вообще законная реализация квиксорта? А то я чёт сомневаюсь в её валидности....
это на самом деле трисорт с несбалансированным деревом
[
хм
Прикольно) А можно дерево как-то забалансить?
Прикольно) А можно дерево как-то забалансить?
к
вот это отсюда - https://ru.wikipedia.org/wiki/Быстрая_сортировка
[
ну, если взять описание алгоритма с википедии, то это полностью законная версия, дословная даже, можно покороче даже
qsort [] = []
qsort (x:xs) = qsort l <> (x : qsort r)
where (l, r) = partition (< x) xs
qsort [] = []
qsort (x:xs) = qsort l <> (x : qsort r)
where (l, r) = partition (< x) xs
а оператор <> это типа конкат на максималках?
[
ну по-хорошему в квиксорте нужно случайный опорный элемент брать
со списками это константу убьёт
[
случайность опорного элемента сильно уменьшает вероятность попасть на O(n^2) кейс, т.к. для моей реализации достаточно сунуть предварительно отсортированный список - его будет жевать квадрат итераций
A
случайность опорного элемента сильно уменьшает вероятность попасть на O(n^2) кейс, т.к. для моей реализации достаточно сунуть предварительно отсортированный список - его будет жевать квадрат итераций
она гарантирует среднее время работы n log n
AA
хм
Прикольно) А можно дерево как-то забалансить?
Прикольно) А можно дерево как-то забалансить?
можно, но проще мердж сорт использовать просто
[
она гарантирует среднее время работы n log n
она не гарантирует этого)
если кости выпадут так, что случайный элемент всегда будет минимальным(а ты не можешь гарантировать, что такого кейса не будет), то всё равно квадрат получится)
если кости выпадут так, что случайный элемент всегда будет минимальным(а ты не можешь гарантировать, что такого кейса не будет), то всё равно квадрат получится)
A
она не гарантирует этого)
если кости выпадут так, что случайный элемент всегда будет минимальным(а ты не можешь гарантировать, что такого кейса не будет), то всё равно квадрат получится)
если кости выпадут так, что случайный элемент всегда будет минимальным(а ты не можешь гарантировать, что такого кейса не будет), то всё равно квадрат получится)
я говорю про среднее время работы, то есть про матожидание