Здравствуйте, 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-ом, и почему:
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.