Как работает быстрая сортировка в Haskell?

На веб-сайте 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]' элемент?

5
задан dodgy_coder 16 April 2012 в 02:56
поделиться