можно ли сделать быструю сортировку списка только с одним проходом?

Я изучаю haskell, и я вижу определение функции:

quickSort (x : xs) = (quickSort less) ++ (x : equal) ++ (quickSort more)
                 where less = filter (< x) xs
                       equal = filter (== x) xs
                       more = filter (> x) xs

Можно ли написать его только с одним обходом списка, а не с 3-мя?


sorting haskell quicksort difference-lists
person Salil    schedule 03.10.2011    source источник
comment
Быстрая сортировка в среднем имеет сложность O(n lg n)...   -  person Etienne de Martel    schedule 04.10.2011
comment
Сложность заключается в количестве сделанных сравнений, и в приведенной выше версии будет в 3 раза больше сравнений, чем в той, которая разделяет список, проходя по нему один раз.   -  person Salil    schedule 04.10.2011
comment
какая разница, сколько раз он проходит по списку? сложность такая же   -  person newacct    schedule 04.10.2011
comment
@newacct, это не просто просмотр списка; он сравнивает каждый элемент при обходе; поэтому.   -  person Salil    schedule 04.10.2011
comment
@Salil: правильно, но O(3n log n) == O(n log n) поэтому сложность времени выполнения одинакова (фактическое время выполнения может быть не таким же, но это отличается от сложности).   -  person ivanm    schedule 04.10.2011
comment
@ivanm, да, сложность та же, и в среднем она составляет O (n log n). Но это O (n ^ 2), в худшем случае. Однако вопрос правомерен вне зависимости от этого факта, а реализации алгоритмов обычно измеряются величиной постоянного множителя.   -  person HaskellElephant    schedule 04.10.2011
comment
@ivanm, нотация O (n) - это способ измерения сложности. Это не значит, что сложность одинакова. Предположим, я измеряю расстояния в милях, чтобы мне было легче. Это не означает, что мне требуется одно и то же время, чтобы дойти до соседней двери и до близлежащего торгового центра.   -  person Salil    schedule 04.10.2011

Ответы (3)


arrow_upward
7
arrow_downward

Несмотря на запоздание, вот версия, которая должна не утекать так много места (и, кажется, работает примерно в два раза быстрее, чем другая трехсторонняя версия здесь):

qsort3 xs = go xs [] 
  where
    go     (x:xs) zs       = part x xs zs [] [] []
    go     []     zs       = zs
    part x []     zs a b c = go a ((x : b) ++ go c zs)
    part x (y:ys) zs a b c =
        case compare y x of
                  LT -> part x ys zs (y:a) b c
                  EQ -> part x ys zs a (y:b) c
                  GT -> part x ys zs a b (y:c)

Это устраняет возможную проблему с использованием кортежей, где let (a,b) = ... фактически преобразуется в let t= ...; a=fst t; b=snd t, что приводит к ситуации, когда даже после того, как a было использовано и обработано, он все еще остается живым как часть кортежа t для чтения b. от него - хотя конечно совершенно ненужного. Это известно как «проблема утечки парного пространства Вадлера». Или, может быть, GHC (с -O2) умнее этого. :)

Также здесь явно используется подход списки различий (спасибо, hammar), что также делает его немного более эффективным (примерно в два раза быстрее, чем версия, использующая кортежи). Я думаю, что part использует параметры аккумулятора, так как строит их в обратном порядке.

person Will Ness    schedule 03.03.2012
comment
ср. вариант стабильной сортировки внизу этого ответа. - person Will Ness; 09.10.2018

arrow_upward
13
arrow_downward

Вы имеете в виду что-то вроде этого?

quicksort [] = []
quicksort (x:xs) = quicksort less ++ (x : equal) ++ quicksort more
  where (less, equal, more) = partition3 x xs

partition3 _ [] = ([], [], [])
partition3 x (y:ys) =
  case compare y x of
    LT -> (y:less, equal, more)
    EQ -> (less, y:equal, more)
    GT -> (less, equal, y:more)
  where (less, equal, more) = partition3 x ys

