На веб-сайте Haskellесть этот пример реализации быстрой сортировки:
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
where
lesser = filter (< p) xs
greater = filter (>= p) xs
На сайте есть объяснение, но у меня есть пара вопросов, на которые я не ответил не вижу, были адресованы ...
- где выполняется фактическое сравнение/замена двух элементов для повторного заказа? Обрабатывается ли это самим определением типа Ord (упорядоченное). Таким образом, тип обеспечивает это условие упорядоченности?
- 'больший' фильтр определяет элементы '>= p' (поворотный элемент), поэтому не означает ли это, что мы получим дополнительную опорную точку [p] в результирующем списке функции из-за '+ + [p]' элемент?
задан dodgy_coder 16 April 2012 в 02:56
поделиться