Здравствуйте, _DAle_, Вы писали:
EP>>Это их фейл. EP>>Даже Степанов этот момент упоминал, конкретно Lomuto vs Hoare partition в CLRS (34:18): EP>>https://youtu.be/d4tFGtGngf4?t=2058 EP>>ЕМНИП даже кто-то из CLRS это в своей лекции что-то такое упоминал. _DA>Окей. Я не согласен. Я считаю, что тот конкретный алгоритм, который когда-то описал Хоар — это одна из реализаций того, что сейчас называется Quicksort (а та конкретная называется сортировкой Хоара). На мой взгляд, сейчас (а не в прошлом веке) по термином Quicksort подразумевают семейство алгоритмов (например, в той же википедии это так), с конкретным подходом: divide and conquer + pivot, и вполне определенной временной сложностью по времени в среднем и худшем случае.
Ошибаются, IMO. Также как и часто путают selection sort и bubble sort. Также как и отнесли трюк с логарифмическим стеком Седжвику.
_DA>Если считать, что, например, Lomuto partition — это уже не Quicksort, не in-place реализация — не Quicksort, тогда отсутствие хвостовой рекурсии — это тоже не Quicksort?
В статье, ссылку на которую я привёл, вообще описывается явный стек (nest). Существенным моментом здесь является не tail-call сам по себе, а гарантия лографмического размера — вполне алгоритмическая черта.
_DA>А переход на insertion sort для малых интервалов — это Quicksort или нет?
Это будет гибрид. Например часто в реализациях std::sort используется следующая схема: начинаем с quicksort, в середине можем перейти на heapsort (чтобы получить линеаритмический худший случай) и заканчиваем insertion sort — и для этого варианта есть специальное отдельное название — introsort.
_DA>Если Quicksort — это только то, что Хоар описал в 60-х, так она тогда на практике и не используется нигде (в модуле turbo pascal разве что..
Quicksort используется в гибридах типа introsort, которая используется в реализациях STL, потому что она действительно quick, как раз из-за inplace'ности и unguarded bidirectional partition — то чего нет в коде из первого сообщения.
_DA>а хотя стойте, там же нет хвостовой рекурсии ).
Причём тут "нет хвостовой рекурсии"? Она элементарно "эмулируется" вручную.
_DA>В целом, я за позицию wikipedia и Кормена et al.
Применение Lomuto partition для подобной сортировки — это крайне нерационально. Степанов объяснил почему — получается крайне неэффективно, так как намного чаще вырождается в квадратичность.
Для алгоритмического курса это действительно фейл.
В общем, я за то чтобы называть quicksort'ом только вариации близкие к оригинальной статье Хоара по двум причинам:
1) Сортировка называется quicksort — этот quick является неотъемлемой её частью.
2) Замечательный факт в том, что алгоритм шестидесятых годов, разрабатываемый под те железные реалии, остаётся крайне актуальным (действительно quick) и в наше время. И это как раз благодаря тем чертам, которых нет в коде из первого сообщения, и которые подробно описаны в оригинальной статье. Если же мы будем называть любую концептуально медленную вариацию этим именем — то связь с оригиналом действительно будет размываться.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>В статье, ссылку на которую я привёл, вообще описывается явный стек (nest). Существенным моментом здесь является не tail-call сам по себе, а гарантия лографмического размера — вполне алгоритмическая черта.
Quicksort, описанный во многих книжках по алгоритмике с O(n) памяти — это не Quicksort тогда, так? Ну и, конечно же, stable версии алгоритма тогда не существует.
EP>Применение Lomuto partition для подобной сортировки — это крайне нерационально. Степанов объяснил почему — получается крайне неэффективно, так как намного чаще вырождается в квадратичность.
Честно говоря, Степанов произнес там какую-то наивную речь. Типа не протестировали, не обратили внимание. Код с Lomuto partition имеет очевидные проблемы, это всем понятно (уж людям уровня авторов CLRS так точно). Так же, как и любая другая реализация Quicksort, каждая со своими проблемами, поэтому в нормальных библиотеках и используют introsort.
Здравствуйте, Basil B, Вы писали:
BB>Предлагаю обменяться мнениями по поводу того, имеет ли право этот "знаменитый двустрочник" на хаскеле называться quicksort-ом, и почему: BB>
BB>qsort [] = []
BB>qsort (x:xs) = qsort [y | y <- xs, y < x] ++ [x] ++ qsort [y | y <- xs, y >= x]
BB>
Даже если отбросить inplace, pivot, log stack size — всё равно здесь есть существенное алгоритмическое отличие от оригинального quicksort.
В оригинальном quicksort разбиение происходит с обоих концов диапазона, причём используются предикаты x <= pivot и x >= pivot — то есть значения равные pivot могут как в правой так и в левой части. Это например позволяет оптимально делить массивы (либо под-массивы) состоящие из одинаковых элементов. То есть вырождение в квадратичность происходит в меньшем классе случаев.
Чтобы достичь подобных характеристик через фильтры — придётся разбивать на три части <x, ==x, >x.
Здравствуйте, Basil B, Вы писали:
BB>Предлагаю обменяться мнениями по поводу того, имеет ли право этот "знаменитый двустрочник" на хаскеле называться quicksort-ом
Это скорее сортировка двоичным несбалансированным деревом.
Квиксорт на хаскеле выглядит, например, так:
import qualified Data.Vector.Generic as V
import qualified Data.Vector.Generic.Mutable as M
qsort :: (V.Vector v a, Ord a) => v a -> v a
qsort = V.modify go where
go xs | M.length xs < 2 = return ()
| otherwise = do
p <- M.read xs (M.length xs `div` 2)
j <- M.unstablePartition (< p) xs
let (l, pr) = M.splitAt j xs
k <- M.unstablePartition (== p) pr
go l; go $ M.drop k pr
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, Klapaucius, Вы писали:
K>Квиксорт на хаскеле выглядит, например, так:
Ближе, но всё равно не то.
K>
K>import qualified Data.Vector.Generic as V
K>import qualified Data.Vector.Generic.Mutable as M
K>qsort :: (V.Vector v a, Ord a) => v a -> v a
K>qsort = V.modify go where
K> go xs | M.length xs < 2 = return ()
K> | otherwise = do
K> p <- M.read xs (M.length xs `div` 2)
K> j <- M.unstablePartition (< p) xs
K> let (l, pr) = M.splitAt j xs
K> k <- M.unstablePartition (== p) pr
K> go l; go $ M.drop k pr
K>
* здесь два разбиения на три класса эквивалентности <, ==, > (причём лучше было бы использовать сразу three-way partition, а-ля Dutch national flag problem). В оригинальном же quicksort одно разбиение, причём в левой части могут быть <= и в правой >= .
* здесь нет гарантии на логарифмическую глубину стэка, которая есть в оригинальном quicksort.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>* здесь два разбиения на три класса эквивалентности <, ==, > (причём лучше было бы использовать сразу three-way partition, а-ля Dutch national flag problem). В оригинальном же quicksort одно разбиение, причём в левой части могут быть <= и в правой >= .
Это все не делает обсуждаемый алгоритм "не квиксортом".
EP> гарантия на логарифмическую глубину стэка, которая есть в оригинальном quicksort.
Да ну? Правда что ли?
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, Klapaucius, Вы писали:
K>Здравствуйте, T4r4sB, Вы писали:
K>>>Mutable TB>>И кто мне тут про чистоту рассказывал?
K>Где вы тут увидели противоречие?
Ну чистота же это когда нет ничего мутабельного.
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Здравствуйте, Klapaucius, Вы писали:
EP>>* здесь два разбиения на три класса эквивалентности <, ==, > (причём лучше было бы использовать сразу three-way partition, а-ля Dutch national flag problem). В оригинальном же quicksort одно разбиение, причём в левой части могут быть <= и в правой >= . K>Это все не делает обсуждаемый алгоритм "не квиксортом".
Сильно другое количество сравнений/перестановок, другое количество проходов по памяти, принципиально другие точки разбиения — вполне веские причины чтобы не называть это quicksort'ом, IMO.
Не говоря уже о другой сложности по памяти (обсуждаемой в другой ветке).
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Сильно другое количество сравнений/перестановок,
Асимптотика не меняется.
EP>другое количество проходов по памяти,
Асимптотика не меняется.
EP>принципиально другие точки разбиения — вполне веские причины чтобы не называть это quicksort'ом, IMO.
Это никак не изменяет то, что в реальности различные модификации quicksort называют quicksort.
EP>Не говоря уже о другой сложности по памяти (обсуждаемой в другой ветке).
У меня есть пример Dijkstra's algorithm. Вообще, оригинальный алгоритм имел временную сложность O(V^2). Простой алгоритм, использующий приоритетную очередь, имеет сложность O(E*logV), и тоже называется алгоритмом Дейкстры. Алгоритм, где в качестве приоритетной очереди используется куча Фибоначчи, имеет сложность O(E+V*logV) и тем не менее эту реализацию тоже называют реализацией алгоритма Дейкстры. А в нашем споре у различных видов реализации сортировки абстрактный алгоритм тот же и сложность та же.
Здравствуйте, _DAle_, Вы писали:
EP>>Сильно другое количество сравнений/перестановок, _DA>Асимптотика не меняется. EP>>другое количество проходов по памяти, _DA>Асимптотика не меняется.
Одинаковая асимптотическая сложность не является достаточным условием. Количество операций тоже имеет значение.
Конкретный пример: hoare_partition vs lomuto_partition — асимптотическая сложность одинаковая, а количество операций разное
EP>>принципиально другие точки разбиения — вполне веские причины чтобы не называть это quicksort'ом, IMO. _DA>Это никак не изменяет то, что в реальности различные модификации quicksort называют quicksort.
Вот я как раз против этого невежества. Оригинальный quicksort имеет куда лучшие характеристики чем поделки называемые его именем.
EP>>Не говоря уже о другой сложности по памяти (обсуждаемой в другой ветке). _DA>У меня есть пример Dijkstra's algorithm. Вообще, оригинальный алгоритм имел временную сложность O(V^2). Простой алгоритм, использующий приоритетную очередь, имеет сложность O(E*logV), и тоже называется алгоритмом Дейкстры. Алгоритм, где в качестве приоритетной очереди используется куча Фибоначчи, имеет сложность O(E+V*logV) и тем не менее эту реализацию тоже называют реализацией алгоритма Дейкстры.
Надо смотреть оригинальную статью Дейкстры.
В любом случае, я не против того чтобы улучшенный алгоритм называли именем автора.
Я против того чтобы изуродованную версию, с намного худшими характеристиками (см. первое сообщение темы), принципиально противоречащими изначальной концепции заложенной автором (quicksort же) называли оригинальным именем.
_DA>А в нашем споре у различных видов реализации сортировки абстрактный алгоритм тот же и сложность та же.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Сильно другое количество сравнений/перестановок, другое количество проходов по памяти, принципиально другие точки разбиения — вполне веские причины чтобы не называть это quicksort'ом, IMO. EP>Не говоря уже о другой сложности по памяти (обсуждаемой в другой ветке).
Это ваше мнение находится в коренном противоречии со сложившейся практикой употребления названия quicksort. Впрочем, это уже ответили.
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, Klapaucius, Вы писали:
EP>>Сильно другое количество сравнений/перестановок, другое количество проходов по памяти, принципиально другие точки разбиения — вполне веские причины чтобы не называть это quicksort'ом, IMO. EP>>Не говоря уже о другой сложности по памяти (обсуждаемой в другой ветке). K>Это ваше мнение находится в коренном противоречии со сложившейся практикой употребления названия quicksort. Впрочем, это уже ответили.
Я в курсе про "сложившуюся практику", и как уже сказал — против этого невежества. Оригинальный quicksort это inplace алгоритм (в смысле логарифмической гарантии на дополнительную память), это одно из главных необходимых свойств — в твоём варианте нет даже этого.
Тот же Erik Meijer открыто считает вопрос спорным, и не таким однозначным, иначе не делал бы дополнительные оговорки, ссылку выше приводил.
). 