Обратите внимание, что на самом деле это не быстрая сортировка, так как настоящая быстрая сортировка находится на месте.

person hammar    schedule 04.10.2011
comment
Это было аккуратно. Исходный алгоритм, о котором я говорил, также не выполняет быструю сортировку на месте. Я предполагаю, что «на месте» означает изменяемую версию, в которой список изменяется на месте. - person Salil; 04.10.2011
comment
разве это не проблема пар Вадлера, которая должна привести к утечке пространства? (Я разместил другую версию, которая должна не иметь этой проблемы, сделанную по его методике IIRC). - person Will Ness; 04.03.2012
comment
@WillNess: ваша версия, безусловно, более эффективна, особенно потому, что она использует списки различий вместо (++) для добавления. Мой может выделить немного больше, так как он использует кортежи, но я не думаю, что он должен пропускать пространство. Однако я не знаком с проблемой пары Вадлера. У вас есть ссылка? Google, похоже, тоже не знал об этом. - person hammar; 04.03.2012
comment
Утечка пространства в паре google Wadler в основном связана с let (a,b)=span ... вещами, которые переводятся в let p=span ...; a=fst$p; b=snd$p, что приводит к тому, что p сохраняется для b, даже когда a уже используется. Пары... :) (я имею в виду кортежи... IIRC это именно то, о чем должна была быть эта утечка). - person Will Ness; 04.03.2012
comment
@WillNess: Ах да, я понимаю, что вы имеете в виду. Однако я не уверен, что назвал бы это утечкой пространства, поскольку это приводит только к сохранению хвостов трех списков, что в любом случае необходимо делать, в дополнение к самим кортежам. Если бы я делал что-то еще с этими списками, а не просто читал перед ними, это определенно могла бы быть утечка. - person hammar; 04.03.2012
comment
Я думаю, что это должно привести к тому, что lesser все еще будет храниться даже после того, как он будет потреблен и отсортирован, как часть тройки, также содержащей bigger. Похоже на утечку. :) А может GHC с -O2 умнее этого. :) - person Will Ness; 04.03.2012
comment
@WillNess: Верно. Возможно, вы могли бы добавить текст к своему ответу, в котором кратко излагаются проблемы с моим решением и то, как ваше улучшает это? Думаю, это будет полезно будущим читателям. - person hammar; 04.03.2012
comment
Кстати, я думаю, что ваша версия является истинным идиоматическим решением Haskell; Жаль, что компилятор не может автоматически выполнить то преобразование, которое мне пришлось кодировать вручную. Мы естественным образом выражаем параллельное присваивание с помощью кортежей переменных; это вина Haskell в том, что он не имеет явной концепции и заставляет нас использовать kludge, а затем наказывает нас за это... - person Will Ness; 05.03.2012
comment
@Salil на месте обычно относится к изменяемым значениям элементов массива, а не к созданию копии массива с более упорядоченными элементами. Для списков, когда cons-ячейки явно повторно связаны (например, в Common LISP и т. д.), сохраняя содержимое ячеек нетронутым, это также можно рассматривать как на месте, поскольку в процессе не создается новое хранилище. - person Will Ness; 15.05.2012

arrow_upward
9
arrow_downward

Ничего не улучшает, кроме:

qs (x:xs) = let (a,b) = partition (< x) xs in (qs a) ++ [x] ++ (qs b)
person qq191    schedule 04.10.2011
comment
Это было здорово. Почему вы думаете, что это ничего не улучшает? Он проходит по списку только один раз. Так что сравнений гораздо меньше. - person Salil; 04.10.2011
comment
@ qq191: это определение предполагает отсутствие повторяющихся значений, поэтому в оригинале есть три фильтра! - person ivanm; 04.10.2011
comment
@JonasDuregård: подождите, вы правы; они входят в раздел b. - person ivanm; 04.10.2011