Здравствуйте, 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>

BB>Там, где я его увидел, он это название носит.

Наврядли удастся это сделать, пока не будет обозначено четкое определение quicksort

А вообще,
1. Pivot выбран, список разделен относительно pivot, рекурсия для каждого куска
2. Сложность O(N*logN)

В общем ДА, это quicksort

Есть конечно нюансы, но это вопрос реализации:
1. Для "настоящего" quicksort не нужна дополнительная память (in-place сортировка), но в Haskell такое понятие вообще не имеет смысла.
2. В haskell-версии эта сортировка является еще и устойчивой (stable), в отличии от "оригинала",
Одновременно эти два условия и не соблюсти — stable in-place за O(N*logN) пока не придумали

Здравствуйте, 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>

BB>Там, где я его увидел, он это название носит.

Наврядли удастся это сделать, пока не будет обозначено четкое определение quicksort

А вообще,
1. Pivot выбран, список разделен относительно pivot, рекурсия для каждого куска
2. Сложность O(N*logN)

В общем ДА, это quicksort

Есть конечно нюансы, но это вопрос реализации:
1. Для "настоящего" quicksort не нужна дополнительная память (in-place сортировка), но в Haskell такое понятие вообще не имеет смысла.
2. В haskell-версии эта сортировка является еще и устойчивой (stable), в отличии от "оригинала",
Одновременно эти два условия и не соблюсти — stable in-place за O(N*logN) пока не придумали

И не забываем, что в Haskell сортируется список, т.е. структура с последовательным доступом (в отличии от массива)